research-article

SelInv---An Algorithm for Selected Inversion of a Sparse Symmetric Matrix

Authors:

Weinan EAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 37, Issue 4

Article No.: 40, Pages 1 - 19

https://doi.org/10.1145/1916461.1916464

Published: 01 February 2011 Publication History

Abstract

We describe an efficient implementation of an algorithm for computing selected elements of a general sparse symmetric matrix A that can be decomposed as A = LDLT, where L is lower triangular and D is diagonal. Our implementation, which is called SelInv, is built on top of an efficient supernodal left-looking LDLT factorization of A. We discuss how computational efficiency can be gained by making use of a relative index array to handle indirect addressing. We report the performance of SelInv on a collection of sparse matrices of various sizes and nonzero structures. We also demonstrate how SelInv can be used in electronic structure calculations.

References

[1]

Alemany, M., Jain, M., Kronik, L., and Chelikowsky, J. 2004. Real-space pseudopotential method for computing the electronic properties of periodic systems. Phys. Rev. B 69, 075101.

[2]

Amestoy, P., Duff, I., L’Excellent, J.-Y., and Koster, J. 2001. A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM J. Matrix Anal. Appl. 23, 15--41.

Digital Library

[3]

Ashcraft, C. and Grimes, R. 1989. The influence of relaxed supernode partitions on the multifrontal method. ACM Trans. Math. Softw. 15, 291--309.

Digital Library

[4]

Ashcraft, C. and Grimes, R. 1999. SPOOLES: An object-oriented sparse matrix library. In Proceedings of the 9th SIAM Conference on Parallel Processing.

[5]

Ashcraft, C., Grimes, R. G., and Lewis, J. G. 1998. Accurate symmetric indefinite linear equation solvers. SIAM J. Matrix Anal. Appl. 20, 513--561.

Digital Library

[6]

Bekas, C., Kokiopoulou, E., and Saad, Y. 2005. Polynomial filtered Lanczos iterations with applications in Density Functional Theory. SIAM J. Matrix Anal. Appl. 30, 1, 397--418.

Digital Library

[7]

Browne, S., Dongarra, J., Garner, N., Ho, G., and Mucci, P. 2000. A portable programming interface for performance evaluation on modern processors. Int. J. High Perform. C. 14, 189.

Digital Library

[8]

Bunch, J. R. and Kaufman, L. 1977. Some stable methods for calculating inertia and solving symmetric linear systems. Math. Comp. 163--179.

[9]

Bunch, J. R. and Parlett, B. N. 1971. Direct methods for solving symmetric indefinite systems of linear equations. SIAM J. Numer. Anal. 8, 639--655.

Digital Library

[10]

Burden, R. L., Faires, J. D., and Reynolds, A. C. 2000. Numerical Analysis. Brooks Cole, Independence, KY.

[11]

Chelikowsky, J., Troullier, N., and Saad, Y. 1994. Finite-difference-pseudopotential method: Electronic structure calculations without a basis. Phys. Rev. Lett. 72, 1240--1243.

[12]

Datta, S. 1997. Electronic Transport in Mesoscopic Systems. Cambridge University Press, Cambridge, U.K.

[13]

Davis, T. 1997. University of Florida sparse matrix collection. NA Digest 97, 7.

[14]

Duff, I. and Reid, J. 1987. Direct Methods for Sparse Matrices. Oxford University, London, UK.

Digital Library

[15]

Duff, I., Grimes, R., and Lewis, J. 1992. Users guide for the Harwell-Boeing sparse matrix collection. Research and Technology Division, Boeing Computer Services, Seattle, WA.

[16]

Duff, I. S. and Reid, J. K. 1983. The multifrontal solution of indefinite sparse symmetric sets of linear equations. ACM Trans. Math. Softw. 9, 302--325.

Digital Library

[17]

Economou, E. 2006. Green’s Functions in Quantum Physics. Springer Berlin, Germany.

[18]

Erisman, A. and Tinney, W. 1975. On computing certain elements of the inverse of a sparse matrix. Comm. ACM 18, 177.

Digital Library

[19]

George, A. 1973. Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10, 345--363.

Digital Library

[20]

George, A. and Liu, J. 1981. Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Englewood Cliffs, NJ.

Digital Library

[21]

Gilbert, J. 1984. Predicting structure in sparse matrix computations. SIAM J. Matrix Anal. Appl. 15, 4, 62--79.

Digital Library

[22]

Gilbert, J. and Peierls, T. 1986. Sparse partial pivoting in time proportional to arithmetic operations. SIAM J. Sci. Stat. Comput. 9, 5, 862--874.

Digital Library

[23]

Greengard, L. and Rokhlin, V. 1987. A fast algorithm for particle simulations. J. Comput. Phys. 73, 2, 325--348.

