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 give a short introduction to methods for the data-sparse approximation of matrices resulting from the discretisation of non-local operators occurring in boundary integral methods, as the inverses of partial differential operators or as solutions of control problems. The result of the approximation will be so-called hierarchical matrices (or short H-matrices). These matrices form a subset of the set of all matrices and have a data-sparse representation. The essential operations for these matrices (matrix-vector and matrix – matrix multiplication, addition and inversion) can be performed in, up to logarithmic factors, optimal complexity. We give a review of specialised variants of H-matrices, especially of H 2 -matrices, and finally consider applications of the different methods to problems from integral equations, partial differential equations and control theory. q 2003 Elsevier Science Ltd. All rights reserved.  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. An algorithm is presented for the rapid evaluation of the potential and force fields in systems involving large numbers of particles whose interactions are Coulombic or gravitational in nature. For a system ofNparticles, an amount of work of the orderO(N2) has traditionally been required to evaluate all pairwise interactions, unless some approximation or truncation method is used. The algorithm of the present paper requires an amount of work proportional toNto evaluate all interactions to within roundoff error, making it considerably more practical for large-scale problems encountered in plasma physics, fluid dynamics, molecular dynamics, and celestial mechanics. 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.   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.  