In this paper, we consider the matrices approximated in H2 format. The direct solution, as well as the preconditioning, of systems with such matrices is a challenging problem. We propose a non-extensive sparse factorization of the H2 matrix that allows to substitute the direct H2 solution with the solution of the system with an equivalent sparse matrix of the same size. The sparse factorization is constructed out of parameters of the H2 matrix. In the numerical experiments, we show the consistency of this approach in comparison to the other approximate block low-rank hierarchical solvers, such as HODLR, H2Lib and IFMM.
Hierarchical low-rank matrix formats such as @math royalblue @cite_15 @cite_8 @cite_19 @cite_4 , HODLR @cite_11 @cite_13 royalblue (Hierarchical Off-Diagonal Low-Rank) , HSS @cite_7 @cite_1 @cite_20 royalblue (Hierarchically Semiseparable) , @cite_19 @cite_22 matrices and etc., that are matrix analogies of the fast multipole method @cite_0 @cite_10 , have two significant features: they do store information in data-sparse formats and they provide the fast matrix by vector product. Fast ( @math , where @math is size of the matrix) matrix by vector product allows to apply iterative solvers. Data-sparse representation allows to store matrix in @math cells of memory, but storage scheme is usually complicated.
@cite_4 @cite_22 @cite_7 @cite_8 @cite_10 @cite_1 @cite_0 @cite_19 @cite_15 @cite_13 @cite_20 @cite_11
2075490698 2141719776 1712535590 2964186186
In this paper we develop a fast direct solver for large discretized linear systems using the supernodal multifrontal method together with low-rank approximations. For linear systems arising from certain partial differential equations such as elliptic equations, during the Gaussian elimination of the matrices with proper ordering, the fill-in has a low-rank property: all off-diagonal blocks have small numerical ranks with proper definition of off-diagonal blocks. Matrices with this low-rank property can be efficiently approximated with semiseparable structures called hierarchically semiseparable (HSS) representations. We reveal the above low-rank property by ordering the variables with nested dissection and eliminating them with the multifrontal method. All matrix operations in the multifrontal method are performed in HSS forms. We present efficient ways to organize the HSS structured operations along the elimination. Some fast HSS matrix operations using tree structures are proposed. This new structured multifrontal method has nearly linear complexity and a linear storage requirement. Thus, we call it a superfast multifrontal method. It is especially suitable for large sparse problems and also has natural adaptability to parallel computations and great potential to provide effective preconditioners. Numerical results demonstrate the efficiency. 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. 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. A combination of hierarchical tree-like data structures and data access patterns from fast multipole methods and hierarchical low-rank approximation of linear operators from H-matrix methods appears to form an algorithmic path forward for efficient implementation of many linear algebraic operations of scientific computing at the exascale. The combination provides asymptotically optimal computational and communication complexity and applicability to large classes of operators that commonly arise in scientific computing applications. A convergence of the mathematical theories of the fast multipole and H-matrix methods has been underway for over a decade. We recap this mathematical unification and describe implementation aspects of a hybrid of these two compelling hierarchical algorithms on hierarchical distributed-shared memory architectures, which are likely to be the first to reach the exascale. We present a new communication complexity estimate for fast multipole methods on such architectures. We also show how the data structures and access patterns of H-matrices for low-rank operators map onto those of fast multipole, leading to an algebraically generalized form of fast multipole that compromises none of its architecturally ideal properties.