{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T03:21:58Z","timestamp":1791429718105,"version":"4.3.3"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2003,1]]},"abstract":"<jats:p>We present support theory, a set of techniques for bounding extreme eigenvalues and condition numbers for matrix pencils. Our intended application of support theory is to enable proving condition number bounds for preconditioners for symmetric, positive definite systems. One key feature sets our approach apart from most other works: We use support numbers instead of generalized eigenvalues. Although closely related, we believe support numbers are more convenient to work with algebraically.<\/jats:p>\n                  <jats:p>This paper provides the theoretical foundation of support theory and describes a set of analytical tools and techniques. For example, we present a new theorem for bounding support numbers (generalized eigenvalues) where the matrices have a known factorization (not necessarily square or triangular). This result generalizes earlier results based on graph theory. We demonstrate the utility of this approach by a simple example: block Jacobi preconditioning on a model problem. Also, our analysis of a new class of preconditioners, maximum-weight basis preconditioners, in [E. G. Boman, D. Chen, B. Hendrickson, and S. Toledo, Numer. Linear Algebra Appl., to appear] is based on results contained in this paper.<\/jats:p>","DOI":"10.1137\/s0895479801390637","type":"journal-article","created":{"date-parts":[[2003,12,22]],"date-time":"2003-12-22T21:00:49Z","timestamp":1072126849000},"page":"694-717","source":"Crossref","is-referenced-by-count":71,"title":["Support Theory for Preconditioning"],"prefix":"10.1137","volume":"25","author":[{"given":"Erik G.","family":"Boman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bruce","family":"Hendrickson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0613052"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511624100"},{"key":"R3","volume-title":"Finite element solution of boundary value problems","author":"Axelsson O.","year":"1984"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(84)90088-0"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(87)90211-4"},{"key":"R6","unstructured":"M. Bern, J. R. Gilbert, B. Hendrickson, N. Nguyen, and S. Toledo,\n                      Support\u2010Graph Preconditioners\n                      , tech. report, School of Computer Science, Tel\u2010Aviv University, 2001;"},{"key":"R6","unstructured":"SIAM J. Matrix Anal. Appl., submitted."},{"key":"R7","unstructured":"E. G. Boman, D. Chen, B. Hendrickson, and S. Toledo,\n                      Maximum\u2010weight\u2010basis preconditioners\n                      , Numer. Linear Algebra Appl., to appear."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1080\/10637199308915437"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(93)00087-G"},{"key":"R10","volume-title":"Matrix computations","author":"Golub Gene","year":"1989"},{"key":"R11","unstructured":"K. Gremban,\n                      Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems\n                      , Ph.D. thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, 1996;"},{"key":"R11","unstructured":"available as Tech. Report CMU\u2010CS\u201096\u2010123."},{"key":"R12","unstructured":"K. Gremban, G. L. Miller, and M. Zagha,\n                      Performance evaluation of a new parallel preconditioner\n                      , in Proceedings of the 9th International Parallel Processing Symposium, IEEE Computer Society Press, Los Alamitos, CA, 1995, pp. 65\u201369; a longer version is available as Tech. Report CMU\u2010CS\u201094\u2010205, Carnegie Mellon University, Pittsburgh, PA, 1994."},{"key":"R13","unstructured":"S. Guattery,\n                      Graph Embedding Techniques for Bounding Condition Numbers of Incomplete Factor Preconditioners\n                      , Tech. Report 97\u201047, ICASE, NASA Langley Research Center, Hampton, VA, 1997."},{"key":"R14","unstructured":"Stephen Guattery, Tom Leighton, Gary Miller, The path resistance method for bounding \u03bb2 of a Laplacian, ACM, New York, 1997, 201\u20132101447666"},{"key":"R15","unstructured":"R. A. Horn,\n                      Personal communication\n                      , 2001."},{"key":"R16","unstructured":"V. Howle and S. Vavasis,\n                      An Iterative Method for Solving Complex\u2010Symmetric Systems Arising in Electric Power Modeling\n                      , tech. report, Cornell University, Ithaca, NY, 2000;"},{"key":"R16","unstructured":"SIAM J. Matrix Anal. Appl., submitted."},{"key":"R17","unstructured":"B. M. Irons and G. Treharne,\n                      A bound theorem in eigenvalues and its practical applications\n                      , in Proceedings of the Third Conference on Matrix Methods in Structural Mechanics, Wright\u2013Patterson AFB, Dayton, Ohio, 1971."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0045-7825(91)90240-7"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(93)90320-N"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(91)90395-D"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(91)90400-Q"},{"key":"R22","unstructured":"Y. Notay, Upper eigenvalue bounds and related modified incomplete factorization strategies, North\u2010Holland, Amsterdam, 1992, 551\u20135621159764"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(98)10162-3"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(98)00191-6"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(98)00191-6"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1911.140.1"},{"key":"R26","unstructured":"B. Smith, P. E. Bj\u00f8rstad, and W. Gropp,\n                      Domain Decomposition. Parallel Multilevel Methods for Elliptic Partial Differential Equations\n                      , Cambridge University Press, Cambridge, UK, 1996."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050306"},{"key":"R28","unstructured":"P. M. Vaidya,\n                      Solving Linear Equations with Symmetric Diagonally Dominant Matrices by Constructing Good Preconditioners\n                      , manuscript."},{"key":"R29","volume-title":"Matrix iterative analysis","author":"Varga Richard","year":"1962"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/0045-7825(89)90052-2"},{"key":"R31","unstructured":"D. M. Young,\n                      Iterative Solution of Large Linear Systems\n                      , Academic Press, New York, 1971."}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895479801390637","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:37:56Z","timestamp":1787333876000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895479801390637"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["10.1137\/S0895479801390637"],"URL":"https:\/\/doi.org\/10.1137\/s0895479801390637","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}