research-article

Highly Parallel Sparse Cholesky Factorization

Authors:

John R. Gilbert,

Robert SchreiberAuthors Info & Claims

SIAM Journal on Scientific and Statistical Computing, Volume 13, Issue 5

Pages 1151 - 1172

https://doi.org/10.1137/0913067

Published: 01 September 1992 Publication History

Abstract

This paper develops and compares several fine-grained parallel algorithms to compute the Cholesky factorization of a sparse matrix. The experimental implementations are on the Connection Machine, a distributed-memory SIMD machine whose programming model conceptually supplies one processor per data element. In contrast to special-purpose algorithms in which the matrix structure conforms to the connection structure of the machine, this paper focuses on matrices with arbitrary sparsity structure.

The most promising alternative is a supernodal, multifrontal algorithm whose inner loop performs several dense factorizations simultaneously on a two-dimensional grid of processors. The key subroutine is a fine-grained parallel, dense-factorization algorithm. The sparse code attains execution rates comparable to those of the dense subroutine. Although at present architectural limitations prevent the dense factorization from realizing its potential efficiency, it is concluded that a regular data parallel architecture can be used efficiently to solve arbitrarily structured sparse problems.

A performance model is also presented and used to analyze these algorithms. Asymptotic analysis combined with experimental measurement of parameters is accurate enough to be useful in choosing among alternative algorithms for a complicated problem.

References

[1]

C. Ashcraft, R. Grimes, J. Lewis, B. Peyton, H. Simon, Recent progress in sparse matrix methods for large linear systems, Internat. J. Supercomput. Appl., (1987), 10–30

[2]

C. C. Ashcraft, The domain/segment partition for the factorization of sparse symmetric positive definite matrices, ECA-TR-148, Tech. Report, Boeing Computer Services, Engineering, Computing and Analysis Division, Seattle, WA, 1990

[3]

C. H. Bischof, J. J. Dongarra, A project for developing a linear algebra library for high-performance computers, Tech. Report, MCS-P105-0989, Argonne National Laboratory, Argonne, IL, 1989

[4]

J. R. S. Blair, B. W. Peyton, On finding minimum-diameter clique trees, Tech. Report, ORNL/TM-11850, Oak Ridge National Laboratory, Oak Ridge, TN, 1991

[5]

M. Dixon, J. de Kleer, Massively parallel assumption-based truth maintenance, Proc. Nat. Conf. Artificial Intelligence, ACM, New York, 1988, 199–204

[6]

I. S. Duff, Multiprocessing a sparse matrix code on the Alliant FX/8, Tech. Report, CSS 210, Computer Science and Systems Division, AERE Harwell, Oxfordshire, U.K., 1988

[7]

I. S. Duff, J. K. Reid, The multifrontal solution of indefinite sparse symmetric linear equations, ACM Trans. Math. Software, 9 (1983), 302–325

Digital Library

[8]

A. Feldmann, J. Sgall, S.-H. Teng, Dynamic scheduling on parallel machines32nd Annual Symposium on Foundations of Computer Science (San Juan, PR, 1991), IEEE Comput. Soc. Press, Los Alamitos, CA, 1991, 111–120

[9]

Michael R. Garey, David S. Johnson, Computers and intractability, W. H. Freeman and Co., San Francisco, Calif., 1979x+338, A Guide to the Theory of NP-Completeness

Digital Library

[10]

F. Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. Comput., 1 (1972), 180–187

Digital Library

[11]

Alan George, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal., 10 (1973), 345–363

Digital Library

[12]

Alan George, Michael T. Heath, Joseph Liu, Esmond Ng, Sparse Cholesky factorization on a local-memory multiprocessor, SIAM J. Sci. Statist. Comput., 9 (1988), 327–340

Digital Library

[13]

Alan George, Joseph W. H. Liu, Computer solution of large sparse positive definite systems, Prentice-Hall Inc., Englewood Cliffs, N.J., 1981xii+324

Digital Library

[14]

Alan George, Esmond Ng, On the complexity of sparse $QR$ and $LU$ factorization of finite-element matrices, SIAM J. Sci. Statist. Comput., 9 (1988), 849–861

