We propose a new approximate factorization for solving linear systems with symmetric positive definite sparse matrices. In a nutshell the algorithm is to apply hierarchically block Gaussian elimination and additionally compress the fill-in. The systems that have efficient compression of the fill-in mostly arise from discretization of partial differential equations. We show that the resulting factorization can be used as an efficient preconditioner and compare the proposed approach with state-of-art direct and iterative solvers.
The main difference between CE-algorithm and the classical direct sparse LU-like solvers royalblue (e.g. block Gaussian elimination @cite_23 , multifrontal method @cite_18 and others @cite_19 @cite_20 @cite_29 @cite_16 ) is that in our algorithm fill-in growth is controlled while maintaining the accuracy, thanks to the additional compression procedure. This leads to big advantage in memory usage and probably makes CE-algorithm asymptotically faster, but this point requires additional analysis. Note that references @cite_18 and @cite_16 use compressed representations (i.e. they are not just using the graph structure of the matrix, as is the case for the other solvers).
@cite_18 @cite_29 @cite_19 @cite_23 @cite_16 @cite_20
2089024363 2051917325 76288046 1008564288 2094542090
CHOLMOD is a set of routines for factorizing sparse symmetric positive definite matrices of the form A or AAT, updating downdating a sparse Cholesky factorization, solving linear systems, updating downdating the solution to the triangular system Lx = b, and many other sparse matrix functions for both symmetric and unsymmetric matrices. Its supernodal Cholesky factorization relies on LAPACK and the Level-3 BLAS, and obtains a substantial fraction of the peak performance of the BLAS. Both real and complex matrices are supported. CHOLMOD is written in ANSI ISO C, with both C and MATLABTM interfaces. It appears in MATLAB 7.2 as x = A when A is sparse symmetric positive definite, as well as in several other sparse matrix functions. An ANSI C code for sparse LU factorization is presented that combines a column pre-ordering strategy with a right-looking unsymmetric-pattern multifrontal numerical factorization. The pre-ordering and symbolic analysis phase computes an upper bound on fill-in, work, and memory usage during the subsequent numerical factorization. User-callable routines are provided for ordering and analyzing a sparse matrix, computing the numerical factorization, solving a system with the LU factors, transposing and permuting a sparse matrix, and converting between sparse matrix representations. The simple user interface shields the user from the details of the complex sparse factorization data structures by returning simple handles to opaque objects. Additional user-callable routines are provided for printing and extracting the contents of these opaque objects. An even simpler way to use the package is through its MATLAB interface. UMFPACK is incorporated as a built-in operator in MATLAB 6.5 as x = Abb when A is sparse and unsymmetric. Abstract Fast direct methods incorporating marching techniques are considered from the viewpoint of sparse Gaussian elimination. It is shown that the algorithms correspond to the nonstandard block backsolution of particular LU decompositions. Direct factorization methods for the solution of large, sparse linear systems that arise from PDE discretizations are robust, but typically show poor time and memory scalability for large systems. In this paper, we describe an efficient sparse, rank-structured Cholesky algorithm for solution of the positive definite linear system @math when @math comes from a discretized partial-differential equation. Our approach combines the efficient memory access patterns of conventional supernodal Cholesky algorithms with the memory efficiency of rank-structured direct solvers. For several test problems arising from PDE discretizations, our method takes less memory than standard sparse Cholesky solvers and less wall-clock time than standard preconditioned iterations. 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 straightforward parallelization of the left-looking supernodal sparse Cholesky factorization algorithm. Like its sequential predecessor, it improves performance by reducing indirect addressing and memory traffic. Experimental results on a Cray Y-MP demonstrate the effectiveness of the new algorithm. On eight processors of a Cray Y-MP, the new routine performs the factorization at rates exceeding one Gflop for several test problems from the Harwell–Boeing sparse matrix collection.