Data-sparse Approximation by Adaptive ℋ2-Matrices

A class of matrices (ℋ²-matrices) has recently been introduced for storing discretisations of elliptic problems and integral operators from the BEM. These matrices 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 linear complexity. (iii) In general, sums and products of these matrices are no longer in the same set, but after truncation to the ℋ²-matrix format these operations are again of quasi-linear complexity. We introduce the basic ideas of ℋ- and ℋ²-matrices and present an algorithm that adaptively computes approximations of general matrices in the latter format. Received April 17, 2002 Published online: July 26, 2002     

Solution of Large Scale Algebraic Matrix Riccati Equations by Use of Hierarchical Matrices

In previous papers, a class of hierarchical matrices (ℋ-matrices) is introduced which are data-sparse and allow an approximate matrix arithmetic of almost optimal complexity. Here, we investigate a new approach to exploit the ℋ-matrix structure for the solution of large scale Lyapunov and Riccati equations as they typically arise for optimal control problems where the constraint is a partial differential equation of elliptic type. This approach leads to an algorithm of linear-logarithmic complexity in the size of the matrices. Received July 30, 2002; revised December 16, 2002 Published online: April 22, 2003     

Adaptive Low-Rank Approximation of Collocation Matrices

This article deals with the solution of integral equations using collocation methods with almost linear complexity. Methods such as fast multipole, panel clustering and ℋ-matrix methods gain their efficiency from approximating the kernel function. The proposed algorithm which uses the ℋ-matrix format, in contrast, is purely algebraic and relies on a small part of the collocation matrix for its blockwise approximation by low-rank matrices. Furthermore, a new algorithm for matrix partitioning that significantly reduces the number of blocks generated is presented. Received August 15, 2002; revised September 20, 2002 Published online: March 6, 2003     

-Matrix Arithmetics in Linear Complexity

For hierarchical matrices, approximations of the matrix-matrix sum and product can be computed in almost linear complexity, and using these matrix operations it is possible to construct the matrix inverse, efficient preconditioners based on approximate factorizations or solutions of certain matrix equations. -matrices are a variant of hierarchical matrices which allow us to perform certain operations, like the matrix-vector product, in ``true' linear complexity, but until now it was not clear whether matrix arithmetic operations could also reach this, in some sense optimal, complexity. We present algorithms that compute the best-approximation of the sum and product of two -matrices in a prescribed -matrix format, and we prove that these computations can be accomplished in linear complexity. Numerical experiments demonstrate that the new algorithms are more efficient than the well-known methods for hierarchical matrices.     

Hierarchical Matrices Based on a Weak Admissibility Criterion