Digital Library

[15]

J. A. George, D. McIntyre, On the application of the minimum degree algorithm to finite element systems, SIAM J. Numer. Anal., 15 (1978), 90–112

Digital Library

[16]

John Russell Gilbert, Some nested dissection order is nearly optimal, Inform. Process. Lett., 26 (1988), 325–328

Digital Library

[17]

J. R. Gilbert, H. Hafsteinsson, Parallel solution of sparse linear systemsSWAT 88 (Halmstad, 1988), Lecture Notes in Comput. Sci., Vol. 318, Springer, Berlin, 1988, 145–153

[18]

J. R. Gilbert, C. Lewis, R. Schreiber, Parallel preordering for sparse matrix factorization, in preparation

[19]

Ching-Tien Ho, S. Lennart Johnsson, Spanning balanced trees in Boolean cubes, SIAM J. Sci. Statist. Comput., 10 (1989), 607–630

Digital Library

[20]

J. J. Hopfield, Neural networks and physical systems with emergent collective computational abilities, Proc. Nat. Acad. Sci. U.S.A., 79 (1982), 2554–2558

[21]

Jochen A. G. Jess, H. G. M. Kees, A data structure for parallel $L/U$ decomposition, IEEE Trans. Comput., 31 (1982), 231–239

Digital Library

[22]

S. G. Kratzer, Massively parallel sparse matrix computations, Tech. Report, SRC-TR-90-008, Supercomputer Research Center, Bowie, MD, 1990

[23]

J. W. H. Liu, The multifrontal method for sparse matrix solution: Theory and practice, Tech. Report, CS-90-04, Computer Science Department, York University, York, England, 1990

[24]

Joseph W. H. Liu, The role of elimination trees in sparse factorization, SIAM J. Matrix Anal. Appl., 11 (1990), 134–172

Digital Library

[25]

J. Naor, M. Naor, A. J. Schäffer, Fast parallel algorithms for chordal graphs, SIAM J. Comput., 18 (1989), 327–349

Digital Library

[26]

B. W. Peyton, Ph.D. Thesis, Some Applications of Clique Trees to the Solution of Sparse Linear Systems, Clemson University, Clemson, SC, 1986

[27]

Donald J. Rose, R. C. Read, A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equationsGraph theory and computing, Academic Press, New York, 1972, 183–217

[28]

Donald J. Rose, R. Endre Tarjan, George S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5 (1976), 266–283

Digital Library

[29]

E. Rothberg, A. Gupta, Fast sparse matrix factorization on modern workstations, Tech. Report, STAN-CS-89-1286, Stanford University, Stanford, CA, 1989

[30]

Robert Schreiber, A new implementation of sparse Gaussian elimination, ACM Trans. Math. Software, 8 (1982), 256–276

Digital Library

[31]

R. Schreiber, H. Simon, An assessment of the connection machineScientific Applications of the Connection Machine, World Scientific, Singapore, 1991

[32]

H. Simon, P. Vu, C. Yang, Performance of a supernodal general sparse solver on the Cray Y-MP, Tech. Report, SCA-TR-117, Boeing Computer Services, Seattle, WA, 1989

[33]

B. Speelpenning, The generalized element method, Tech. Report, UIUCDCS-R-78-946, University of Illinois, Urbana, IL, 1978

[34]

Paris reference manual, version 5.0, Cambridge, MA, 1988

[35]

E. Zmijewski, Ph.D. Thesis, Sparse Cholesky Factorization on a Multiprocessor, Cornell University, Ithaca, NY, 1987

Cited By

Mohammadi MYuki TCheshmi KDavis EHall MDehnavi MNandy POlschanowsky CVenkat AStrout MMcKinley KFisher K(2019)Sparse computation data dependence simplification for efficient compiler-generated inspectorsProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314646(594-609)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314646
Cheshmi KKamil SStrout MDehnavi M(2018)ParSyProceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis10.5555/3291656.3291739(1-15)Online publication date: 11-Nov-2018
https://dl.acm.org/doi/10.5555/3291656.3291739
Cheshmi KKamil SStrout MDehnavi M(2018)ParSyProceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis10.1109/SC.2018.00065(1-15)Online publication date: 11-Nov-2018
https://dl.acm.org/doi/10.1109/SC.2018.00065
Show More Cited By

