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.
We describe an algorithm for the direct solution of systems of linear algebraic equations associated with the discretization of boundary integral equations with non-oscillatory kernels in two dimensions. The algorithm is ''fast'' in the sense that its asymptotic complexity is O(n), where n is the number of nodes in the discretization. Unlike previous fast techniques based on iterative solvers, the present algorithm directly constructs a compressed factorization of the inverse of the matrix; thus it is suitable for problems involving relatively ill-conditioned matrices, and is particularly efficient in situations involving multiple right hand sides. The performance of the scheme is illustrated with several numerical examples. rformance of the scheme is illustrated with several numerical examples. ples. The preceding Part I of this paper has introduced a class of matrices (ℋ-matrices) which are data-sparse and allow an approximate matrix arithmetic of almost linear complexity. The matrices discussed in Part I are able to approximate discrete integral operators in the case of one spatial dimension.  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. 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 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. The adaptive cross approximation method can be used to efficiently approximate stiffness matrices arising from boundary element applications by hierarchical matrices. In this article an approximative LU decomposition in the same format is presented which can be used for preconditioning the resulting coefficient matrices efficiently. If the LU decomposition is computed with high precision, it may even be used as a direct yet efficient solver. 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. A class of matrices ( ( H )-matrices) is introduced which have the following properties. (i) They are sparse in the sense that only few data are needed for their representation. (ii) The matrix-vector multiplication is of almost linear complexity. (iii) In general, sums and products of these matrices are no longer in the same set, but their truncations to the ( H )-matrix format are again of almost linear complexity. (iv) The same statement holds for the inverse of an ( H )-matrix. A number of problems in probability and statistics can be addressed using the multivariate normal (Gaussian) distribution. In the one-dimensional case, computing the probability for a given mean and variance simply requires the evaluation of the corresponding Gaussian density. In the @math -dimensional setting, however, it requires the inversion of an @math covariance matrix, @math , as well as the evaluation of its determinant, @math . In many cases, such as regression using Gaussian processes, the covariance matrix is of the form @math , where @math is computed using a specified covariance kernel which depends on the data and additional parameters (hyperparameters). The matrix @math is typically dense, causing standard direct methods for inversion and determinant evaluation to require @math work. This cost is prohibitive for large-scale modeling. Here, we show that for the most commonly used covariance functions, the matrix @math can be hierarchically factored into a product of block low-rank updates of the identity matrix, yielding an @math algorithm for inversion. More importantly, we show that this factorization enables the evaluation of the determinant @math , permitting the direct calculation of probabilities in high dimensions under fairly broad assumptions on the kernel defining @math . Our fast algorithm brings many problems in marginalization and the adaptation of hyperparameters within practical reach using a single CPU core. The combination of nearly optimal scaling in terms of problem size with high-performance computing resources will permit the modeling of previously intractable problems. We illustrate the performance of the scheme on standard covariance kernels. In preceding papers [8], [11], [12], [6], a class of matrices ( Open image in new window -matrices) has been developed which are data-sparse and allow to approximate integral and more general nonlocal operators with almost linear complexity. In the present paper, a weaker admissibility condition is described which leads to a coarser partitioning of the hierarchical Open image in new window -matrix format. A coarser format yields smaller constants in the work and storage estimates and thus leads to a lower complexity of the Open image in new window -matrix arithmetic. On the other hand, it preserves the approximation power which is known in the case of the standard admissibility criterion. Furthermore, the new weak Open image in new window -matrix format allows to analyse the accuracy of the Open image in new window -matrix inversion and multiplication.  