Tensor-structured Preconditioners and Approximate Inverse of Elliptic Operators in ℝ^d

Boris N. Khoromskij

Contact the author: Please use for correspondence this email.
Submission date: 11. Nov. 2008 (revised version: March 2009)
Pages: 24
published in: Constructive approximation, 30 (2009) 3, p. 599-620 
DOI number (of the published article): 10.1007/s00365-009-9068-9
Bibtex
MSC-Numbers: 65F50, 65F30, 46B28
Keywords and phrases: preconditioning, high dimensions, elliptic resolvent, tensor approximation, Green's kernels
Download full preprint: PDF (718 kB)

Abstract:
In the present paper we analyse a class of tensor-structured preconditioners for the multidimensional second order elliptic operators in , . For equations in bounded domain the construction is based on the rank-R tensor-product approximation of the elliptic resolvent , where is the sum of univariate elliptic operators. We prove the explicit estimate on the tensor rank R that ensures the spectral equivalence. For equations in unbounded domain one can utilise the tensor-structured approximation of Green's kernel for the shifted Laplacian in , that is well developed in the case of non-oscillatory potentials. For the oscillating kernels , , we constructive proof of the rank- separable approximation. This leads to the tensor representation for the discretized 3D Helmholtz kernel on grid that requires only reals for storage. Such representations can be applied to both the 3D volume and boundary calculations with sublinear cost even in the case .

Numerical illustrations demonstrate the efficiency of low tensor rank approximation for Green's kernels , , in the case of Newton (), Yukawa () and Helmholtz () potentials, as well as for the kernel functions and , , in higher dimensions d>3. We present numerical results on the iterative calculation of the minimal eigenvalue for the d-dimensional finite difference Laplacian by power method with the rank truncation and based on the approximate inverse , with .