×

A fast algorithm for sparse matrix computations related to inversion. (English) Zbl 1297.65030

J. Comput. Phys. 242, 915-945 (2013); erratum ibid. 252, 535-536 (2013).
Summary: We have developed a fast algorithm for computing certain entries of the inverse of a sparse matrix. Such computations are critical to many applications, such as the calculation of non-equilibrium Green’s functions \(\mathbf{G}^r\) and \(\mathbf{G}^<\) for nano-devices. The FIND (Fast Inverse using Nested Dissection) algorithm is optimal in the big-O sense. However, in practice, FIND suffers from two problems due to the width-2 separators used by its partitioning scheme. One problem is the presence of a large constant factor in the computational cost of FIND. The other problem is that the partitioning scheme used by FIND is incompatible with most existing partitioning methods and libraries for nested dissection, which all use width-1 separators. Our new algorithm resolves these problems by thoroughly decomposing the computation process such that width-1 separators can be used, resulting in a significant speedup over FIND for realistic devices – up to twelve-fold in simulation. The new algorithm also has the added advantage that desired off-diagonal entries can be computed for free. Consequently, our algorithm is faster than the current state-of-the-art recursive methods for meshes of any size. Furthermore, the framework used in the analysis of our algorithm is the first attempt to explicitly apply the widely-used relationship between mesh nodes and matrix computations to the problem of multiple eliminations with reuse of intermediate results. This framework makes our algorithm easier to generalize, and also easier to compare against other methods related to elimination trees. Finally, our accuracy analysis shows that the algorithms that require back-substitution are subject to significant extra round-off errors, which become extremely large even for some well-conditioned matrices or matrices with only moderately large condition numbers. When compared to these back-substitution algorithms, our algorithm is generally a few orders of magnitude more accurate, and our produced round-off errors stay at a reasonable level.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices

Software:

CSparse; SelInv
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Datta, S., Nanoscale device modeling: the Green’s function method, Superlattices and Microstructures, 28, 4, 253-278 (2000)
[2] Svizhenko, A.; Anantram, M. P.; Govindan, T. R.; Biegel, B., Two-dimensional quantum mechanical modeling of nanotransistors, Journal of Applied Physics, 91, 4, 2343-2354 (2002)
[3] Cauley, S.; Jain, J.; Koh, C.-K.; Balakrishnand, V., A scalable distributed method for quantum-scale device simulation, Journal of Applied Physics, 101, 123715 (2007)
[4] Li, S.; Ahmed, S.; Darve, E., Fast inverse using nested dissection for NEGF, Journal of Computational Electronics, 6, 187-190 (2007)
[5] Li, S.; Ahmed, S.; Klimeck, G.; Darve, E., Computing entries of the inverse of a sparse matrix using the FIND algorithm, Journal of Computational Physics, 227, 9408-9427 (2008) · Zbl 1214.82124
[7] George, A.; Ng, E., On row and column orderings for sparse least squares problems, SIAM Journal on Numerical Analysis, 20, 2, 326-344 (1983) · Zbl 0513.65019
[8] Gilbert, J.; Zmijewski, E., A parallel graph partitioning algorithm for a message-passing multiprocessor, International Journal of Parallel Programming, 16, 6, 427-449 (1987) · Zbl 0657.68073
[9] Pothen, A.; Simon, H.; Liou, K., Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, 11, 3, 430-452 (1990) · Zbl 0711.65034
[10] Varah, J., The calculation of the eigenvectors of a general complex matrix by inverse iteration, Mathematics of Computation, 22, 785-791 (1968) · Zbl 0174.46903
[11] Peters, G.; Wilkinson, J., Linear algebra, (Handbook for Automatic Computation. Handbook for Automatic Computation, The Calculation of Specified Eigenvectors by Inverse Iteration, vol. II (1971), Springer-Verlag), 418-439
[13] Peters, G.; Wilkinson, J., Inverse iteration ill-conditioned equations and Newton’s method, SIAM Review, 21, 339-360 (1979) · Zbl 0424.65021
[15] Lin, L.; Lu, J.; Car, R.; E, W., Multipole representation of the Fermi operator with application to the electronic structure analysis of metallic systems, Physical Review B, 79, 11, 115133 (2009)
[16] Petersen, D. E.; Li, S.; Stokbro, K.; Sørensen, H. H.B.; Hansen, P. C.; Skelboe, S.; Darve, E., A hybrid method for the parallel computation of Green’s functions, Journal of Computational Physics, 228, 14, 5020-5039 (2009) · Zbl 1280.82010
[20] Lin, L.; Yang, C.; Lu, J.; Ying, L.; E, W., SelInv — an algorithm for selected inversion of a sparse symmetric matrix, ACM Transactions on Mathematical Software, 37, 4, 40:1-40:19 (2011) · Zbl 1365.65069
[21] George, A., Nested dissection of a regular finite-element mesh, SIAM Journal on Numerical Analysis, 10, 2, 345-363 (1973) · Zbl 0259.65087
[22] Davis, T. B., Direct Methods for Sparse Linear Systems (2006), Society for Industrial and Applied Mathematics
[23] Heath, M.; Ng, E.; Peyton, B., Parallel algorithms for sparse linear systems, SIAM Review, 33, 3, 420-460 (1991) · Zbl 0738.65014
[24] Liu, J., Equivalent sparse matrix reordering by elimination tree rotations, SIAM Journal on Scientific and Statistical Computing, 9, 424 (1988) · Zbl 0651.65016
[25] Liu, J., The role of elimination trees in sparse factorization, SIAM Journal on Matrix Analysis and Applications, 11, 134 (1990) · Zbl 0697.65013
[28] Lin, L.; Lu, J.; Ying, L.; Car, R.; E, W., Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems, Communications in Mathematical Sciences, 7, 755-777 (2009) · Zbl 1182.65072
[29] Cauley, S.; Jain, J.; Koh, C.-K.; Balakrishnand, V., A two-dimensional domain decomposition technique for the simulation of quantum-scale devices, Journal of Computational Physics, 231, 1293-1313 (2012) · Zbl 1242.65263
[32] Ng, E.; Peyton, B., Block sparse cholesky algorithms on advanced uniprocessor computers, SIAM Journal on Scientific Computing, 14, 1034 (1993) · Zbl 0785.65015
[33] Duff, I.; Reid, J., The multifrontal solution of indefinite sparse symmetric linear equations, ACM Transactions on Mathematical Software, 6, 302-325 (1983) · Zbl 0515.65022
[34] Duff, I.; Erisman, A.; Reid, J., On george’s nested dissection method, SIAM Journal on Numerical Analysis, 13, 5, 686-695 (1976) · Zbl 0345.65015
[35] George, A., An automatic nested dissection algorithm for irregular finite element problems, SIAM Journal on Numerical Analysis, 15, 5, 1053-1069 (1978)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.