Digital Library

[24]

Gupta, A. 1997. WSMP: The Watson Sparse Matrix Package. IBM Research rep. RC 21886(98462).

[25]

Gupta, A., Karypis, G., and Kumar, V. 1997. Highly scalable parallel algorithms for sparse matrix factorization. IEEE Trans. Parall. Distrib. Syst. 8, 502--520.

Digital Library

[26]

Hohenberg, P. and Kohn, W. 1964. Inhomogeneous electron gas. Phys. Rev. 136, B864.

[27]

Kohn, W. and Sham, L. 1965. Self-consistent equations including exchange and correlation effects. Phys. Rev. 140, A1133.

[28]

Lehoucq, R., Sorensen, D., and Yang, C. 1998. ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods. SIAM, Philadelphia, PA.

[29]

Li, S., Ahmed, S., Klimeck, G., and Darve, E. 2008. Computing entries of the inverse of a sparse matrix using the FIND algorithm. J. Comput. Phys. 227, 9408--9427.

Digital Library

[30]

Lin, L., Lu, J., Car, R., and E, W. 2009a. Multipole representation of the Fermi operator with application to the electronic structure analysis of metallic systems. Phys. Rev. B 79, 115133.

[31]

Lin, L., Lu, J., Ying, L., Car, R., and E, W. 2009b. Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems. Comm. Math. Sci. 7, 755--777.

[32]

Lin, L., Lu, J., Ying, L., and E, W. 2009c. Pole-based approximation of the Fermi-Dirac function. Chinese Ann. Math. 30B, 729--742.

[33]

Lin, L., Yang, C., Lu, J., Ying, L., and E, W. 2009d. A fast parallel algorithm for selected inversion of structured sparse matrices with application to 2D electronic structure calculations. Tech. rep. LBNL-2677E. Lawrence Berkeley National Laboratory, Berkeley.

[34]

Liu, J. 1985. Modification of the minimum degree algorithm by multiple elimination. ACM Trans. Math. Softw. 11, 141--153.

Digital Library

[35]

Liu, J. 1990. The role of elimination trees in sparse factorization. SIAM J. Matrix Anal. Appl. 11, 134.

Digital Library

[36]

Martin, R. 2004. Electronic Structure---Basic Theory and Practical Methods. Cambridge University Press, Cambridge. UK.

[37]

Moler, C. 2004. Numerical Computing with MATLAB. SIAM, Philadelphia, PA.

[38]

Ng, E. and Peyton, B. 1993. Block sparse Cholesky algorithms on advanced uniprocessor computers. SIAM J. Sci. Comput. 14, 1034.

Digital Library

[39]

Payne, M. C., Teter, M. P., Allen, D. C., Arias, T. A., and Joannopoulos, J. D. 1992. Iterative minimization techniques for ab initio total energy calculation: Molecular dynamics and conjugate gradients. Rev. Mod. Phys. 64, 4, 1045--1097.

[40]

Petersen, D., Li, S., Stokbro, K., Sørensen, H., Hansen, P., Skelboe, S., and Darve, E. 2009. A hybrid method for the parallel computation of Green’s functions. J. Comput. Phys. 228, 5020--5039.

Digital Library

[41]

Raghavan, P. 2002. DSCPACK: Domain-separator codes for solving sparse linear systems. Tech. rep. CSE-02-004. Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA.

[42]

Rothberg, E. and Gupta, A. 1994. An efficient block-oriented approach to parallel sparse choleskyfactorization. SIAM J. Sci. Comput. 15, 1413--1439.

Digital Library

[43]

Schenk, O. and Gartner, K. 2006. On fast factorization pivoting methods for symmetric indefinite systems. Elec. Trans. Numer. Anal. 23, 158--179.

[44]

Takahashi, K., Fagan, J., and Chin, M. 1973. Formation of a sparse bus impedance matrix and its application to short circuit study. In Proceedings of the 8th PICA Conference. Minneapolis, MN.

[45]

Zhou, Y., Saad, Y., Tiago, M. L., and Chelikowsky, J. R. 2006. Self-consistent-field calculations using chebyshev-filtered subspace iteration. J. Comput. Phys. 219, 172--184.

Digital Library

Cited By

Harbrecht HKempf RMulterer M(2025)Construction of quasi-localized dual bases in reproducing kernel Hilbert spacesJournal of Computational and Applied Mathematics10.1016/j.cam.2025.116545465(116545)Online publication date: Sep-2025
https://doi.org/10.1016/j.cam.2025.116545
Schäfer FOwhadi H(2024)Sparse Recovery of Elliptic Solvers from Matrix-Vector ProductsSIAM Journal on Scientific Computing10.1137/22M154226X46:2(A998-A1025)Online publication date: 12-Mar-2024
https://doi.org/10.1137/22M154226X
Leamer JDawson WBondar D(2024)Positivity preserving density matrix minimization at finite temperatures via square rootThe Journal of Chemical Physics10.1063/5.0189864160:7Online publication date: 20-Feb-2024
https://doi.org/10.1063/5.0189864
Show More Cited By

