{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T05:26:30Z","timestamp":1787376390116,"version":"build-2736575974"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>We present a new preconditioner for linear systems arising from finite-element discretizations of scalar elliptic partial differential equations (PDE's). The solver splits the collection $\\{K_{e}\\}$ of element matrices into a subset of matrices that are approximable by diagonally dominant matrices and a subset of matrices that are not approximable. The approximable $K_{e}$'s are approximated by diagonally dominant matrices $L_{e}$'s that are assembled to form a global diagonally dominant matrix L. A combinatorial graph algorithm then approximates L by another diagonally dominant matrix M that is easier to factor. Finally, M is added to the inapproximable elements to form the preconditioner, which is then factored. When all the element matrices are approximable, which is often the case, the preconditioner is provably efficient. Approximating element matrices by diagonally dominant ones is not a new idea, but we present a new approximation method which is both efficient and provably good. The splitting idea is simple and natural in the context of combinatorial preconditioners, but hard to exploit in other preconditioning paradigms. Experimental results show that on problems in which some of the $K_{e}$'s are ill conditioned, our new preconditioner is more effective than an algebraic multigrid solver, than an incomplete-factorization preconditioner, and than a direct solver.<\/jats:p>","DOI":"10.1137\/060675940","type":"journal-article","created":{"date-parts":[[2009,6,17]],"date-time":"2009-06-17T18:04:42Z","timestamp":1245261882000},"page":"694-720","source":"Crossref","is-referenced-by-count":5,"title":["Combinatorial Preconditioners for Scalar Elliptic Finite-Element Problems"],"prefix":"10.1137","volume":"31","author":[{"given":"Haim","family":"Avron","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Doron","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gil","family":"Shklarski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sivan","family":"Toledo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,6,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen,\n                      LAPACK User's Guide\n                      , 3rd ed., SIAM, Philadelphia, 1999. Also available online from http:\/\/www.netlib.org.","DOI":"10.1137\/1.9780898719604"},{"key":"R2","unstructured":"H. Avron, E. Ng, and S. Toledo,\n                      Using perturbed QR factorizations to solve linear least-squares problems\n                      , SIAM J. Sci. Comput., submitted."},{"key":"R3","unstructured":"H. Avron, G. Shklarski, and S. Toledo,\n                      On element SDD approximability\n                      , Technical report, Tel-Aviv University, Israel, Apr. 2008, http:\/\/www.cs.tau.ac.il\/~haima\/element_approximability.pdf."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01385880"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801384019"},{"key":"R6","unstructured":"D. S. Bernstein,\n                      Matrix Mathematics: Theory, Facts, and Formulas with Applications to Linear Systems Theory\n                      , Princeton University Press, Princeton, NJ, 2005."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1002\/nla.343"},{"key":"R8","unstructured":"E. G. Boman and B. Hendrickson,\n                      On spanning tree preconditioners\n                      , unpublished manuscript, Sandia National Laboratories, 2001."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801390637"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/040611781"},{"key":"R11","unstructured":"R. D. Braatz,\n                      Response to Chen and Toledo on \u201cminimizing the Euclidean condition number\u201d\n                      , private communication, Sept. 2005."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012992238680"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598344303"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S106482750139892X"},{"key":"R15","first-page":"30","volume":"16","author":"Chen D.","year":"2003","journal-title":"Electron. Trans. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1097-4067","issn-type":"print"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2004.05.016"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"P. Concus, G. H. Golub, and D. P. O'Leary,\n                      A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations\n                      , in Sparse Matrix Computations, J. R. Bunch and D. J. Rose, eds., Academic Press, New York, 1976, pp. 309\u2013332.","DOI":"10.1016\/B978-0-12-141050-6.50023-4"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"M. Elkin, Y. Emek, D. A. Spielman, and S.H. Teng,\n                      Lower-stretch spanning trees\n                      , in Proceedings of the 37th annual ACM symposium on Theory of computing (STOC), Baltimore, MD, 2005, ACM Press, New York, pp. 494\u2013503.","DOI":"10.1145\/1060590.1060665"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/S105262340240519X"},{"key":"R20","unstructured":"K. D. Gremban,\n                      Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems\n                      , Ph.D. thesis, School of Computer Science, Carnegie Mellon University, Oct. 1996. Available as Technical Report CMU-CS-96-123."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"K. D. 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, 1995, pp. 65\u201369. A longer version is available as Technical Report CMU-CS-94-205, Carnegie-Mellon University.","DOI":"10.1109\/IPPS.1995.395915"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1080\/00207160108805133"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9274(01)00115-5"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021882330897"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"R27","unstructured":"I. Koutis and G. L. Miller,\n                      A linear work, O(n$^{1\/6}$) time, parallel algorithm for solving planar Laplacians\n                      , in Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, LA, January 7\u20139, 2007, N. Bansal, K. Pruhs, and C. Stein, eds., SIAM, Philadelphia, 2007, pp. 1002\u20131011."},{"key":"R28","doi-asserted-by":"crossref","unstructured":"U. Langer, S. Reitzinger, and J. Schicho,\n                      Symbolic methods for the element preconditioning technique\n                      , Technical report, Johannes Kepler Universit\u00e4t (JKU) Linz, Jan. 2002.","DOI":"10.1007\/3-540-45084-X_15"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"B. M. Maggs, G. L. Miller, O. Parekh, R. Ravi, and S. L. M. Woo,\n                      Finding effective support-tree preconditioners\n                      , in SPAA '05: Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, ACM Press, New York, 2005, pp. 176\u2013185.","DOI":"10.1145\/1073970.1073996"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1980-0559197-0"},{"key":"R31","unstructured":"The MathWorks,\n                      Matlab version\n                      7.2. software package, Jan. 2006."},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1977-0438681-4"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/0712047"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503429121"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827593258280"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(200003)35:2<91::AID-NET1>3.0.CO;2-T"},{"key":"R37","unstructured":"S. Reitzinger,\n                      Algebraic multigrid and element preconditioning\n                      I, Technical report, J. Kepler Universit\u00e4t (JKU) Linz, Dec. 1998."},{"key":"R38","doi-asserted-by":"crossref","unstructured":"M. Resense and G. Veiga,\n                      An efficient implementation of the network interior-point method\n                      , in Network Flows and Matching: The First DIMACS Implementation Challenge, D. Johnson and C. McGeoch, eds., DIMACS Series in Discrete Mathematics and Computer Science 12, AMS, New York, 1993.","DOI":"10.1090\/dimacs\/012\/12"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(82)90101-X"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1080\/03081089108818065"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1137\/060650295"},{"key":"R42","unstructured":"H. Si,\n                      TetGen, A Quality Tetrahedral Mesh Generator and Three-Dimensional Delaunay Triangulator: Users's Manual for Version\n                      1.4, Jan. 2006, available online from http:\/\/tetgen.berlios.de."},{"key":"R43","doi-asserted-by":"crossref","unstructured":"D. A. Spielman and S.H. Teng,\n                      Solving sparse, symmetric, diagonally-dominant linear systems in time $0(m^{1.31})$\n                      , in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, Oct. 2003, pp. 416\u2013427.","DOI":"10.1109\/SFCS.2003.1238215"},{"key":"R44","doi-asserted-by":"crossref","unstructured":"D. A. Spielman and S.H. Teng,\n                      Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems\n                      , in STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, ACM Press, New York, 2004, pp. 81\u201390.","DOI":"10.1145\/1007352.1007372"},{"key":"R45","unstructured":"D. A. Spielman and S.H. Teng,\n                      Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems\n                      , unpublished manuscript available online at http:\/\/arxiv.org\/abs\/cs\/0607105, 2006."},{"key":"R46","unstructured":"P. M. Vaidya,\n                      Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners\n                      , unpublished manuscript. A talk based on this manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computations, Minneapolis, MN, October 1991."},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165096"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1137\/0717066"},{"key":"R49","unstructured":"S. Vavasis, private communication, 2007."}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060675940","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:45:27Z","timestamp":1787334327000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060675940"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/060675940"],"URL":"https:\/\/doi.org\/10.1137\/060675940","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}