The design and implementation of a new out-of-core sparse cholesky factorization method
ACM Transactions on Mathematical SoftwarePublished 1 March 2004
Vladimir Rotkin, Sivan Toledo
Citations66
SJR quartileQ1
SJR score1.23
SNIP2.12
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new out-of-core sparse Cholesky factorization method that uses the elimination tree to partition the matrix, an advanced subtree-scheduling algorithm, and both right-looking and left-looking updates is described.
Abstract
We describe a new out-of-core sparse Cholesky factorization method. The new method uses the elimination tree to partition the matrix, an advanced subtree-scheduling algorithm, and both right-looking and left-looking updates. The implementation of the new method is efficient and robust. On a 2 GHz personal computer with 768 MB of main memory, the code can easily factor matrices with factors of up to 48 GB, usually at rates above 1 Gflop/s. For example, the code can factor audikw, currenly the largest matrix in any matrix collection (factor size over 10 GB), in a little over an hour, and can factor a matrix whose graph is a 140-by-140-by-140 mesh in about 12 hours (factor size around 27 GB).
Keywords
Computer ScienceEngineering
SIAM Journal on Scientific ComputingA Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
5,588 Citations1998George Karypis, Vipin Kumar
This work presents a new coarsening heuristic (called heavy-edge heuristic) for which the size of the partition of the coarse graph is within a small factor of theSize of the final partition obtained after multilevel refinement, and presents a much faster variation of the Kernighan--Lin (KL) algorithm for refining during uncoarsening.
SIAM Journal on Matrix Analysis and ApplicationsA Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling
2,236 Citations2001Patrick Amestoy, Iain Duff +2 more
The main features and the tuning of the algorithms for the direct solution of sparse linear systems on distributed memory computers developed in the context of a long term European research project are analyzed and discussed.
Direct Methods for Sparse Matrices
1,612 Citations2017Iain Duff, A. M. Erisman +1 more
This book aims to be suitable also for a student course, probably at MSc level, and the subject is intensely practical and this book is written with practicalities ever in mind.
ACM Transactions on Mathematical SoftwareThe Multifrontal Solution of Indefinite Sparse Symmetric Linear
923 Citations1983Iain Duff, John Reid
On etend la methode frontale pour resoudre des systemes lineaires d'equations en permettant a plus d'un front d'apparaitre en meme temps.
Computer Methods in Applied Mechanics and EngineeringMultifrontal parallel distributed symmetric and unsymmetric solvers
917 Citations2000Patrick Amestoy, I. S. Duff +1 more
A new parallel distributed memory multifrontal approach with dynamic scheduling of the computing tasks has been developed to handle numerical pivoting efficiently and performance analysis shows the efficiency and the potential of the method.
Conference on High Performance Computing (Supercomputing)Automatically Tuned Linear Algebra Software
878 Citations1998R. Clint Whaley, Jack Dongarra
SIAM Journal on Matrix Analysis and ApplicationsAn Approximate Minimum Degree Ordering Algorithm
718 Citations1996Patrick Amestoy, Timothy A. Davis +1 more
An approximate minimum degree (AMD) ordering algorithm for preordering a symmetric sparse matrix prior to numerical factorization is presented and produces results that are comparable in quality with the best orderings from other minimum degree algorithms.
SIAM Journal on Numerical AnalysisGeneralized Nested Dissection
549 Citations1979Richard J. Lipton, Donald J. Rose +1 more
It is shown that sparse Gaussian elimination is efficient for any class of graphs which have good separator, and conversely that graphs without good separators are not amenable to sparse GaRussian elimination.
SIAM Journal on Matrix Analysis and ApplicationsThe Role of Elimination Trees in Sparse Factorization
518 Citations1990Joseph W. H. Liu
The role of elimination trees in the direct solution of large sparse linear systems is examined and its relation to sparse Cholesky factorization is discussed.
SIAM ReviewThe Multifrontal Method for Sparse Matrix Solution: Theory and Practice
420 Citations1992Joseph W. H. Liu
An overview of the multifrontal method for the solution of large sparse symmetric positive definite linear systems, formulated in terms of frontal matrices, update matrices, and an assembly tree, which has proved to be extremely valuable.
SIAM Journal on Scientific ComputingBlock Sparse Cholesky Algorithms on Advanced Uniprocessor Computers
207 Citations1993Esmond Ng, Barry W. Peyton
Two sparse Cholesky factorization algorithms 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.
ACM Transactions on Mathematical SoftwareA New Implementation of Sparse Gaussian Elimination
195 Citations1982Robert Schreiber
An implementation of sparse ${LDL}^T$ and LU factorization and back-substitution, based on a new scheme for storing sparse matrices, is presented and appears to be as efficient in terms of work and storage as existing schemes.
SIAM Journal on Matrix Analysis and ApplicationsLocality of Reference in LU Decomposition with Partial Pivoting
157 Citations1997Sivan Toledo
Experimental comparisons show that an implementation of the new algorithm outperforms a similarly coded right-looking algorithm on six different RISC architectures, that the new algorithms performs fewer cache misses than any other algorithm tested, and that it benefits more from Strassen's matrix-multiplication algorithm.
ACM Transactions on Mathematical SoftwareThe influence of relaxed supernode partitions on the multifrontal method
116 Citations1989Cleve Ashcraft, Roger G. Grimes
An algorithm for partitioning the nodes of a graph into supernodes is presented, which improves the performance of the multifrontal method for the factorization of large, sparse matrices on vector computers, and factorizes the extremely sparse electric power matrices faster than the general sparse algorithm.
SIAM Journal on Numerical AnalysisComplexity Bounds for Regular Finite Difference and Finite Element Grids
115 Citations1973Alan J. Hoffman, Michael Martin +1 more
Sharp lower bounds are obtained for multiplications and storage in the sparse system arising from the application of finite difference or finite element techniques to linear boundary value problems on plane regions yielding regular $n \times n$ grids.
ACM Transactions on Mathematical SoftwareOn the storage requirement in the out-of-core multifrontal method for sparse factorization
109 Citations1986Joseph W. H. Liu
Two techniques are introduced to reduce the working storage requirement for the recent multifrontal method of Duff and Reid used in the sparse out-of-core factorization of symmetric matrices.
The design and implementation of SOLAR, a portable library for scalable out-of-core linear algebra computations
91 Citations1996Sivan Toledo, Fred G. Gustavson
It is expected that the combination of portability, modularity, and the use of a high-level 110 interface will make the library an important platfonn for research on out-of-core algorithms and on parallel 110.
SIAM Journal on Matrix Analysis and ApplicationsOn Finding Supernodes for Sparse Matrix Computations
88 Citations1993Joseph W. H. Liu, Esmond Ng +1 more
A simple characterization of fundamental supernodes is given in terms of the row subtrees of sparse Cholesky factors in the elimination tree and an efficient algorithm is presented that determines the set of suchsupernodes in time proportional to the number of nonzeros and equations in the original matrix.
ACM Transactions on Mathematical SoftwareEfficient sparse matrix factorization on high performance workstations—exploiting the memory hierarchy
50 Citations1991Edward Rothberg, Anoop Gupta
This paper considers the problem of Cholesky factorization of a large sparse positive definite system of equations on a high-performance workstation and finds that the major factor limiting performance is the cost of moving data between memory and the processor.
Journal of Computational PhysicsVery Large Electronic Structure Calculations Using an Out-of-Core Filter-Diagonalization Method
50 Citations2002Sivan Toledo, Eran Rabani
SIAM Journal on Scientific ComputingEfficient Methods for Out-of-Core Sparse Cholesky Factorization
36 Citations1999Edward Rothberg, Robert Schreiber
This work considers the problem of sparse Cholesky factorization with limited main memory and finds that a left-looking method that nevertheless uses the multifrontal algorithm for portions of the matrix (subtrees of the supernodal elimination tree whose multifrontal stack fits in memory) is very effective.
HAL (Le Centre pour la Communication Scientifique Directe)MUltifrontal Massively Parallel Solver (MUMPS Version 4.3) Users' guide
30 Citations2003Patrick Amestoy, Iain Duff +2 more
Out-of-Core SVD and QR Decompositions.
29 Citations2001Eran Rabani, Sivan Toledo
The out-of-core singular-value-decomposition algorithm for tall narrow matrices that are too large to fit in main memory and are stored on disks is implemented and combined with a larger eigensolver code to obtain the electronic states of a semiconductor nanocrystal.
SIAM Journal on Scientific and Statistical ComputingSolution of Large-Scale Sparse Least Squares Problems Using Auxiliary Storage
24 Citations1981John A. George, Michael T. Heath +1 more
This paper describes a method for solving very large sparse linear least squares problems on a typical (large) computer and provides the results of some experiments illustrating the effectiveness of this approach.
SIAM Journal on Scientific and Statistical ComputingAuxiliary Storage Methods for Solving Finite Element Systems
19 Citations1985Alan D. George, Hamza Rashwan
This paper considers the direct solution of the system of linear equations $Ax = b$ where A is a large, sparse, symmetric and positive definite matrix, and considers an improvement for the basic strategy which reduces the I/O traffic to the extent that it is dominated by writing the Cholesky factor alone.
SIAM Journal on Scientific and Statistical ComputingAn Adaptive General Sparse Out-Of-Core Cholesky Factorization Scheme
15 Citations1987Joseph W. H. Liu
Experimental results on some large sparse practical problems are provided; they show significant reduction in storage requirement for Cholesky factors with little increase (and sometimes decrease) in execution time.
Parallel ComputingA large scale, sparse, secondary storage, direct linear equation solver for structural analysis and its implementation on vector and parallel architectures
14 Citations1987Petter E. Bjørstad
The linear equation solver in the analysis part of SESAM is described, which is well suited for vector and parallel processing and uses substructure techniques at the highest level.
High-Performance Out-of-Core Sparse LU Factorization.
14 Citations1999John R. Gilbert, Sivan Toledo
An out-of-core sparse nonsymmetric LU -factorization algorithm with partial pivoting that can easily factor matrices whose factors are larger than main memory at rates comparable to those of an in-core solver.