Index Terms

SelInv---An Algorithm for Selected Inversion of a Sparse Symmetric Matrix
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms
2. Mathematics of computing
  1. Mathematical software

Recommendations

PSelInv—A Distributed Memory Parallel Algorithm for Selected Inversion: The Symmetric Case

We describe an efficient parallel implementation of the selected inversion algorithm for distributed memory computer systems, which we call PSelInv. The PSelInv method computes selected elements of a general sparse matrix A that can be decomposed as A = ...
The multifrontal method for sparse matrix solution: theory and practice
A Supernodal Approach to Sparse Partial Pivoting

We investigate several ways to improve the performance of sparse LU factorization with partial pivoting, as used to solve unsymmetric linear systems. We introduce the notion of unsymmetric supernodes to perform most of the numerical computation in dense ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 37, Issue 4

February 2011

212 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/1916461

Issue’s Table of Contents

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 2011

Accepted: 01 August 2010

Revised: 01 March 2010

Received: 01 October 2009

Published in TOMS Volume 37, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

94
Total Citations
View Citations
812
Total Downloads

Downloads (Last 12 months)53
Downloads (Last 6 weeks)6

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Harbrecht HKempf RMulterer M(2025)Construction of quasi-localized dual bases in reproducing kernel Hilbert spacesJournal of Computational and Applied Mathematics10.1016/j.cam.2025.116545465(116545)Online publication date: Sep-2025
https://doi.org/10.1016/j.cam.2025.116545
Schäfer FOwhadi H(2024)Sparse Recovery of Elliptic Solvers from Matrix-Vector ProductsSIAM Journal on Scientific Computing10.1137/22M154226X46:2(A998-A1025)Online publication date: 12-Mar-2024
https://doi.org/10.1137/22M154226X
Leamer JDawson WBondar D(2024)Positivity preserving density matrix minimization at finite temperatures via square rootThe Journal of Chemical Physics10.1063/5.0189864160:7Online publication date: 20-Feb-2024
https://doi.org/10.1063/5.0189864
Pathrudkar SThiagarajan PAgarwal SBanerjee AGhosh S(2024)Electronic structure prediction of multi-million atom systems through uncertainty quantification enabled transfer learningnpj Computational Materials10.1038/s41524-024-01305-710:1Online publication date: 12-Aug-2024
https://doi.org/10.1038/s41524-024-01305-7
Tu YXu ZYang H(2024)Hierarchical Interpolative Factorization for Self Green’s Function in 3D Modified Poisson-Boltzmann EquationsCommunications on Applied Mathematics and Computation10.1007/s42967-023-00352-z7:2(536-561)Online publication date: 6-Mar-2024
https://doi.org/10.1007/s42967-023-00352-z
Harbrecht HMulterer MSchenk OSchwab C(2024)Multiresolution kernel matrix algebraNumerische Mathematik10.1007/s00211-024-01409-8156:3(1085-1114)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00211-024-01409-8
Cunha DPavanello R(2024)Finite variation sensitivity analysis in the design of isotropic metamaterials through discrete topology optimizationInternational Journal for Numerical Methods in Engineering10.1002/nme.7560125:19Online publication date: 27-Jun-2024
https://doi.org/10.1002/nme.7560
Lebedeva IGarcía AArtacho EOrdejón P(2023)Modular implementation of the linear- and cubic-scaling orbital minimization methods in electronic structure codes using atomic orbitalsRoyal Society Open Science10.1098/rsos.23006310:4Online publication date: 26-Apr-2023
https://doi.org/10.1098/rsos.230063
Switzer HStathopoulos ARomero ELaeuchli JOrginos K(2022)Probing for the Trace Estimation of a Permuted Matrix Inverse Corresponding to a Lattice DisplacementSIAM Journal on Scientific Computing10.1137/21M142249544:4(B1096-B1121)Online publication date: 22-Aug-2022
https://doi.org/10.1137/21M1422495
Tu YPang QYang HXu Z(2022)Linear-scaling selected inversion based on hierarchical interpolative factorization for self Green's function for modified Poisson-Boltzmann equation in two dimensionsJournal of Computational Physics10.1016/j.jcp.2021.110893461:COnline publication date: 15-Jul-2022
https://dl.acm.org/doi/10.1016/j.jcp.2021.110893
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents