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.

We establish multiresolution norm equivalences in weighted spaces <i>L²_w</i>((0,1)) with possibly singular weight functions <i>w(x)</i>&ge;0 in (0,1). Our analysis exploits the locality of the biorthogonal wavelet basis and its dual basis functions. The discrete norms are sums of wavelet coefficients which are weighted with respect to the collocated weight function <i>w(x)</i> within each scale. Since norm equivalences for Sobolev norms are by now well-known, our result can also be applied to weighted Sobolev norms. We apply our theory to the problem of preconditioning <i>p</i>-Version FEM and wavelet discretizations of degenerate elliptic problems.

As shown by Dahmen, Harbrecht and Schneider, the fully discrete wavelet Galerkin scheme for boundary integral equations scales linearly with the number of unknowns without compromising the accuracy of the underlying Galerkin scheme. The supposition is a wavelet basis with a sufficiently large number of vanishing moments. In this paper we present several constructions of appropriate wavelet bases on manifolds based on the biorthogonal spline wavelets of A. Cohen, I. Daubechies and J.-C. Feauveau. By numerical experiments we demonstrate that it is worthwhile to spent effort on their construction to increase the performance of the wavelet Galerkin scheme considerably.

The present paper is devoted to the fast solution of boundary integral equations on unstructured meshes by the Galerkin scheme. On the given mesh we construct a wavelet basis providing vanishing moments with respect to the traces of polynomials in the space. With this basis at hand, the system matrix in wavelet coordinates can be compressed to $\mathcal{O}(N\log N)$ relevant matrix coefficients, where $N$ denotes the number of unknowns. The compressed system matrix can be computed within suboptimal complexity by using techniques from the fast multipole method or panel clustering. Numerical results prove that we succeeded in developing a fast wavelet Galerkin scheme for solving the considered class of problems.

The present paper is devoted to the fast solution of boundary integral equations on unstructured meshes by the Galerkin scheme. On the given mesh we construct a wavelet basis providing vanishing moments with respect to the traces of polynomials in the space. With this basis at hand, the system matrix in wavelet coordinates can be compressed to $\mathcal{O}(N\log N)$ relevant matrix coefficients, where $N$ denotes the number of unknowns. The compressed system matrix can be computed within suboptimal complexity by using techniques from the fast multipole method or panel clustering. Numerical results prove that we succeeded in developing a fast wavelet Galerkin scheme for solving the considered class of problems.

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.

We establish multiresolution norm equivalences in weighted spaces <i>L²_w</i>((0,1)) with possibly singular weight functions <i>w(x)</i>&ge;0 in (0,1). Our analysis exploits the locality of the biorthogonal wavelet basis and its dual basis functions. The discrete norms are sums of wavelet coefficients which are weighted with respect to the collocated weight function <i>w(x)</i> within each scale. Since norm equivalences for Sobolev norms are by now well-known, our result can also be applied to weighted Sobolev norms. We apply our theory to the problem of preconditioning <i>p</i>-Version FEM and wavelet discretizations of degenerate elliptic problems.

As shown by Dahmen, Harbrecht and Schneider, the fully discrete wavelet Galerkin scheme for boundary integral equations scales linearly with the number of unknowns without compromising the accuracy of the underlying Galerkin scheme. The supposition is a wavelet basis with a sufficiently large number of vanishing moments. In this paper we present several constructions of appropriate wavelet bases on manifolds based on the biorthogonal spline wavelets of A. Cohen, I. Daubechies and J.-C. Feauveau. By numerical experiments we demonstrate that it is worthwhile to spent effort on their construction to increase the performance of the wavelet Galerkin scheme considerably.