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.
The factorization approach is more popular for hierarchical matrices with strong low-rank structure, also known as hierarchical matrices with weak-admissibility criteria royalblue @cite_25 ( @math royalblue @cite_15 @cite_8 , HODLR royalblue @cite_11 @cite_13 , HSS royalblue @cite_7 @cite_1 @cite_20 matrices). royalblue For the @math matrix, the algorithm @math -LU @cite_6 with almost linear complexity was proposed. This algorithm has been successfully applied to many problems. The major drawback of the @math -LU algorithm is that factorization time and memory required for @math and @math factors can be quite large. Approximate direct solvers based on factorization of HSS and HODLR matrices are royalblue also well studied royalblue and found many @cite_20 @cite_17 @cite_21 @cite_3 @cite_9 @cite_13 @cite_7 successful applications .
@cite_7 @cite_8 @cite_9 @cite_21 @cite_1 @cite_17 @cite_6 @cite_3 @cite_15 @cite_13 @cite_25 @cite_20 @cite_11
1712535590 1983103429 1252747413 2075490698
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. Randomized sampling has recently been proven a highly efficient technique for computing approximate factorizations of matrices that have low numerical rank. This paper describes an extension of such techniques to a wider class of matrices that are not themselves rank-deficient but have off-diagonal blocks that are; specifically, the class of so-called hierarchically semiseparable (HSS) matrices. HSS matrices arise frequently in numerical analysis and signal processing, particularly in the construction of fast methods for solving differential and integral equations numerically. The HSS structure admits algebraic operations (matrix-vector multiplications, matrix factorizations, matrix inversion, etc.) to be performed very rapidly, but only once the HSS representation of the matrix has been constructed. How to rapidly compute this representation in the first place is much less well understood. The present paper demonstrates that if an @math matrix can be applied to a vector in @math time, and if individual entries of the matrix can be computed rapidly, then provided that an HSS representation of the matrix exists, it can be constructed in @math operations, where @math is an upper bound for the numerical rank of the off-diagonal blocks. The point is that when legacy codes (based on, e.g., the fast multipole method) can be used for the fast matrix-vector multiply, the proposed algorithm can be used to obtain the HSS representation of the matrix, and then well-established techniques for HSS matrices can be used to invert or factor the matrix. 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 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.