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.
Recently, so-called have attracted a lot of attention. To name few references: @cite_2 @cite_24 @cite_4 @cite_25 @cite_9 . As a subclass of such solvers, @math direct solvers @cite_15 @cite_13 @cite_27 have been introduced. These solvers compute approximate sparse LU-like factorization of HSS-matrices. The simplicity of the structure in comparison to the general @math structure allows for a very efficient implementation, and despite the fact that these matrices are essentially 1D- @math matrices and optimal linear complexity is not possible for the matrices that are discretization of 2D 3D PDEs the running times can be quite impressive.
@cite_4 @cite_9 @cite_24 @cite_27 @cite_2 @cite_15 @cite_13 @cite_25
1712535590 1252747413 2141719776 2127144731
This article presents a fast solver for the dense "frontal" matrices that arise from the multifrontal sparse elimination process of 3D elliptic PDEs. The solver relies on the fact that these matrices can be efficiently represented as a hierarchically off-diagonal low-rank (HODLR) matrix. To construct the low-rank approximation of the off-diagonal blocks, we propose a new pseudo-skeleton scheme, the boundary distance low-rank approximation, that picks rows and columns based on the location of their corresponding vertices in the sparse matrix graph. We compare this new low-rank approximation method to the adaptive cross approximation (ACA) algorithm and show that it achieves better speedup specially for unstructured meshes. Using the HODLR direct solver as a preconditioner (with a low tolerance) to the GMRES iterative scheme, we can reach machine accuracy much faster than a conventional LU solver. Numerical benchmarks are provided for frontal matrices arising from 3D finite element problems corresponding to a wide range of applications. This paper presents a fast direct solver for 3D discretized linear systems using the supernodal multifrontal method together with low-rank approximations. For linear systems arising from certain partial differential equations (PDEs) such as elliptic equations, during the Gaussian elimination of the matrices with Nested Dissection ordering, the fill-in of L and U factors loses its sparsity and contains dense blocks with low-rank property. Off-diagonal blocks can be efficiently approximated with low-rank matrices; diagonal blocks approximated with semiseparable structures called hierarchically semiseparable (HSS) representations. Matrix operations in the multifrontal method are performed in low-rank arithmetic. We present efficient way to organize the HSS structured operations along the elimination. To compress dense blocks into low-rank or HSS structures, we use effective cross approximation (CA) approach. We also use idea of adaptive balancing between robust arithmetic for computing the small dense blocks and low-rank matrix operations for handling with compressed ones while performing the Gaussian elimination. This new proposed solver can be essentially parallelized both on architecture with shared and distributed memory and can be used as effective preconditioner. To check efficient of our solver we compare it with Intel MKL PARDISO - the high performance direct solver. Memory and performance tests demonstrate up to 3 times performance and memory gain for the 3D problems with more than (10^6 ) unknowns. Therefore, proposed multifrontal HSS solver can solve large problems, which cannot be resolved by direct solvers because of large memory consumptions. In this paper we present a fast direct solver for certain classes of dense structured linear systems that works by first converting the given dense system to a larger system of block sparse equations and then uses standard sparse direct solvers. The kind of matrix structures that we consider are induced by numerical low rank in the off-diagonal blocks of the matrix and are related to the structures exploited by the fast multipole method (FMM) of Greengard and Rokhlin. The special structure that we exploit in this paper is captured by what we term the hierarchically semiseparable (HSS) representation of a matrix. Numerical experiments indicate that the method is probably backward stable. 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 Gray T3D parallel computer. Through our analysis and experimental results, we demonstrate that our algorithms substantially improve the state of the art in parallel direct solution of sparse linear systems-both in terms of scalability and overall performance. It is a well known fact that dense matrix factorization scales well and can be implemented efficiently on parallel computers. In this paper, we present the first algorithms to factor a wide class of sparse matrices (including those arising from two- and three-dimensional finite element problems) that are asymptotically as scalable as dense matrix factorization algorithms on a variety of parallel architectures. Our algorithms incur less communication overhead and are more scalable than any previously known parallel formulation of sparse matrix factorization. Although, in this paper, we discuss Cholesky factorization of symmetric positive definite matrices, the algorithms can be adapted for solving sparse linear least squares problems and for Gaussian elimination of diagonally dominant matrices that are almost symmetric in structure. An implementation of one of our sparse Cholesky factorization algorithms delivers up to 20 GFlops on a Gray T3D for medium-size structural engineering and linear programming problems. To the best of our knowledge, this is the highest performance ever obtained for sparse Cholesky factorization on any supercomputer.