Index Terms

Highly Parallel Sparse Cholesky Factorization

Index terms have been assigned to the content through auto-classification.

Recommendations

Efficient Sparse Cholesky Factorization on a Massively Parallel SIMD Computer

We investigate the effect of load balancing when performing Cholesky factorization on a massively parallel SIMD computer. In particular we describe a supernodal algorithm for performing sparse Cholesky factorization. The way the matrix is mapped onto the ...
Exactly Solving Sparse Rational Linear Systems via Roundoff-Error-Free Cholesky Factorizations

Exactly solving sparse symmetric positive definite (SPD) linear systems is a key problem in mathematics, engineering, and computer science. This paper derives two new sparse roundoff-error-free (REF) Cholesky factorization algorithms which exactly solve ...
Efficient Structured Multifrontal Factorization for General Large Sparse Matrices

Rank structures provide an opportunity to develop new efficient numerical methods for practical problems, when the off-diagonal blocks of certain dense intermediate matrices have small (numerical) ranks. In this work, we present a framework of structured ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Scientific and Statistical Computing

SIAM Journal on Scientific and Statistical Computing Volume 13, Issue 5

Sep 1992

226 pages

ISSN:0196-5204

Issue’s Table of Contents

Copyright © 1992 Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 September 1992

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mohammadi MYuki TCheshmi KDavis EHall MDehnavi MNandy POlschanowsky CVenkat AStrout MMcKinley KFisher K(2019)Sparse computation data dependence simplification for efficient compiler-generated inspectorsProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314646(594-609)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314646
Cheshmi KKamil SStrout MDehnavi M(2018)ParSyProceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis10.5555/3291656.3291739(1-15)Online publication date: 11-Nov-2018
https://dl.acm.org/doi/10.5555/3291656.3291739
Cheshmi KKamil SStrout MDehnavi M(2018)ParSyProceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis10.1109/SC.2018.00065(1-15)Online publication date: 11-Nov-2018
https://dl.acm.org/doi/10.1109/SC.2018.00065
Pingali KNguyen DKulkarni MBurtscher MHassaan MKaleem RLee TLenharth AManevich RMéndez-Lojo MPrountzos DSui XHall MPadua D(2011)The tao of parallelism in algorithmsProceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/1993498.1993501(12-25)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/1993498.1993501
Pingali KNguyen DKulkarni MBurtscher MHassaan MKaleem RLee TLenharth AManevich RMéndez-Lojo MPrountzos DSui X(2011)The tao of parallelism in algorithmsACM SIGPLAN Notices10.1145/1993316.199350146:6(12-25)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/1993316.1993501
Emiris IPan V(2010)Applications of FFT and structured matricesAlgorithms and theory of computation handbook10.5555/1882757.1882775(18-18)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.5555/1882757.1882775
Emiris IPan VTsigaridas E(2010)Algebraic and numerical algorithmsAlgorithms and theory of computation handbook10.5555/1882757.1882774(17-17)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.5555/1882757.1882774
Pan VMurphy BRosholt RTabanjeh MWatt SVerschelde J(2007)The schur aggregation for solving linear systems of equationsProceedings of the 2007 international workshop on Symbolic-numeric computation10.1145/1277500.1277522(142-151)Online publication date: 25-Jul-2007
https://dl.acm.org/doi/10.1145/1277500.1277522
Aleksandrov LDjidjev HGuo HMaheshwari A(2007)Partitioning planar graphs with costs and weightsACM Journal of Experimental Algorithmics10.1145/1187436.121058811(1.5-es)Online publication date: 9-Feb-2007
https://dl.acm.org/doi/10.1145/1187436.1210588
Lin W(2003)Finding Optimal Ordering of Sparse Matrices for Column-Oriented Parallel Cholesky FactorizationThe Journal of Supercomputing10.1023/A:102203283010524:3(259-277)Online publication date: 1-Mar-2003
https://dl.acm.org/doi/10.1023/A%3A1022032830105
Show More Cited By

View Options

View options

Get Access

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 Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents