Search

The convergence analysis of a special variant of the additive Schwarz iteration is presented. It can be applied to the frequency decomposition multigrid method and yields robust convergence

Many important physical applications are governed by the wave equation. The formulation as time domain boundary integral equations involves retarded potentials. For the numerical solution of this problem, we employ the convolution quadrature method for the discretization in time and the Galerkin boundary element method for the space discretization. We introduce a simple a priori cut-off strategy where small entries of the system matrices are replaced by zero. The threshold for the cut-off is determined by an a priori analysis which will be developed in this paper. This analysis will also allow to estimate the effect of additional perturbations such as panel clustering and numerical integration on the overall discretization error. This method reduces the storage complexity for time domain integral equations from O(M 2 N) to O(M 2 N 1/2 log M), where N denotes the number of time steps and M is the dimension of the boundary element space.

The approximation of the functions 1/x and \(1/\sqrt{x}\) by exponential sums enables us to evaluate some high-dimensional integrals by products of one-dimensional integrals. The degree of approximation can be estimated via the study of rational approximation of the square root function. The latter has interesting connections with the Babylonian method and Gauss’ arithmetic-geometric process.

We present Hartree-Fock surface energies, work functions, and dipole barriers for a Jellium slab model at different electron densities and slab widths. The fully self-consistent calculations take into account the nonlocal exchange coupling of the momentum parallel to the surface with the perpendicular component of the orbitals. Typical oscillations due to quantum-size effects have been observed. Our results provide lower and upper bounds for the Hartree-Fock surface energy and work function of the semi-infinite jellium model which can serve as benchmarks for previously reported variational calculations performed with different types of non-self-consistent orbitals. Furthermore we observed the expected characteristic band structures and electron densities, i.e., vanishing density of states at the Fermi energy and pronounced Friedel oscillations at jellium surfaces. In order to resolve the perpendicular components of the orbitals we have used a wavelet based interpolating scaling function basis.

A large class of multiscale problems are described by partial differential equations with highly oscillatory coefficients. Such coefficients represent the properties of a composite material or the heterogeneity of the medium in the computation of flow in porous media problem. The computation of an accurate discrete solution of such problems requires a very fine discretisation associated with a fine grid Th. For such a fine resolution, the storage and computation costs are very high. From an engineer’s perspective, we are interested in the average behaviour of the elliptic oscillatory operator on a coarse scale taking into account the small scale features without fully resolving them. We intend to provide a smoother elliptic operator which on a coarse mesh behaves like the original operator. As a model problem, let us consider the elliptic boundary value problem on Ω, a bounded Lipschitz domain in R

In this paper we review the technique of hierarchical matrices and put it into the context of black-box solvers for large linear systems. Numerical examples for several classes of problems from medium- to large-scale illustrate the applicability and efficiency of this technique. We compare the results with those of several direct solvers (which typically scale quadratically in the matrix size) as well as an iterative solver (algebraic multigrid) which scales linearly (if it converges in O(1) steps).

Usually, the fast evaluation of a convolution integral f ℝ f(y)g(x−y)dy requires that the functions f, g are discretised on an equidistant grid in order to apply FFT. Here we discuss the efficient performance of the convolution in locally refined grids. More precisely, f and g are assumed to be piecewise linear and the convolution result is projected into the space of linear functions in a given locally refined grid. Under certain conditions, the overall costs are still O(N logN), where N is the sum of the dimensions of the subspaces containing f, g and the resulting function.

In this paper, we will propose a boundary element method for solving classical boundary integral equations on complicated surfaces which, possibly, contain a large number of geometric details or even uncertainties in the given data. The (small) size of such details is characterised by a small parameter $$\varepsilon$$ and the regularity of the solution is expected to be low in such zones on the surface (which we call the wire-basket zones). We will propose the construction of an initial discretisation for such type of problems. Afterwards standard strategies for boundary element discretisations can be applied such as the h, p, and the adaptive hp-version in a straightforward way.For the classical boundary integral equations, we will prove the optimal approximation results of our so-called wire-basket boundary element method and discuss the stability aspects. Then, we construct the panel-clustering and $$\mathcal{H}$$-matrix approximations to the corresponding Galerkin BEM stiffness matrix. The method is shown to have an almost linear complexity with respect to the number of degrees of freedom located on the wire basket.

We consider the wave equation in a time domain boundary integral formulation. To obtain a stable time discretization, we employ the convolution quadrature method in time, developed by Lubich. In space, a Galerkin boundary element method is considered. The resulting Galerkin matrices are fully populated and the computational complexity is proportional to N log2 NM 2, where M is the number of spatial unknowns and N is the number of time steps.

In order to treat multiple energy- and length-scales in electronic structure calculations for extended systems, we have studied a wavelet based multiresolution analysis of electron correlations. Wavelets provide hierarchical basis sets that can be locally adapted to the length- and energy-scales of physical phenomena. The inherently high dimensional many-body problem can be kept tractable by using the sparse grid method for the construction of multivariate wavelets. These so called “hyperbolic” wavelets provide sparse representations for correlated wavefunctions and can be combined with diagrammatic techniques from quantum many-particle theory into a diagrammatic multiresolution analysis. Using sparsity features originating from the hierarchical structure and vanishing moments property of wavelet bases, this leads to many-particle methods with almost linear computational complexity for the treatment of electron correlations.

In population balance equations particle breakage is often described by a Volterra integral operator. Naive discretisation of this operator leads to quadratic complexity. In this paper an efficient numerical treatment for Galerkin discretisation of the integral operator is suggested, based on the idea of H-matrices, which leads to linear complexity.

In this paper, we will present composite boundary elements (CBE) for classical Fredholm boundary integral equations. These new boundary elements allow the low-dimensional discretisation of boundary integral equations where the minimal number of degrees of freedom is independent of the, possibly, huge number of charts which are necessary to describe a complicated surface.The applications are threefold: (a) The coarse-grid discretisation by composite boundary elements allow the use of multigrid algorithms for solving the fine-grid discretisation independently of the number of patches which are necessary to describe the surface. (b) If the accuracy requirements are moderate, the composite boundary elements allow the low-dimensional discretisation of the integral equation. (c) A posteriori error indicators can be applied already to a low-dimensional discretisation, which do not resolve the domain, to obtain a problem-adapted discretisation.

We present a multiscale treatment of electron correlations based on hyperbolic wavelet expansions of Jastrow-type correlation functions. Wavelets provide hierarchical basis sets that can be locally adapted to the length- and energy-scales of physical phenomena. Combined with hyperbolic tensor products and local adaptive refinement near the interelectron cusp, these wavelet bases enable sparse representations of Jastrow factors. The computational efficiency of wavelets in electronic structure calculations is demonstrated within the coupled electron-pair approximation (local ansatz). Based on a diagrammatic multiresolution analysis, we discuss various kinds of sparsity features for matrix elements required by the local ansatz. Sparsity originates from the hierarchical structure and vanishing moments property of wavelet bases. This led us to a recurrence scheme for the evaluation of matrix elements with almost linear computational complexity with respect to the size of the underlying isotropic 3d-wavelet basis. Numerical studies for selected diagrams are presented for a homogeneous electron gas.

The goal of this work is the presentation of some new formats which are useful for the approximation of (large and dense) matrices related to certain classes of functions and nonlocal (integral, integrodifferential) operators, especially for high-dimensional problems. These new formats elaborate on a sum of few terms of Kronecker products of smaller-sized matrices (cf. [34, 35]). In addition to this we need that the Kronecker factors possess a certain data-sparse structure. Depending on the construction of the Kronecker factors we are led to so-called “profile-low-rank matrices” or hierarchical matrices (cf. [17, 18]). We give a proof for the existence of such formats and expound a gainful combination of the Kronecker-tensor-product structure and the arithmetic for hierarchical matrices. AMS Subject Classification: 65F50, 65F30, 65N38, 65N35, 15A09

After discretization of the partial differential equations from mechanics, one usually obtains large systems of (non)linear equations. Their efficient solution requires the use of fast iterative methods. Multigrid iterations are able to solve linear and nonlinear systems with a rather fast rate of convergence, provided the problem is of elliptic type. The contribution describes the basic construction of multigrid methods, their ingredients, related methods, and their application to various problem classes. Although most of the applications concern FEM discretizations of partial differential equations, there are also applications to integral equations as they occur in boundary element methods (BEM). Keywords: multigrid method; two-grid method; nested iteration; systems of linear equations; systems of nonlinear equations; integral equations; eigenvalue problems; FEM; BEM

