In this paper matrix compression techniques in the context of wavelet Galerkin schemes for boundary integral equations are developed and analyzed that exhibit optimal complexity in the following sense. The fully discrete scheme produces approximate solutions within discretization error accuracy offered by the underlying Galerkin method at a computational expense that is proven to stay proportional to the number of unknowns. Key issues are the second compression, that reduces the near field complexity significantly, and an additional a-posteriori compression. The latter one is based on a general result concerning an optimal work balance, that applies, in particular, to the quadrature used to compute the compressed stiffness matrix with sufficient accuracy in linear time. The theoretical results are illustrated by a 3D example on a nontrivial domain.

The boundary concentrated finite element method is a variant of the hp-version of the finite element method that is particularly suited for the numerical treatment of elliptic boundary value problems with smooth coefficients and low regularity boundary conditions. For this method we present two multilevel preconditioners that lead to preconditioned stiffness matrices with condition numbers that are bounded uniformly in the problem size N. The cost of applying the preconditioners is O(N). Numerical examples illustrate the efficiency of the algorithms.

Introduction In recent years, domain decomposition methods have been used extensively to efficiently solve boundary value problems for partial differential equations in complex{form domains. On the other hand, multilevel techniques on hierarchical data structures also have developed into an effective tool for the construction and analysis of fast solvers. But direct realization of multilevel techniques on a parallel computer system for the global problem in the original domain involves difficult communication problems. I this paper, we present and analyze a combination of these two approaches: domain decomposition and multilevel decomposition on hierarchical structures to design optimal preconditioning operators.

In this paper matrix compression techniques in the context of wavelet Galerkin schemes for boundary integral equations are developed and analyzed that exhibit optimal complexity in the following sense. The fully discrete scheme produces approximate solutions within discretization error accuracy offered by the underlying Galerkin method at a computational expense that is proven to stay proportional to the number of unknowns. Key issues are the second compression, that reduces the near field complexity significantly, and an additional a-posteriori compression. The latter one is based on a general result concerning an optimal work balance, that applies, in particular, to the quadrature used to compute the compressed stiffness matrix with sufficient accuracy in linear time. The theoretical results are illustrated by a 3D example on a nontrivial domain.

The boundary concentrated finite element method is a variant of the hp-version of the finite element method that is particularly suited for the numerical treatment of elliptic boundary value problems with smooth coefficients and low regularity boundary conditions. For this method we present two multilevel preconditioners that lead to preconditioned stiffness matrices with condition numbers that are bounded uniformly in the problem size N. The cost of applying the preconditioners is O(N). Numerical examples illustrate the efficiency of the algorithms.