research-article

Block Sparse Cholesky Algorithms on Advanced Uniprocessor Computers

Authors:

Barry W. PeytonAuthors Info & Claims

SIAM Journal on Scientific Computing, Volume 14, Issue 5

Pages 1034 - 1056

https://doi.org/10.1137/0914063

Published: 01 September 1993 Publication History

Abstract

As with many other linear algebra algorithms, devising a portable implementation of sparse Cholesky factorization that performs well on the broad range of computer architectures currently available is a formidable challenge. Even after limiting the attention to machines with only one processor, as has been done in this paper, there are still several interesting issues to consider. For dense matrices, it is well known that block factorization algorithms are the best means of achieving this goal. This approach is taken for sparse factorization as well.

This paper has two primary goals. First, two sparse Cholesky factorization algorithms, the multifrontal method and a blocked left-looking sparse Cholesky method, are examined in a systematic and consistent fashion, both to illustrate the strengths of the blocking techniques in general and to obtain a fair evaluation of the two approaches, Second, the impact of various implementation techniques on time and storage efficiency is assessed, paying particularly close attention to the work-storage requirement of the two methods and their variants.

References

[1]

P. Amestoy, I. Duff, Vectorization of a multiprocessor multifrontal code, Internat. J. Supercomput. Appl., 3 (1989), 41–59

Digital Library

[2]

E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. D. Croz, A. Greenbaum, S. Hammarling, A. McKenney, D. Sorensen, LAPACKA portable linear algebra library for high-performance computers, Proceedings of Supercomputing '90,, IEEE Press, 1990, 1–10

[3]

C. Ashcraff, A vector implementation of the multifrontal method for large sparse, symmetric positive definite linear systems, Tech. Report, ETA-TR-51, Engineering Technology Applications Division, Boeing Computer Services, Seattle, WA, 1987

[4]

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

[5]

C. Ashcraff, 1991, Personal communication

[6]

C. Ashcraft, S. Eisenstat, J. Liu, A. Sherman, A comparison of three column-based distributed sparse factorization schemes, Tech. Report, YALEU/DCS/RR-810, Department of Computer Science, Yale University, New Haven, CT, 1990

[7]

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

Digital Library

[8]

E. Chu, A. George, J. W.-H. Liu, E. G.-Y. Ng, User's guide for SPARSPAK-A: Waterloo sparse linear equations package, Tech. Report, CS-84-36, University of Waterloo, Waterloo, Ontario, Canada, 1984

[9]

A. Dave, I. Duff, Sparse matrix calculations on the CRAY- 2, Parallel Comput., 5 (1987), 55–64

[10]

J. Dongarra, S. Eisenstat, Squeezing the most out of an algorithm in CRAY FORTRAN, ACM Trans. Math. Software, 10 (1984), 219–230

Digital Library

[11]

J. Dongarra, F. Gustavson, A. Karp, Implementing linear algebra algorithms for dense matrices on a vector pipeline machine, SIAM Rev., 26 (1984), 91–112

Digital Library

[12]

I. Duff, A. Erisman, J. K. Reid, Direct Methods for Sparse Matrices, Oxford University Press, Oxford, England, 1987

Digital Library

[13]

I. Duff, R. Grimes, J. Lewis, Sparse matrix test problems, ACM Trans. Math. Software, 15 (1989), 1–14

Digital Library

[14]

I. Duff, J. Reid, MA27—A set of Fortran subroutines for solving sparse symmetric sets of linear equations, Tech. Report, AERE R 10533, Harwell, England, 1982

[15]

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

Digital Library

[16]

S. Eisenstat, M. Gursky, M. Schultz, A. H. Sherman, The Yale sparse matrix package I.the symmetric codes, Internat. J. Numer. Methods Engrg., 18 (1982), 1145–1151

[17]

A. George, M. Heath, J. W.-H. Liu, E. G.-Y. Ng, Solution of sparse positive definite systems on a shared-memory multiprocessor, Internat. J. Parallel Programming, 15 (1986), 309–325

Digital Library

[18]

A. George, M. Heath, J. W.-H. Liu, E. G.-Y. Ng, Sparse Cholesky factorization on a local-memory multiprocessor, SIAM J. Sci. Statist. Comput., 9 (1988), 327–340

Digital Library

[19]

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

Digital Library

[20]

Laurie Hulbert, Earl Zmijewski, Limiting communication in parallel sparse Cholesky factorization, SIAM J. Sci. Statist. Comput., 12 (1991), 1184–1197

Digital Library

[21]

J. W.-H. Liu, A compact row storage scheme for Cholesky factors using elimination trees, ACM Trans. Math. Software, 12 (1986), 127–148

Digital Library

[22]

J. W.-H. Liu, On the storage requirement in the out-of-core multifrontal method for sparse factorization, ACM Trans. Math. Software, 12 (1986), 249–264

Digital Library

[23]

J. W.-H. Liu, The multifrontal method and paging in sparse Cholesky factorization, ACM Trans. Math. Software, 15 (1989), 310–325

Digital Library

[24]

J. W.-H. Liu, The multifrontal method for sparse matrix solution: theory and practice, SIAM Rev., 34 (1992), 82–109

Digital Library

[25]

J. W.-H. Liu, A generalized envelope method for sparse factorization by rows, ACM Trans. Math. Software, 17 (1991), 112–129

Digital Library

[26]

E. G. Ng, B. Peyton, A supernodal Cholesky factorization algorithm for shared-memory multiprocessors, SIAM J. Sci. Comput., 14 (1993), 761–769

Digital Library

[27]

