Fast Numerical Methods for Non-local Operators

Abstract

The fast numerical treatment of non-local operators is an important challenge in many fields of mathematics and its applications. This includes classical Fredholm integral operators, retarded potentials for wave equations, inversion of (discretised) partial differential equations, solutions to the matrix Riccati equation, infinitesimal generators of step processes, non-local filter operators in image processing, or non-local potentials in quantum chemistry and process simulation. The terminology “fast” is related to the “Fast Fourier Transform” which allows to apply the (non-local) discrete Fourier transform of $N$ data points in $O\left(N\log N\right)$ operations instead of $O\left(N^2\right)$ operations.

With growing demand for reliable discretisation methods for such applications the need of fast numerical methods for non-local operators has increased rapidly worldwide since the mid 80th and we list below some of these methods:

1. Cluster methods for the sparse representation of classical Fredholm integral operators.
2. Multipole methods for the fast evaluation of Coulomb-type potentials.
3. $\mathcal{H}$-matrices for the sparse representation of inverses of finite element discretisations of partial differential equations.
4. Wavelet- and multiscale representations of non-local elliptic operators.

These methods allow to reduce the storage amount and the computational cost when applying a non-local operator to $O\left(N\right)$ data points from $O\left(N^2\right)$ to $O\left(N{\log }^{\alpha }N\right)$ , for some moderate $\alpha \sim 1$. This $\log$ -linear complexity is based on an approximate representation of non-local operators which are already afflicted with a consistency error stemming from an underlying numerical discretisation. The size of this additional error is controlled by suitable control parameters in such algorithms and the numerical analysis allows to choose them in an optimal way.

The efficiency of these newly developed numerical methods has generated a vivid research activity in this field of numerical analysis and new challenging problems are arising: For instance, we mention the ab-initio numerical solution of Schrödinger's equation for $N$ particle systems with far field interaction, where the numerical solution for very large $N$ is feasible only by using new fast algorithms for non-local operators. Among further novel applications is the optimal stopping of step-diffusion processes for which the infinitesimal generator of the process is non-local. The full potential of fast methods for such kinds of applications is not yet utilized and research activities are directed in these directions.

A further field of active research is the numerical solution of problems arising in electromagnetics. Such problems are described in a wide range of parameters (wave numbers, dielectric constants, etc.) by Maxwell's equation. Integral operators are often used to reduce the problem on unbounded domains to the compact surface of the scatterer. These operators depend on parameters, e.g., the wave number in a critical way and the fast algorithm are currently developed for such type of problems.

The goal of the (half) conference was to focus on the basic methodological problems such as

• numerical analysis of fast compression methods
• algorithmic aspects of fast compression methods
• fast algorithms for integral equations in electromagnetics
• fast compression algorithms for new types of applications

This Oberwolfach conference brought together 22 scientists in the field of fast numerical methods for non-local operators. The workshop had a clear mathematical focus on the systematic development of fast methods for new types of applications, on their algorithmic aspects and the relevant numerical analysis. A total of 17 presentations were given. The fact that after each talk there arose very stimulating and intense discussions show that the conference truly had workshop character where all participants profited from the talks and the discussions after the talks and in the breaks.

The topics of the talks can be categorized in the following areas:

Discretisation by wavelets and Fast Multipole Methods Wavelets allow the sparse discretisation of non-local operators due to the vanishing moment properties. Progress in the application of wavelets to (time-harmonic) electromagnetic problems for high wave numbers and for high-dimensional problems has been presented by the talks of R. Schneider, J. Tausch and E. Tyrtyshnikov. In O. Steinbach's talk Tearing and Interconnecting Domain Decomposition Methods, the FETI/BETI method was considered which is an efficient preconditioned iterative solver for finite element/boundary element domain decomposition methods. It was shown that dense matrices arising in BETI could be avoided by using the Fast Multipole Method.

$\mathcal{H}$-matrix arithmetics $\mathcal{H}$-matrices allow the sparse representation of non-local inverses of finite element discretisations of PDEs and to perform arithmetic operations such as matrix-matrix multiplication, matrix exponentials, etc. in log-linear complexity. In this field, $\mathcal{H}$-matrix LU based preconditioning of BEM equations have been presented by M. Bebendorf. In his lecture, L. Grasedyck presented adaptive coarsening strategies for $\mathcal{H}$-matrices. A further development in this area was presented by B. Khoromsikij in his talk on data sparse representations for multidimensional non-local operators.

Scattering Problems The numerical solution of inverse scattering problems can be based on an iteration process based on integral equations. The presentation integral equations and numerical solution of inverse scattering problems by R. Kress provided a survey on the newest developments in this area. In his presentation, G. Monegato considered the problem of scattering at a T-junction. The arising integral operators are non-standard and results on their mapping properties and the numerical solution have been presented. In the talk of S. Sauter, the Galerkin method for Helmholtz' equation was analysed and error estimates which are explicit in the wave numbers have been presented. In his presentation, I. Graham presented a method which allows to use asymptotic information to compute diffraction coefficients in high frequency scattering.

Novel Applications In some talks, new applications in the field of non-local operators have been considered. S. Rjasanow has presented numerical solution methods for the non-local electrostatic problems arising in the modelling of large biomolecules. C. Schwab gave a presentation on numerical solution of operator equations based on stochastic data. The computation of the $k$-th moments of the random solution can be based on high-dimensional integral equations and numerical methods for its solution have been presented.

hp Boundary Elements The discretisation of integral equations by $hp$ boundary element method enjoys exponential convergence rates. In the talk of E. Stephan on Schwarz methods for integral equations on surfaces, fast solvers for the arising systems of linear equations have been presented.

Convergence Theory for Boundary Elements Methods Besides the development of fast numerical methods for non-local operators there have been two talks on the stability and convergence theory for integral equations. W. Wendland gave a presentation on J. Radon's convergence proof of J. Neumann's method with double layer potentials while R. Hiptmair has presented a method for a stable coupling of integral equations in scattering.