The panel clustering method and the hierarchical matrix technique described here are important tools for the efficient treatment of fully populated matrices that arise from boundary element (BEM) problems and elliptic FEM problems. Keywords: panel clustering; hierarchical matrices; BEM; fully populated matrices; fast multiplication; efficient matrix operations

In [8], a class of (data-sparse) hierarchical (*-) matrices is introduced that can be used to efficiently assemble and store stiffness matrices arising in boundary element applications. In this paper, we develop and analyse modifications in the construction of an *-matrix that will allow an efficient application to problems involving adaptive mesh refinement. In particular, we present a new clustering algorithm such that, when an *-matrix has to be updated due to some adaptive grid refinement, the majority of the previously assembled matrix entries can be kept whereas only a few new entries resulting from the refinement have to be computed. We provide an efficient implementation of the necessary updates and prove for the resulting *-matrix that the storage requirements as well as the complexity of the matrix-vector multiplication are almost linear, i.e., *.

We simulate an electromagnetic humidity sensor in order to determine its eigenfrequencies. The underlying model is given by Maxwell’s field equations, they are transformed into two decoupled two-dimensional problems by eliminating the magnetic field and changing to cylinder coordinates.

In preceding papers [10]-[15], a class of matrices (H-matrices) has been analysed which are data-sparse and allow an approximate matrix arithmetic of almost linear complexity. Several types of H-matrices were shown to provide good approximation of nonlocal (integral) operators in FEM and BEM applications.

We develop a data-sparse and accurate approximation of the normalised hyperbolic operator sine family generated by a strongly P-positive elliptic operator defined in [4, 7]. In the preceding papers [14]-[18], a class of H-matrices has been analysed which are data-sparse and allow an approximate matrix arithmetic with almost linear complexity. An H-matrix approximation to the operator exponent with a strongly P-positive operator was proposed in [5]. In the present paper, we apply the H-matrix techniques to approximate the elliptic solution operator on cylindric domains Ω× [a, b] associated with the elliptic operator d 2 dx2 − L, x ∈ [a, b]. It is explicitly presented by the operator-valued normalised hyperbolic sine function sinh−1( √L) sinh(x√L) of an elliptic operator L defined in Ω. Starting with the Dunford-Cauchy representation for the hyperbolic sine operator, we then discretise the integral by the exponentially convergent quadrature rule involving a short sum of resolvents. The latter are approximated by the H-matrix techniques. Our algorithm inherits a two-level parallelism with respect to both the computation of resolvents and the treatment of different values of the spatial variable x ∈ [a, b]. The approach is applied to elliptic partial differential equations in domains composed of rectangles or cylinders. In particular, we consider the H-matrix approximation to the interface Poincare-Steklov operators with application in the Schur-complement domain decomposition method. AMS Subject Classification: 65F50, 65F30

Recently ordering techniques have been studied in connection with their influence on the multigrid solution of convection dominant problems [3], [6], [7]. Due to its potential for general applications, in this paper we will detail the characteristics of the software developed to perform numerical tests for the proposed ordering and solution schemes given in [3]. The purpose of this paper is twofold: Firstly, we show how ordering techniques can be incorporated in a complex software package developed for the solution of convection dominated partial differential equations, and secondly, we document the capabilities of the existing software and provide a general description of the employed data structures and interfaces so that users new to the package are able to easily experiment with the implemented ordering techniques or apply it to their own applications.

A class of matrices (H-matrices) has recently been introduced by one of the authors. 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 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.

The well-known smoothing iterations for scalar elliptic problems can usually not be applied to the Stokes- or Navier-Stokes equations. The reason is that the matrices arising from FE- or FD-discretizations of saddle-point problems are no longer positive definite. One remedy is to use the squared system. This leads to convergence in the symmetric case, but does not work if there is dominant convection. In this paper we will describe efficient smoothing methods that depend on the ordering of the unknowns. We provide numerical results illustrating the improved convergence properties of the multigrid algorithm.

We consider the numerical simulation of a piezoceramical system operating as transmitter. The system consists of a piezoceramic, which is embedded in a coupling material and a casing, and is radiating into a liquid (sound field).