Fast Numerical Methods for Non-local Operators

  • Wolfgang Hackbusch

    Max-Planck-Institut für Mathematik in den Naturwissenschaften, Leipzig, Germany
  • Stefan A. Sauter

    Universität Zürich, Switzerland
  • Christoph Schwab

    Eidgenössische Technische Hochschule, Zürich, Switzerland
Fast Numerical Methods for Non-local Operators cover

A subscription is required to access this article.


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 \textquotedblleft fast\textquotedblright\ is related to the \textquotedblleft Fast Fourier Transform\textquotedblright\ which allows to apply the (non-local) discrete Fourier transform of NN data points in % O\left( N\log N\right) operations instead of O(N2)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: \begin{enumerate} \item Cluster methods for the sparse representation of classical Fredholm integral operators. \item Multipole methods for the fast evaluation of Coulomb-type potentials. \item H\mathcal{H}-matrices for the sparse representation of \textit{% inverses} of finite element discretisations of partial differential equations. \item Wavelet- and multiscale representations of non-local elliptic operators. \end{enumerate} These methods allow to reduce the storage amount and the computational cost when applying a non-local operator to O(N)O\left( N\right) data points from % O\left( N^{2}\right) to O(NlogαN)O\left( N\log ^{\alpha }N\right) , for some moderate α1\alpha \sim 1. This log\log -linear complexity is based on an \textit{approximate} representation of non-local operators which are already afflicted with a consistency error stemming from an underlying numerical discretisation. The size of this \textit{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\"{o}dinger's equation for NN particle systems with far field interaction, where the numerical solution for very large NN 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 \begin{itemize} \item numerical analysis of fast compression methods. \item algorithmic aspects of fast compression methods. \item fast algorithms for integral equations in electromagnetics. \item fast compression algorithms for new types of applications. \end{itemize} 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: \begin{itemize} \item \textbf{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 \textit{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. \medskip \item H\mathcal{H}\textbf{-matrix arithmetics} H\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, H\mathcal{H}-matrix LU based preconditioning of BEM equations have been presented by M. Bebendorf. In his lecture, L. Grasedyck presented \textit{adaptive coarsening strategies for }% \mathcal{H}\textit{-matrices.} A further development in this area was presented by B. Khoromsikij in his talk on \textit{data sparse representations for multidimensional non-local operators}. \medskip \item \textbf{Scattering Problems} The numerical solution of inverse scattering problems can be based on an iteration process based on integral equations. The presentation \textit{% integral equations and numerical solution of inverse scattering problems }by R. Kress provided a survey on the newest developments in this area. %S. Chandler-Wilde {\Huge HIS ABSTRACT IS\ STILL MISSING}. 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. \medskip \item \textbf{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 \textit{numerical solution of operator equations based on stochastic data}. The computation of the kk-th moments of the random solution can be based on high-dimensional integral equations and numerical methods for its solution have been presented. \medskip \item \textbf{hp Boundary Elements} The discretisation of integral equations by hphp boundary element method enjoys exponential convergence rates. In the talk of E. Stephan on \textit{% Schwarz methods for integral equations on surfaces}, fast solvers for the arising systems of linear equations have been presented. \medskip \item \textbf{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 \textit{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.

Cite this article

Wolfgang Hackbusch, Stefan A. Sauter, Christoph Schwab, Fast Numerical Methods for Non-local Operators. Oberwolfach Rep. 1 (2004), no. 3, pp. 1747–1788

DOI 10.4171/OWR/2004/33