In preceding papers [8], [11], [12], [6], a class of matrices (-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 -matrix format. A coarser format yields smaller constants in the work and storage estimates and thus leads to a lower complexity of the -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 -matrix format allows to analyse the accuracy of the -matrix inversion and multiplication.     

Adaptive Recompression of -Matrices for BEM

The efficient treatment of dense matrices arising, e.g., from the finite element discretisation of integral operators requires special compression techniques. In this article, we use a hierarchical low-rank approximation, the so-called -matrix, that approximates the dense stiffness matrix in admissible blocks (corresponding to subdomains where the underlying kernel function is smooth) by low rank matrices. The low rank matrices are assembled by the ACA+ algorithm, an improved variant of the well-known ACA method. We present an algorithm that can determine a coarser block structure that minimises the storage requirements (enhanced compression) and speeds up the arithmetic (e.g., inversion) in the -matrix format. This coarse approximation is done adaptively and on-the-fly to a given accuracy such that the matrix is assembled with minimal storage requirements while keeping the desired approximation quality. The benefits of this new recompression technique are demonstrated by numerical examples.     

Construction and Arithmetics of <Emphasis Type="Italic">H</Emphasis>-Matrices

In previous papers hierarchical matrices were introduced which are data-sparse and allow an approximate matrix arithmetic of nearly optimal complexity. In this paper we analyse the complexity (storage, addition, multiplication and inversion) of the hierarchical matrix arithmetics. Two criteria, the sparsity and idempotency, are sufficient to give the desired bounds. For standard finite element and boundary element applications we present a construction of the hierarchical matrix format for which we can give explicit bounds for the sparsity and idempotency.     

Computing Interpolation Weights in AMG Based on Multilevel Schur Complements

This paper presents a particular construction of neighborhood matrices to be used in the computation of the interpolation weights in AMG (algebraic multigrid). The method utilizes the existence of simple interpolation matrices (piecewise constant for example) on a hierarchy of coarse spaces (grids). Then one constructs by algebraic means graded away coarse spaces for any given fine-grid neighborhood. Next, the corresponding stiffness matrix is computed on this graded away mesh, and the actual neighborhood matrix is obtained by computing the multilevel Schur complement of this matrix where degrees of freedom outside the neighborhood have to be eliminated. The paper presents algorithmic details, provides model complexity analysis as well as some comparative tests of the quality of the resulting interpolation based on the multilevel Schur complements versus element interpolation based on the true element matrices.     

Incomplete Cross Approximation in the Mosaic-Skeleton Method

The mosaic-skeleton method was bred in a simple observation that rather large blocks in very large matrices coming from integral formulations can be approximated accurately by a sum of just few rank-one matrices (skeletons). These blocks might correspond to a region where the kernel is smooth enough, and anyway it can be a region where the kernel is approximated by a short sum of separable functions (functional skeletons). Since the effect of approximations is like that of having small-rank matrices, we find it pertinent to say about mosaic ranks of a matrix which turn out to be pretty small for many nonsingular matrices. On the first stage, the method builds up an appropriate mosaic partitioning using the concept of a tree of clusters and some extra information rather than the matrix entries (related to the mesh). On the second stage, it approximates every allowed block by skeletons using the entries of some rather small cross which is chosen by an adaptive procedure. We focus chiefly on some aspects of practical implementation and numerical examples on which the approximation time was found to grow almost linearly in the matrix size. Received February 13, 1999; revised October 26, 1999     

ℋ-matrices for Convection-diffusion Problems with Constant Convection

L ^∞-coefficients. This paper analyses the application of hierarchical matrices to the convection-dominant convection-diffusion equation with constant convection. In the case of increasing convection, the convergence of a standard ℋ-matrix approximant towards the original matrix will deteriorate. We derive a modified partitioning and admissibility condition that ensures good convergence also for the singularly perturbed case. Received January 1, 2003; revised March 4, 2003 Published online: May 2, 2003     

Energy Optimization of Algebraic Multigrid Bases

We propose a fast iterative method to optimize coarse basis functions in algebraic multigrid by minimizing the sum of their energies, subject to the condition that linear combinations of the basis functions equal to given zero energy modes, and subject to restrictions on the supports of the coarse basis functions. For a particular selection of the supports, the first iteration gives exactly the same basis functions as our earlier method using smoothed aggregation. The convergence rate of the minimization algorithm is bounded independently of the mesh size under usual assumptions on finite elements. The construction is presented for scalar problems as well as for linear elasticity. Computational results on difficult industrial problems demonstrate that the use of energy minimal basis functions improves algebraic multigrid performance and yields a more robust multigrid algorithm than smoothed aggregation. Received: March 9, 1998; revised January 25, 1999     

Hierarchical LU Decomposition-based Preconditioners for BEM

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.     

The Eigenvalue Problem for the 2D Laplacian in ℋ-Matrix Arithmetic and Application to the Heat and Wave Equation

A class of matrices (-matrices) has recently been introduced by Hackbusch for approximating large and fully populated matrices arising from FEM and BEM applications. These matrices are data-sparse and allow approximate matrix operations of almost linear complexity. In the present paper, we choose a special class of -matrices that provides a good approximation to the inverse of the discrete 2D Laplacian. For these 2D -matrices we study the blockwise recursive schemes for block triangular linear systems of equations and the Cholesky and LDL^T factorization in an approximate arithmetic of almost linear complexity. Using the LDL^T factorization we compute eigenpairs of the discrete 2D Laplacian in -matrix arithmetic by means of a so-called simultaneous iteration for computing invariant subspaces of non-Hermitian matrices due to Stewart. We apply the -matrix techniques to approximate the solutions of the high-frequency 2D wave equation for smooth initial data and the 2D heat equation for arbitrary initial data by spectral decomposition of the discrete 2D Laplacian in, up to logarithmic factors, optimal complexity.     

On some new approximate factorization methods for block tridiagonal matrices suitable for vector and parallel processors

In this paper, to obtain an efficient parallel algorithm to solve sparse block-tridiagonal linear systems, stair matrices are used to construct some parallel polynomial approximate inverse preconditioners. These preconditioners are suitable when the desired goal is to maximize parallelism. Moreover, some theoretical results concerning these preconditioners are presented and how to construct preconditioners effectively for any nonsingular block tridiagonal H-matrices is also described. In addition, the validity of these preconditioners is illustrated with some numerical experiments arising from the second order elliptic partial differential equations and oil reservoir simulations.     

A Sparse ℋ-Matrix Arithmetic.

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. In the present Part II, the construction of ‹-matrices is explained for FEM and BEM applications in two and three spatial dimensions. The orders of complexity of the various matrix operations are exactly the same as in Part I. In particular, it is shown that the applicability of ‹-matrices does not require a regular mesh. We discuss quasi-uniform unstructured meshes and the case of composed surfaces as well.     

Hierarchical Tensor-Product Approximation to the Inverse and Related Operators for High-Dimensional Elliptic Problems

The class of -matrices allows an approximate matrix arithmetic with almost linear complexity. In the present paper, we apply the -matrix technique combined with the Kronecker tensor-product approximation (cf. [2, 20]) to represent the inverse of a discrete elliptic operator in a hypercube (0, 1)^dd in the case of a high spatial dimension d. In this data-sparse format, we also represent the operator exponential, the fractional power of an elliptic operator as well as the solution operator of the matrix Lyapunov-Sylvester equation. The complexity of our approximations can be estimated by (dn log ^qn), where N=n^d is the discrete problem size.     

Reduction of Smith Normal Form Transformation Matrices

Smith normal form computations are important in group theory, module theory and number theory. We consider the transformation matrices for the Smith normal form over the integers and give a presentation of arbitrary transformation matrices for this normal form. Our main contribution is an algorithm that replaces already computed transformation matrices by others with small entries. We combine methods from lattice basis reduction with a procedure to reduce the sum of the squared entries of both transformation matrices. This algorithm performs well even for matrices of large dimensions.     

Block triangular preconditioners for the discretized time-harmonic Maxwell equations in mixed form

In this paper, we consider the solution of the saddle point linear systems arising from the finite element discretization of the time-harmonic Maxwell equations in mixed form. Two types of block triangular Schur complement-free preconditioners used with Krylov subspace methods are proposed, involving the choice of the parameter. Furthermore, we give the optimal parameter in practice. Theoretical analysis shows that all eigenvalues of the preconditioned matrices are strongly clustered. Finally, numerical experiments that validate the analysis are presented.     

Low-complexity approximate iterative LMMSE detection for large-scale MIMO systems

This paper deals with iterative detection for uplink large-scale MIMO systems. The well-known iterative linear minimum mean squared error (LMMSE) detector requires quadratic complexity (per symbol per iteration) with the number of antennas, which may be a concern in large-scale MIMO. In this work, we develop approximate iterative LMMSE detectors based on transformed system models where the transformation matrices are obtained through channel matrix decompositions. It is shown that, with quasi-linear complexity (per symbol per iteration), the proposed detectors can achieve almost the same performance as the conventional LMMSE detector. It is worth mentioning that the linear transformations are also useful to reduce the complexity of downlink precoding, so the relevant computational complexity can be shared by both uplink and downlink.     

Algebraic Multigrid Based on Computational Molecules, 1: Scalar Elliptic Problems

We consider the problem of splitting a symmetric positive definite (SPD) stiffness matrix A arising from finite element discretization into a sum of edge matrices thereby assuming that A is given as the sum of symmetric positive semidefinite (SPSD) element matrices. We give necessary and sufficient conditions for the existence of an exact splitting into SPSD edge matrices and address the problem of best positive (nonnegative) approximation. Based on this disassembling process we present a new concept of ``strong' and ``weak' connections (edges), which provides a basis for selecting the coarse-grid nodes in algebraic multigrid methods. Furthermore, we examine the utilization of computational molecules (small collections of edge matrices) for deriving interpolation rules. The reproduction of edge matrices on coarse levels offers the opportunity to combine classical coarsening algorithms with effective (energy minimizing) interpolation principles yielding a flexible and robust new variant of AMG.