Cited By
View all- Fialko S(2022)Parallel finite element solver PARFES for the structural analysis in NUMA architectureAdvances in Engineering Software10.1016/j.advengsoft.2022.103290174:COnline publication date: 1-Dec-2022
On Computing Inverse Entries of a Sparse Matrix in an Out-of-Core Environment
Authors: 
Patrick R. Amestoy, Iain S. Duff, Jean-Yves L'Excellent, Yves Robert, François-Henry Rouet, Bora UçarAuthors Info & Claims
Pages A1975 - A1999
Abstract
The inverse of an irreducible sparse matrix is structurally full, so that it is impractical to think of computing or storing it. However, there are several applications where a subset of the entries of the inverse is required. Given a factorization of the sparse matrix held in out-of-core storage, we show how to compute such a subset efficiently, by accessing only parts of the factors. When there are many inverse entries to compute, we need to guarantee that the overall computation scheme has reasonable memory requirements, while minimizing the volume of communication (data transferred) between disk and main memory. This leads to a partitioning problem that we prove is NP-complete. We also show that we cannot get a close approximation to the optimal solution in polynomial time. We thus need to develop heuristic algorithms, and we propose (i) a lower bound on the cost of an optimum solution; (ii) an exact algorithm for a particular case; (iii) two other heuristics for a more general case; and (iv) hypergraph partitioning models for the most general setting. We compare the proposed algorithms and illustrate the performance of our algorithms in practice using the \textttMUMPS software package on a set of real-life problems.
References
[1]
E. Agullo, On the Out-of-Core Factorization of Large Sparse Matrices, Ph.D. thesis, Ecole Normale Supérieure de Lyon, 2008.
[2]
P. R. Amestoy, I. S. Duff, A. Guermouche, and \relax Tz. Slavova, Analysis of the solution phase of a parallel multifrontal approach, Parallel Comput., 36 (2010), pp. 3--15.
[3]
P. R. Amestoy, I. S. Duff, J. Koster, and J.-Y. L'Excellent, A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 15--41.
[4]
P. R. Amestoy, I. S. Duff, Y. Robert, F.-H. Rouet, and B. Ucar, On Computing Inverse Entries of a Sparse Matrix in an Out-of-Core Environment, Technical report RT-APO-10-06, INPT-IRIT, 2010.
[5]
P. R. Amestoy, A. Guermouche, J.-Y. L'Excellent, and S. Pralet, Hybrid scheduling for the parallel solution of linear systems, Parallel Comput., 32 (2006), pp. 136--156.
[6]
C. Aykanat, A. Pinar, and Ü. V. Çatalyürek, Permuting sparse rectangular matrices into block-diagonal form, SIAM J. Sci. Comput., 25 (2004), pp. 1860--1879.
[7]
C. Bekas, A. Curioni, and I. Fedulova, Low cost high performance uncertainty quantification, in Proceedings of the 2nd Workshop on High Performance Computational Finance, ACM, 2009, p. 8.
[8]
\AA. Björck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, 1996.
[9]
L. Bouchet, J.-P. Roques, P. Mandrou, A. Strong, R. Diehl, F. Lebrun, and R. Terrier, INTEGRAL SPI observation of the galactic central radian: Contribution of discrete sources and implication for the diffuse emission 1, Astrophys. J., 635 (2005), pp. 1103--1115.
[10]
Y. E. Campbell and T. A. Davis, Computing the Sparse Inverse Subset: An Inverse Multifrontal Approach, Technical report TR-95-021, CIS Department, University of Florida, 1995.
[11]
S. Cauley, J. Jain, C. K. Koh, and V. Balakrishnan, A scalable distributed method for quantum-scale device simulation, J. Appl. Phys., 101 (2007), p. 123715.
[12]
Ü. V. Çatalyürek and C. Aykanat, Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication, IEEE Trans. Parallel Distrib. Syst., 10 (1999), pp. 673--693.
[13]
Ü. V. Çatalyürek and C. Aykanat, PaToH: A Multilevel Hypergraph Partitioning Tool, Version 3.0, Department of Computer Engineering, Bilkent University, Ankara, Turkey, 1999; also available online from http://bmi.os u.edu/˜umit/software.htm.
[14]
E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), pp. 201--213.
[15]
I. S. Duff, A. M. Erisman, C. W. Gear, and J. K. Reid, Sparsity structure and Gaussian elimination, SIGNUM Newsletter, 23 (1988), pp. 2--8.
[16]
A. M. Erisman and W. F. Tinney, On computing certain elements of the inverse of a sparse matrix, Commun. ACM, 18 (1975), pp. 177--179.
[17]
M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, 1979.
[18]
G. A. Geist and E. G. Ng, Task scheduling for parallel sparse Cholesky factorization, Int. J. Parallel Program., 18 (1989), pp. 291--314.
[19]
J. R. Gilbert and J. W. H. Liu, Elimination structures for unsymmetric sparse LU factors, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 334--352.
[20]
J. R. Gilbert, G. L. Miller, and S.-H. Teng, Geometric mesh partitioning: Implementation and experiments, SIAM J. Sci. Comput., 19 (1998), pp. 2091--2110.
[21]
G. Karypis and V. Kumar, MeTiS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version 4.0, Army HPC Research Center, University of Minnesota, Minneapolis, 1998.
[22]
T. Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, John Wiley & Sons, New York, 1990.
[23]
S. Li, S. Ahmed, G. Klimeck, and E. Darve, Computing entries of the inverse of a sparse matrix using the find algorithm, J. Comput. Phys., 227 (2008), pp. 9408--9427.
[24]
S. Li and E. Darve, Optimization of the find algorithm to compute the inverse of a sparse matrix, in IWCE'09 13th International Workshop on Computational Electronics, IEEE, 2009, pp. 1--4.
[25]
L. Lin, J. Lu, L. Ying, R. Car, and W. E, Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems, Comm. Math. Sci., 7 (2009), pp. 755--777.
[26]
J. W. H. Liu, The role of elimination trees in sparse factorization, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 134--172.
[27]
M. Luisier, A. Schenk, W. Fichtner, and G. Klimeck, Atomistic simulation of nanowires in the $sp^{3} d^{5} s^{*}$ tight-binding formalism: From boundary conditions to strain calculations, Phys. Rev. B, 74 (2006), 205323.
[28]
H. Niessner and K. Reichert, On computing the inverse of a sparse matrix, Internat. J. Numer. Methods Engrg., 19 (1983), pp. 1513--1526.
[29]
R. Schreiber, A new implementation of sparse Gaussian elimination, ACM Trans. Math. Software, 8 (1982), pp. 256--276.
[30]
\relax Tz. Slavova, Parallel Triangular Solution in an Out-of-Core Multifrontal Approach for Solving Large Sparse Linear Systems, Ph.D. thesis, Institut National Polytechnique de Toulouse, 2009.
[31]
K. Takahashi, J. Fagan, and M. Chin, Formation of a sparse bus impedance matrix and its application to short circuit study, in Proceedings of the 8th PICA Conference, Minneapolis, 1973.
[32]
J. Tang and Y. Saad, A Probing Method for Computing the Diagonal of the Matrix Inverse, Technical report umsi-2010-42, Minnesota Supercomputer Institute, University of Minnesota, Minneapolis, 2009.
[33]
B. Uçar and C. Aykanat, Encapsulating multiple communication-cost metrics in partitioning sparse rectangular matrices for parallel matrix-vector multiplies, SIAM J. Sci. Comput., 25 (2004), pp. 1837--1859.
[34]
B. Uçar and C. Aykanat, Revisiting hypergraph models for sparse matrix partitioning, SIAM Rev., 49 (2007), pp. 595--603.
[35]
I. Yamazaki, X. S. Li, and E. G. Ng, Partitioning, load balancing, and matrix ordering in a parallel hybrid solver, presented at SIAM Conference on Parallel Processing for Scientific Computing, 2010.
[36]
I. Yamazaki, X. S. Li, F. H. Rouet, and B. Uçar, Combinatorial problems in a parallel hybrid linear solver, presented at SIAM Workshop on Combinatorial Scientific Computing, Darmstadt, Germany, 2011.
Recommendations
A sparse-sparse iteration for computing a sparse incomplete factorization of the inverse of an SPD matrix
In this paper, a method via sparse-sparse iteration for computing a sparse incomplete factorization of the inverse of a symmetric positive definite matrix is proposed. The resulting factorized sparse approximate inverse is used as a preconditioner for ...
The design and use of a sparse direct solver for skew symmetric matrices
We consider the LDL^T factorization of sparse skew symmetric matrices. We see that the pivoting strategies are similar, but simpler, to those used in the factorization of sparse symmetric indefinite matrices, and we briefly describe the algorithms used ...
Permuting Sparse Rectangular Matrices into Block-Diagonal Form
We investigate the problem of permuting a sparse rectangular matrix into block-diagonal form. Block-diagonal form of a matrix grants an inherent parallelism for solving the deriving problem, as recently investigated in the context of mathematical ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© 2012, Society for Industrial and Applied Mathematics.
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 01 January 2012
Author Tags
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Jan 2025
Other Metrics
Citations
Cited By
View all- Fialko S(2022)Parallel finite element solver PARFES for the structural analysis in NUMA architectureAdvances in Engineering Software10.1016/j.advengsoft.2022.103290174:COnline publication date: 1-Dec-2022