{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T05:21:05Z","timestamp":1789968065737,"version":"4.0.1"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Numer. Anal."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>We consider linear systems arising from the use of the finite element method for solving scalar linear elliptic problems. Our main result is that these linear systems, which are symmetric and positive semidefinite, are well approximated by symmetric diagonally dominant matrices. Our framework for defining matrix approximation is support theory. Significant graph theoretic work has already been developed in the support framework for preconditioners in the diagonally dominant case, and, in particular, it is known that such systems can be solved with iterative methods in nearly linear time. Thus, our approximation result implies that these graph theoretic techniques can also solve a class of finite element problems in nearly linear time. We show that the support number bounds, which control the number of iterations in the preconditioned iterative solver, depend on mesh quality measures but not on the problem size or shape of the domain.<\/jats:p>","DOI":"10.1137\/040611781","type":"journal-article","created":{"date-parts":[[2008,10,17]],"date-time":"2008-10-17T18:04:21Z","timestamp":1224266661000},"page":"3264-3284","source":"Crossref","is-referenced-by-count":37,"title":["Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners"],"prefix":"10.1137","volume":"46","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"}]},{"given":"Stephen","family":"Vavasis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,10,17]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0045-7825(75)90038-9"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"H. Avron, D. Chen, G. Shklarski, and S. Toledo,\n                      Combinatorial preconditioners for scalar elliptic finite-element problems\n                      , preprint, Tel-Aviv University, Tel-Aviv, 2006.","DOI":"10.1002\/pamm.200700828"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"O. Axelsson and V. A. Barker,\n                      Finite Element Solution of Boundary Value Problems: Theory and Computation\n                      , SIAM Press, Philadelphia, 2001.","DOI":"10.1137\/1.9780898719253"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801384019"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801390637"},{"key":"R6","unstructured":"D. Chen and S. Toledo,\n                      Vaidya's preconditioners: Implementation and experimental study\n                      , Electron. Trans. Numer. Anal., 16 (2003); also available online from http:\/\/etna.mcs.kent.edu."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2004.05.016"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/S0885-064X(03)00011-6"},{"key":"R9","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, New York, NY, 2005, Association for Computing Machinery, pp. 494\u2013503.","DOI":"10.1145\/1060590.1060665"},{"key":"R10","unstructured":"G. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , 3rd ed., Johns Hopkins University Press, Baltimore, 1996."},{"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, Pittsburg, PA, 1996. Available as Technical Report CMU-CS-96-123."},{"key":"R12","unstructured":"R. Gupta,\n                      Support Graph Preconditioners for Sparse Linear Systems\n                      , Master's thesis, Texas A&M University, College Station, TX, 2004. Available online at https:\/\/txspace.tamu.edu\/ bitstream\/1969.1\/1353\/1\/etd-tamu-2004C-2-CPSC-Gupta.pdf."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01740546"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479800370871"},{"key":"R15","unstructured":"C. Johnson,\n                      Numerical Solution of Partial Differential Equations by the Finite Element Method\n                      , Cambridge University Press, London, 1987."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827500371499"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796314124"},{"key":"R18","unstructured":"T. Phillips and G. Miller,\n                      private communication\n                      , 2005."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"J. R. Shewchuk,\n                      Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator\n                      , in Applied Computational Geometry: Towards Geometric Engineering, Lecture Notes Comput. Sci. 1148, M. C. Lin and D. Manocha, eds., Springer, Berlin, 1996, pp. 203\u2013222. From the First ACM Workshop on Applied Computational Geometry.","DOI":"10.1007\/BFb0014497"},{"key":"R20","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 Proceedings of the 36th Annual ACM Symposium on Theory of Computing, ACM Press, New York, NY, 2004, pp. 81\u201390.","DOI":"10.1145\/1007352.1007372"},{"key":"R21","unstructured":"S. Vavasis,\n                      A Bernstein-B\u00e9zier sufficient condition for invertibility of polynomial mappings\n                      , http:\/\/arxiv.org\/abs\/cs.NA\/0308021 (2003)."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/0733045"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"M. Wang and V. Sarin,\n                      Parallel support graph preconditions\n                      , in High Performance Computing \u2013 HiPC 2006, Lecture Notes Comput. Sci. 4297, Y. Roberts, M. Parashas, R. Badrinath, and V. Prasanna, eds., Springer, Berlin, 2006, pp. 387\u2013398.","DOI":"10.1007\/11945918_39"}],"container-title":["SIAM Journal on Numerical Analysis"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/040611781","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:15:19Z","timestamp":1787325319000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/040611781"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":23,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/040611781"],"URL":"https:\/\/doi.org\/10.1137\/040611781","relation":{},"ISSN":["0036-1429","1095-7170"],"issn-type":[{"value":"0036-1429","type":"print"},{"value":"1095-7170","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}