Preprint 82/2008

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
MSC-Numbers: 65F50, 65F30, 46B28
Keywords and phrases: preconditioning, high dimensions, elliptic resolvent, tensor approximation, Green's kernels
Download full preprint: PDF (718 kB)

In the present paper we analyse a class of tensor-structured preconditioners for the multidimensional second order elliptic operators in formula36, formula38. For equations in bounded domain the construction is based on the rank-R tensor-product approximation of the elliptic resolvent formula42, where formula44 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 formula36, that is well developed in the case of non-oscillatory potentials. For the oscillating kernels formula50, formula52, formula54 we constructive proof of the rank-formula56 separable approximation. This leads to the tensor representation for the discretized 3D Helmholtz kernel on formula58 grid that requires only formula60 reals for storage. Such representations can be applied to both the 3D volume and boundary calculations with sublinear cost formula62 even in the case formula64.

Numerical illustrations demonstrate the efficiency of low tensor rank approximation for Green's kernels formula66, formula68, in the case of Newton (formula70), Yukawa (formula72) and Helmholtz (formula74) potentials, as well as for the kernel functions formula76 and formula78, formula52, 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 formula86, with formula88.

19.04.2013, 01:42