E. Rothberg, A. Gupta, A comparative evaluation of nodal and supernodal parallel sparse matrix factorization: Detailed simulation results, Tech. Report, STAN-CS-90-1305, Stanford University, Stanford, CA, 1990

[28]

E. Rothberg, A. Gupta, An evaluation of left-looking right-looking and multifrontal approaches to sparse Cholesky factorization on hierarchical-memory machines, Tech. Report, STAN-CS-91-1377, Stanford University, Stanford, CA, 1991

[29]

E. Rothberg, A. Gupta, Fast sparse matrix factorization on modem workstations—exploiting the memory hierarchy, ACM Trans. Math. Software, 17 (1991), 313–334

Digital Library

[30]

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

Digital Library

[31]

A. Sherman, On the efficient solution of sparse systems of linearand nonlinear equations, Tech. Report, 46, Department of Computer Science, Yale University, New Haven, CT, 1975

[32]

C. Yang, A vector/parallel implementation of the multifrontal method for sparse symmetric definite linear systems on the Cray Y-MP, 1990, Cray Research Inc., Mendota Heights, MN, manuscript

Cited By

Zhou WChen Y(2024)A mixed cell compressed sparse row for time domain boundary element method in elastodynamicsAdvances in Engineering Software10.1016/j.advengsoft.2024.103633192:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.advengsoft.2024.103633
Gilbert JLi XNg EPeyton B(2022)Computing Row and Column Counts for Sparse QR and LU FactorizationBIT10.1023/A:102194390202541:4(693-710)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1023/A%3A1021943902025
Jacquelin MLin LJia WZhao YYang C(2018)A Left-Looking Selected Inversion Algorithm and Task Parallelism on Shared Memory SystemsProceedings of the International Conference on High Performance Computing in Asia-Pacific Region10.1145/3149457.3149472(54-63)Online publication date: 28-Jan-2018
https://dl.acm.org/doi/10.1145/3149457.3149472
Show More Cited By

Index Terms

Block Sparse Cholesky Algorithms on Advanced Uniprocessor Computers

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

Recommendations

A Supernodal Cholesky Factorization Algorithm for Shared-Memory Multiprocessors

This paper presents a parallel sparse Cholesky factorization algorithm for shared-memory MIMD multiprocessors. The algorithm is particularly well suited for vector supercomputers with multiple processors, such as the Cray Y-MP. The new algorithm is a ...
Row Modifications of a Sparse Cholesky Factorization

Given a sparse, symmetric positive definite matrix C and an associated sparse Cholesky factorization LDL$\tr$, we develop sparse techniques for updating the factorization after a symmetric modification of a row and column of C. We show how the ...
Highly Scalable Parallel Algorithms for Sparse Matrix Factorization

In this paper, we describe scalable parallel algorithms for symmetric sparse matrix factorization, analyze their performance and scalability, and present experimental results for up to 1,024 processors on a Cray T3D parallel computer. Through our ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Scientific Computing

SIAM Journal on Scientific Computing Volume 14, Issue 5

Sep 1993

245 pages

ISSN:1064-8275

Issue’s Table of Contents

Copyright © 1993 Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 September 1993

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou WChen Y(2024)A mixed cell compressed sparse row for time domain boundary element method in elastodynamicsAdvances in Engineering Software10.1016/j.advengsoft.2024.103633192:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.advengsoft.2024.103633
Gilbert JLi XNg EPeyton B(2022)Computing Row and Column Counts for Sparse QR and LU FactorizationBIT10.1023/A:102194390202541:4(693-710)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1023/A%3A1021943902025
Jacquelin MLin LJia WZhao YYang C(2018)A Left-Looking Selected Inversion Algorithm and Task Parallelism on Shared Memory SystemsProceedings of the International Conference on High Performance Computing in Asia-Pacific Region10.1145/3149457.3149472(54-63)Online publication date: 28-Jan-2018
https://dl.acm.org/doi/10.1145/3149457.3149472
Yang Y(2018)Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programmingNumerical Algorithms10.1007/s11075-018-0469-379:3(957-992)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1007/s11075-018-0469-3
Yang Y(2017)CurveLP-A MATLAB implementation of an infeasible interior-point algorithm for linear programmingNumerical Algorithms10.1007/s11075-016-0180-174:4(967-996)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s11075-016-0180-1
Furrer RBachoc FDu J(2016)Asymptotic properties of multivariate tapering for estimation and predictionJournal of Multivariate Analysis10.1016/j.jmva.2016.04.006149:C(177-191)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.jmva.2016.04.006
Lebedev SAkhmedzhanov DKozinov EMeyerov IPirova ASysoyev A(2015)Dynamic Parallelization Strategies for Multifrontal Sparse Cholesky FactorizationProceedings of the 13th International Conference on Parallel Computing Technologies - Volume 925110.1007/978-3-319-21909-7_7(68-79)Online publication date: 31-Aug-2015
https://dl.acm.org/doi/10.1007/978-3-319-21909-7_7
Avron HGupta AHollingsworth J(2012)Managing data-movement for effective shared-memory parallelization of out-of-core sparse solversProceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis10.5555/2388996.2389134(1-11)Online publication date: 10-Nov-2012
https://dl.acm.org/doi/10.5555/2388996.2389134
Davis THu Y(2011)The university of Florida sparse matrix collectionACM Transactions on Mathematical Software10.1145/2049662.204966338:1(1-25)Online publication date: 7-Dec-2011
https://dl.acm.org/doi/10.1145/2049662.2049663
Lin LYang CMeza JLu JYing LE W(2011)SelInv---An Algorithm for Selected Inversion of a Sparse Symmetric MatrixACM Transactions on Mathematical Software10.1145/1916461.191646437:4(1-19)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1145/1916461.1916464
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