{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:31:59Z","timestamp":1787383919741,"version":"build-2736575974"},"reference-count":67,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We consider parallel preconditioning to solve large sparse linear systems $Ax=b$ using conjugate gradients when A is symmetric and positive definite. We develop a preconditioner that can be viewed as a hybrid of incomplete factorization and sparse approximate inversion schemes. Such a hybrid can potentially enable fast and reliable solution through a preconditioner with low memory requirements that allows latency-tolerant construction and application on multiprocessor systems. We propose a parallel hybrid scheme which yields a preconditioner as a tree-structured aggregate of sparse incomplete factors and inverses of selected submatrices. We analyze the computation and communication costs of our hybrid preconditioner and report on its parallel performance on some well-known test matrices. Our results indicate that our hybrid has significant advantages over sparse approximate inverse preconditioners and incomplete Cholesky preconditioners using either drop-threshold or zero-level-of-fill schemes.<\/jats:p>","DOI":"10.1137\/080739987","type":"journal-article","created":{"date-parts":[[2010,5,14]],"date-time":"2010-05-14T18:13:52Z","timestamp":1273860832000},"page":"1323-1345","source":"Crossref","is-referenced-by-count":10,"title":["Parallel Hybrid Preconditioning: Incomplete Factorization with Selective Sparse Approximate Inversion"],"prefix":"10.1137","volume":"32","author":[{"given":"Padma","family":"Raghavan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Keita","family":"Teranishi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,5,14]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"P. R. Amestoy, I. S. Duff, and J.Y. L'Excellent,\n                      Multifrontal parallel distributed symmetric and unsymmetric sparse solvers\n                      , Comput. Methods Appl. Mech. Engrg. (2000), pp. 501\u2013520.","DOI":"10.1016\/S0045-7825(99)00242-X"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/0911033"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/060675940"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"O. Axelsson,\n                      Iterative Solution Methods\n                      , Cambridge University Press, Cambridge, UK, 1994.","DOI":"10.1017\/CBO9780511624100"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"S. Balay, W. D. Gropp, L. C. McInnes, and B. F. Smith,\n                      Efficient management of parallelism in object oriented numerical software libraries\n                      , in Modern Software Tools in Scientific Computing, E. Arge, A. M. Bruaset, and H. P. Langtangen, eds., Birkh\u00e4user, Boston, 1997, pp. 163\u2013202.","DOI":"10.1007\/978-1-4612-1986-6_8"},{"key":"R6","unstructured":"S. Balay, W. D. Gropp, L. C. McInnes, and B. F. Smith,\n                      PETSc Users Manual\n                      , Tech. Rep. ANL-95\/11-Revision 2.1.1, Argonne National Laboratories, Argonne, IL, 2002."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"R. Barrett, M. W. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. van der Vorst,\n                      Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods\n                      , SIAM, Philadelphia, PA, 1994.","DOI":"10.1137\/1.9781611971538"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827594271421"},{"key":"R9","unstructured":"M. Bollh\u00f6fer and Y. Saad,\n                      ILUPACK\u2014Preconditioning Software Package\n                      , Release V1.0, 2004; available online from http:\/\/www.math.tu-berlin.de\/ilupack\/."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/040608271"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"W. L. Briggs, V. E. Henson, and S. F. McCormick,\n                      A Multigrid Tutorial\n                      , 2nd ed., SIAM, Philadelphia, PA, 2000.","DOI":"10.1137\/1.9780898719505"},{"key":"R12","unstructured":"R. Chandra, S. Eisenstat, and M. Schultz,\n                      The modified conjugate residual method for partial differential equations\n                      , in Advances in Computer Methods for Partial Differential Equations. II, R. Vichnevetsky, ed., IMACS, New Brunswick, NJ, 1977, pp. 13\u201319."},{"key":"R13","unstructured":"E. Chow and Y. Saad,\n                      Robust Preconditioning for Sparse Linear Systems\n                      , Ph.D. thesis, Department of Computer Science, University of Minnesota, Minneapolis, MN, 1997."},{"key":"R14","unstructured":"E. Chow,\n                      ParaSails User's Guide\n                      , Tech. Rep. UCRL-MA-137863, Lawrence Livermore National Laboratory, Livermore, CA, 2000."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1177\/109434200101500106"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"E. Chow, R. D. Falgout, J. J. Hu, R. S. Tuminaro, and U. M. Yang,\n                      A survey of parallelization techniques for multigrid solvers\n                      , in Parallel Processing for Scientific Computing, M. A. Heroux, P. Raghavan, and H. D. Simon, eds., SIAM, Philadelphia, PA, 2006, pp. 179\u2013201.","DOI":"10.1137\/1.9780898718133.ch10"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827594270415"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598339402"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"P. Concus, G. Golub, and D. 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":"R20","doi-asserted-by":"publisher","DOI":"10.1080\/00207169208804097"},{"key":"R21","unstructured":"T. Davis,\n                      University of Florida Sparse Matrix Collection\n                      , http:\/\/www.cise.ufl.edu\/research\/ sparse\/matrices\/."},{"key":"R22","unstructured":"J. Demmel, S. C. Eisenstat, J. R. Gilbert, X. S. Li, and J. W. H. Liu,\n                      A Supernodal Approach to Sparse Partial Pivoting\n                      , Tech. Rep. CSL\u201394\u201314, Xerox Palo Alto Research Center, Palo Alto, CA, 1995."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"J. W. Demmel,\n                      Applied Numerical Linear Algebra\n                      , SIAM, Philadelphia, PA, 1997.","DOI":"10.1137\/1.9781611971446"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/040615729"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"J. J. Dongarra, I. S. Duff, D. C. Sorensen, and H. A. van der Vorst,\n                      Numerical Linear Algebra for High-Performance Computers\n                      , SIAM, Philadelphia, PA, 1998.","DOI":"10.1137\/1.9780898719611"},{"key":"R26","unstructured":"I. S. Duff, A. M. Erisman, and J. K. Reid,\n                      Direct Methods for Sparse Matrices\n                      , Oxford University Press, Oxford, UK, 1986."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/0909038"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/0915044"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"R. D. Falgout and U. M. Yang,\n                      Hypre: A Library of High Performance Preconditioners\n                      , in Computational Science - ICCS 2002, Part III, P. Sloot, C. Tan, J. Dongarra, and A. Hoekstra, eds., Lecture Notes in Comput. Sci. 2331, Springer-Verlag, Berlin, 2002, pp. 632\u2013641.","DOI":"10.1007\/3-540-47789-6_66"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1137\/0909021"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/1031001"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/0715069"},{"key":"R34","unstructured":"A. George and J. W.H. Liu,\n                      Computer Solution of Large Sparse Positive Definite Systems\n                      , Prentice-Hall, Englewood Cliffs, NJ, 1981."},{"key":"R35","unstructured":"G. Golub and C. Van Loan,\n                      Matrix Computations\n                      , 3rd ed., Johns Hopkins University Press, Baltimore, MD, 1996."},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1137\/1031003"},{"key":"R37","unstructured":"A. Grama, A. Gupta, G. Karypis, and V. Kumar,\n                      Introduction to Parallel Computing\n                      , 2nd ed., Addison\u2013Wesley, Reading, MA, 2003."},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1137\/0613011"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827594276552"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9274(01)00115-5"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"M. Jones and P. Plassmann,\n                      The efficient parallel iterative solution of large sparse linear systems\n                      , in Graph Theory and Sparse Matrix Computations, A. George, J. R. Gilbert, and J. W. H. Liu, eds., IMA Vol. Math. Appl. 56, Springer-Verlag, New York, 1994, pp. 229\u2013245.","DOI":"10.1007\/978-1-4613-8369-7_11"},{"key":"R43","unstructured":"M. T. Jones and P. E. Plassmann,\n                      Blocksolve$95$ Users Manual: Scalable Library Software for the Parallel Solution of Sparse Linear Systems\n                      , Tech. Rep. ANL-95\/48, Argonne National Laboratory, Argonne, IL, 1995."},{"key":"R44","unstructured":"G. Karypis and V. Kumar,\n                      ParMETIS: Parallel Graph Partitioning and Sparse Matrix Ordering Library\n                      , Tech. Rep. TR 97-060, Department of Computer Science, University of Minnesota, 1997."},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1137\/0614004"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1137\/0614019"},{"key":"R48","unstructured":"D. Luenberger,\n                      Introduction to Linear and Nonlinear Programming\n                      , 2nd ed., Addison\u2013Wesley, Reading, MA, 1984."},{"key":"R49","doi-asserted-by":"crossref","unstructured":"K. Malkowski and P. Raghavan,\n                      Multi-pass mapping schemes for parallel sparse matrix computation\n                      , in Proceedings of the 5th International Conference of Computational Science (ICCS2005), V. S. Sunderam, G. D. van Albada, P. M. A. Sloot, and J. J. Dongarra, eds., Lecture Notes in Comput. Sci. 3514, Springer-Verlag, Berlin, 2005, pp. 245\u2013255.","DOI":"10.1007\/11428831_31"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1980-0559197-0"},{"key":"R51","first-page":"148","volume":"31","author":"Meijerink J. A.","year":"1977","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1145\/355887.355893"},{"key":"R53","doi-asserted-by":"crossref","unstructured":"K. Nakajima,\n                      Parallel iterative solvers of geofem with selective blocking preconditioning for nonlinear contact problems on the earth simulator\n                      , in Proceedings of SC2003: High Performance Networking and Computing, 2003; http:\/\/www.sc-conference.org\/sc2003\/.","DOI":"10.1145\/1048935.1050164"},{"key":"R54","unstructured":"E. Ng, B. Peyton, and P. Raghavan,\n                      A blocked incomplete Cholesky preconditioner for hierarchical-memory computers\n                      , in Proceedings of the 4th IMACS International Symposium on Iterative Methods in Scientific Computation, D. R. Kincaid and A. C. Elster, eds., IMACS Ser. Comput. Appl. Math. 5, 1999, pp. 211\u2013221."},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1137\/0914063"},{"key":"R56","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1096-9128(200002\/03)12:2\/3<53::AID-CPE473>3.0.CO;2-B"},{"key":"R57","doi-asserted-by":"publisher","DOI":"10.1137\/0914074"},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626498000067"},{"key":"R59","unstructured":"P. Raghavan,\n                      DSCPACK: Domain-Separator Codes for Solving Sparse Linear Systems\n                      , Tech. Rep. CSE-02-004, Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA, 2002."},{"key":"R60","doi-asserted-by":"publisher","DOI":"10.1002\/nla.327"},{"key":"R61","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1680010405"},{"key":"R62","doi-asserted-by":"crossref","unstructured":"Y. Saad,\n                      Iterative Method for Sparse Linear Systems\n                      , 2nd ed., SIAM, Philadelphia, PA, 2003.","DOI":"10.1137\/1.9780898718003"},{"key":"R63","doi-asserted-by":"publisher","DOI":"10.1007\/BF01389450"},{"key":"R64","unstructured":"K. Teranishi,\n                      Scalable Hybrid Sparse Linear Solvers\n                      , Ph.D. thesis, Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA, 2004."},{"key":"R65","doi-asserted-by":"crossref","unstructured":"K. Teranishi, P. Raghavan, and E. Ng,\n                      A new data-mapping scheme for latency-tolerant distributed sparse triangular solution\n                      , in Proceedings of the 2002 ACM\/IEEE Conference on Supercomputing, 2002, pp. 238\u2013247.","DOI":"10.1109\/SC.2002.10020"},{"key":"R66","unstructured":"R. Tuminaro, M. Heroux, S. Hutchinson, and J. Shadid,\n                      Official Aztec User's Guide: Version\n                      2.1, Tech. Rep. SAND99-8801, Sandia National Laboratories, 1999."},{"key":"R67","doi-asserted-by":"publisher","DOI":"10.1137\/0719024"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080739987","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:13:44Z","timestamp":1787328824000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080739987"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":67,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080739987"],"URL":"https:\/\/doi.org\/10.1137\/080739987","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}