We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.
MiS Preprint
82/2008
Tensor-structured Preconditioners and Approximate Inverse of Elliptic Operators in $\mathbb{R}^d$
Boris N. Khoromskij
Abstract
In the present paper we analyse a class of tensor-structured preconditioners for the multidimensional second order elliptic operators in $\mathbb{R}^d$, $d\geq 2$.
For equations in bounded domain the construction is based on the rank-$R$ tensor-product approximation of the elliptic resolvent ${\cal B}_R\approx ({\cal L}-\lambda {I} )^{-1}$, where ${\cal L}$ 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 $\mathbb{R}^d$, that is well developed in the case of non-oscillatory potentials. For the oscillating kernels $\frac{e^{- i\kappa \|x\|}}{\|x\|} $, $x \in \mathbb{R}^{d} $, $\kappa\in \mathbb{R}_+ $ we constructive proof of the rank-$O(\kappa)$ separable approximation.
This leads to the tensor representation for the discretized 3D Helmholtz kernel on $n\times n \times n$ grid that requires only $O( \kappa \, |\log \varepsilon|^2\, n)$ reals for storage. Such representations can be applied to both the 3D volume and boundary calculations with sublinear cost $O(n^2)$ even in the case $\kappa=O(n)$.
Numerical illustrations demonstrate the efficiency of low tensor rank approximation for Green's kernels $\frac{e^{- \lambda \|x\|}}{\|x\|} $, $x \in \mathbb{R}^{3} $, in the case of Newton ($\lambda=0$), Yukawa ($\lambda \in \mathbb{R}_+$) and Helmholtz ($\lambda= i \kappa, \,\kappa\in \mathbb{R}_+ $) potentials, as well as for the kernel functions ${1}/{\|x\|}$ and ${1}/{\|x\|^{d-2}}$, $x \in \mathbb{R}^{d} $, 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 ${\cal B}_R\approx (-\Delta)^{-1}$, with $3\leq d\leq 50$.
