×

Fast sparse selected inversion. (English) Zbl 1323.65024

Summary: We propose a fast structured selected inversion method for extracting the diagonal blocks of the inverse of a sparse symmetric matrix \(A\), using the multifrontal method and rank structures. When \(A\) arises from the discretization of some partial differential equations (PDEs) and has a low-rank property (the intermediate dense matrices in the factorization have small off-diagonal numerical ranks), structured approximations of the diagonal blocks and certain off-diagonal blocks of \(A^{-1}\) (that are needed to find the diagonal blocks of \(A^{-1}\)) can be quickly computed. A structured multifrontal LDL factorization is first computed for \(A\) with a forward traversal of an assembly tree, which yields a sequence of local data-sparse factors. The factors are used in a backward traversal of the tree for the structured inversion. The intermediate operations in the inversion are performed in hierarchically semiseparable or low-rank forms. With the assumptions of data sparsity and appropriate rank conditions, the theoretical structured inversion cost is proportional to the matrix size \(n\) times a low-degree polylogarithmic function of \(n\) after structured factorizations. The memory counts are similar. In comparison, existing direct selected inversion methods cost \(O(n^{3/2})\) flops in two dimensions and \(O(n^{2})\) flops in three dimensions for both the factorization and the inversion, with \(O(n^{4/3})\) memory in three dimensions. Additional formulas for efficient structured operations are also derived. Numerical tests on two- and three-dimensional discretized PDEs and more general sparse matrices are done to demonstrate the performance.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
15A23 Factorization of matrices
65F50 Computational methods for sparse matrices
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. R. Amestoy, I. S. Duff, J. Y. L’Excellent, Y. Robert, F. H. Rouet, and B. Uçar, {\it On computing inverse entries of a sparse matrix in an out-of-core environment}, SIAM J. Sci. Comput., 34 (2012), pp. A1975-A1999. · Zbl 1252.05108
[2] M. Bebendorf and W. Hackbusch, {\it Existence of }\( \mathcal{H} \){\it -matrix approximants to the inverse FE-matrix of elliptic operators with }\(L^∞\){\it -Coefficients}, Numer. Math., 95 (2003), pp. 1-28. · Zbl 1033.65100
[3] C. Bekas, A. Curioni, and I. Fedulova, {\it Low cost high performance uncertainty quantification}, in Proceedings of the 2nd Workshop on High Performance Computational Finance, ACM, New York, 2009, 8.
[4] S. Börm, {\it Adaptive variable-rank approximation of general dense matrices}, SIAM J. Sci. Comput., 30 (2008), pp. 148-168. · Zbl 1159.65324
[5] S. Börm, {\it Efficient Numerical Methods for Non-local Operators}, EMS Tracts Math. 14, European Mathematical Society, Zurich, 2010. · Zbl 1208.65037
[6] S. Börm and W. Hackbusch, {\it Data-sparse approximation by adaptive }\( \mathcal{H}^2 \){\it -matrices}, Computing, 69 (2002), pp. 1-35. · Zbl 1012.65023
[7] S. Börm, L. Grasedyck, and W. Hackbusch, {\it Introduction to hierarchical matrices with applications}, Eng. Anal. Bound. Elem., 27 (2003), pp. 405-422. · Zbl 1035.65042
[8] S. Cauley, J. Jain, C. K. Koh, and V. Balakrishnan, {\it A scalable distributed method for quantum-scale device simulation}, J. Appl. Phys., 101 (2007), 123715.
[9] S. Chandrasekaran, P. Dewilde, M. Gu, W. Lyons, and T. Pals, {\it A fast solver for HSS representations via sparse matrices}, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 67-81. · Zbl 1135.65317
[10] S. Chandrasekaran, M. Gu, and T. Pals, {\it A fast }\( \emph{ULV} \){\it decomposition solver for hierarchically semiseparable representations}, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 603-622. · Zbl 1120.65031
[11] S. Chandrasekaran, P. Dewilde, M. Gu, and N. Somasunderam, {\it On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs}, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2261-2290. · Zbl 1209.65032
[12] T. A. Davis and Y. Hu, {\it University of Florida Sparse Matrix Collection}, http://www.cise.ufl.edu/research/sparse/matrices/index.html.
[13] I. S. Duff and J. K. Reid, {\it The multifrontal solution of indefinite sparse symmetric linear equations}, ACM Trans. Math. Software, 9 (1983), pp. 302-325. · Zbl 0515.65022
[14] J. George, {\it Nested dissection of a regular finite element mesh}, SIAM J. Numer. Anal., 10 (1973), pp. 345-363. · Zbl 0259.65087
[15] J. R. Gilbert and S.-H. Teng, {\it MESHPART, A Matlab Mesh Partitioning and Graph Separator Toolbox}, http://www.cerfacs.fr/algor/Softs/MESHPART/.
[16] A. Gillman, P. Young, and P. G. Martinsson, {\it A direct solver with }\(O(N)\){\it complexity for integral equations on one-dimensional domains}, Front. Math. China, 7 (2012), pp. 217-247. · Zbl 1262.65198
[17] L. Grasedyck, R. Kriemann, and S. Le Borne, {\it Domain-decomposition based }\( \mathcal{H} \){\it -LU preconditioners}, in Domain Decomposition Methods in Science and Engineering XVI, Lecture Notes in Computational Sci. Eng. 55, O. B. Widlund and D. E. Keyes, eds., Springer, Berlin, 2007, pp. 661-668.
[18] L. Grasedyck, R. Kriemann, and S. Le Borne, {\it Domain decomposition based }\( \mathcal{H} \){\it -LU preconditioning}, Numer. Math., 112 (2009), pp. 565-600. · Zbl 1178.65140
[19] L. Greengard and V. Rokhlin, {\it A fast algorithm for particle simulations}, J. Comput. Phys., 73 (1987), pp. 325-348. · Zbl 0629.65005
[20] W. Hackbusch, B. N. Khoromskij, and R. Kriemann, {\it Hierarchical matrices based on a weak admissibility criterion}, Computing, 73 (2004), pp. 207-243. · Zbl 1063.65035
[21] W. Hackbusch, B. N. Khoromskij, and S. Sauter, {\it On }\( \mathcal{H}^2 \){\it -matrices}, in Lectures on Applied Mathematics, Springer, Berlin, 2000, pp. 9-29. · Zbl 0963.65043
[22] S. Le Borne, \( \mathcal{H} \){\it -FAINV: Hierarchically Factored Approximate Inverse Preconditioners}, private communication. · Zbl 1388.65027
[23] S. Li, S. Ahmed, G. Klimeck, and E. Darve, {\it Computing entries of the inverse of a sparse matrix using the FIND algorithm}, J. Comput. Phys., 227 (2008), pp. 9408-9427. · Zbl 1214.82124
[24] S. Li and E. Darve, {\it Extension and optimization of the FIND algorithm: Computing Green’s and less-than Green’s functions}, J. Comput. Phys., 231 (2012), pp. 1121-1139. · Zbl 1239.65027
[25] L. Lin, J. Lu, L. Ying, R. Car, and W. E, {\it Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems}, Commun. Math. Sci. 7 (2009), pp. 755-777. · Zbl 1182.65072
[26] L. Lin, C. Yang, J. Lu, L. Ying, and W. E, {\it A fast parallel algorithm for selected inversion of structured sparse matrices with application to \(2\) D electronic structure calculations}, SIAM J. Sci. Comput., 33 (2011), pp. 1329-1351. · Zbl 1230.65039
[27] L. Lin, C. Yang, J. Meza, J. Lu, L. Ying, and W. E, {\it SelInv-An algorithm for selected inversion of a sparse symmetric matrix}, ACM Trans. Math. Software, 37 (2011), 40. · Zbl 1365.65069
[28] W. Lyons, {\it Fast Algorithms with Applications to PDEs}, Ph.D. thesis, University of California Santa Barbara, Santa Barbara, CA, 2005.
[29] P. G. Martinsson, {\it A fast direct solver for a class of elliptic partial differential equations}, J. Sci. Comput., 3, 2009, pp. 316-330. · Zbl 1203.65066
[30] METIS, {\it Family of Graph and Hypergraph Partitioning Software Applications}, .
[31] P. Schmitz and L. Ying, {\it A fast direct solver for elliptic problems on general meshes in 2D}, J. Comput. Phys., 231 (2012), pp. 1314-1338. · Zbl 1408.65022
[32] K. Takahashi, J. Fagan, and M. Chin, {\it Formation of a sparse bus impedance matrix and its application to short circuit study}, Proceedings 8th Power Industry Computer Applications Conference, Minneapolis, MN, 1973, IEEE, New York, 1973.
[33] J. Tang and Y. Saad, {\it A Probing Method for Computing the Diagonal of a Matrix Inverse}, Numer. Linear Algegra Appl., 19 (2012), pp. 485-501. · Zbl 1274.65132
[34] J. M. Tang and Y. Saad, {\it Domain-decomposition-type methods for computing the diagonal of a matrix inverse}, SIAM J. Sci. Comput., 33 (2011), pp. 2823-2847. · Zbl 1232.65048
[35] R. B. Sidje and Y. Saad, {\it Rational Approximation to the Fermi-Dirac Function with Applications in Density Functional Theory}, Numer. Algorithms, 56 (2011), pp. 455-479. · Zbl 1211.65026
[36] S. Wang, M. V. de Hoop, J. Xia, and X. S. Li, {\it Massively parallel structured multifrontal solver for time-harmonic elastic waves in 3D anisotropic media}, Geophys. J. Int., 191 (2012), pp. 346-366.
[37] Y. Xi, J. Xia, S. Cauley, and V. Balakrishnan, {\it Superfast and stable structured solvers for Toeplitz least squares via randomized sampling}, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 44-72. · Zbl 1300.65018
[38] J. Xia, {\it On the complexity of some hierarchical structured matrix algorithms}, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 388-410. · Zbl 1250.65050
[39] J. Xia, {\it Efficient structured multifrontal factorization for general large sparse matrices}, SIAM J. Sci. Comput., 35 (2013), pp. A832-A860. · Zbl 1266.15022
[40] J. Xia, {\it Randomized sparse direct solvers}, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 197-227. · Zbl 1269.65029
[41] J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li, {\it Superfast multifrontal method for large structured linear systems of equations}, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1382-1411. · Zbl 1195.65031
[42] J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li, {\it Fast algorithms for hierarchically semiseparable matrices}, Numer. Linear Algebra Appl., 17 (2010), pp. 953-976. · Zbl 1240.65087
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.