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

By Boris N. Khoromskij. 2009

69 citations recorded by the source corpus.

AbstractIn the present paper we analyze a class of tensor-structured preconditioners for the multidimensional second-order elliptic operators in ℝd, d≥2. For equations in a bounded domain, the construction is based on the rank-R tensor-product approximation of the elliptic resolvent ℬR≈(ℒ−λI)−1, 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 an unbounded domain, one can utilize the tensor-structured approximation of Green’s kernel for the shifted Laplacian in ℝd, which is well developed in the case of nonoscillatory potentials. For the oscillating kernels e−iκ‖x‖/‖x‖, x∈ℝd, κ∈ℝ+, we give constructive proof of the rank-O(κ) separable approximation. This leads to the tensor representation for the discretized 3D Helmholtz kernel on an n×n×n grid that requires only O(κ |log ε|2 n) reals for storage. Such representations can be applied to both the 3D volume and boundary calculations with sublinear cost O(n2), even in the case κ=O(n).Numerical illustrations demonstrate the efficiency of low tensor-rank approximation for Green’s kernels e−λ‖x‖/‖x‖, x∈ℝ3, in the case of Newton (λ=0), Yukawa (λ∈ℝ+), and Helmholtz (λ=iκ, κ∈ℝ+) potentials, as well as for the kernel functions 1/‖x‖ and 1/‖x‖d−2, x∈ℝ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 the power method with the rank truncation and based on the approximate inverse ℬR≈(−Δ)−1, with 3≤d≤50.

Subfields: Computational Mathematics, Computational Mechanics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

A literature survey of low‐rank tensor approximation techniques (2013, neutral): “Other techniques include the use of approximate inverses for high-dimensional Laplace operators [151, 165, 172, 210], low-rank manipulation of the PDE coefficients [60], low-rank tensor approximation of multilevel preconditioners [8], and low-rank tensor diagonal preconditioners for wavelet discreti”
Mathematik in den Naturwissenschaften Leipzig Tensor-Structured Galerkin Approximation of parametric and stochastic Elliptic PDEs (2010, background): “Detailed discussion on such kind of approximation can be found in [20].”
Numerical Solution of the Hartree - Fock Equation in Multilevel Tensor-Structured Format (2011, background): “1 Introduction In the recent years the concept of tensor-structured numerical methods has opened new perspectives for solving the basic equations of mathematical physics in R, d ≥ 3, in particular, the many-particle Schrödinger equation [1, 11, 2, 27], and multidimensional elliptic spectral problems”
Use of tensor formats in elliptic eigenvalue problems (2012, unknown): “[ 17 ] for the more detailed discussion of preconditionig issues).”
Computation of the Hartree-Fock Exchange by the Tensor-Structured Methods (2010, background): “Theoretical analysis of the multilinear tensor product approaches for the treatment of some multivariate operators and functions arising in scientific computing have been addressed in [5, 6, 8, 12].”
Quantized-TT-Cayley Transform for Computing the Dynamics and the Spectrum of High-Dimensional Hamiltonians (2011, background): “Along the line of [23], we consider the model discrete elliptic problem of stationary type with H = D + V , where D ∈ RI×I represents the elliptic diffusion operator, −∇a(x)∇, 0 < a0 6 a(x) 6 a1 ∈ Rd×d, defined on the tensor-product domain in R, and the matrix V ∈ RI×I , represents some physically r”
Adaptive low rank wavelet methods and applications to two-electron Schrödinger equations (2012, background): “The price to pay is that the corresponding diagonal rescaling leads to a rank increase, similar to known preconditioners for low-rank schemes as considered in [93, 63].”
Tensors-structured Numerical Methods in Scientific Computing: Survey on Recent Advances (2012, background): “In the case of unbounded domains, the low tensor rank preconditioner can be chosen as inverse of the translated Laplacian with positive shift (separable approximation to the Yukawa type Green kernel), that is proven to have the low canonical rank approximation [53, 54].”
O(dlog N)-Quantics Approximation of N-d Tensors in High-Dimensional Numerical Modeling (2011, background): “Other successful applications to high-dimensional eigenvalue problems [17, 24 ] and to stochastic PDEs [29, 30] are reported.”
Constructive Representation of Functions in Low-Rank Tensor Formats (2012, background): “Low-parametric approximation of multivariate functions is very important in highdimensional applications (financial mathematics [33, 36], quantum chemistry [18, 19, 22], multiparametric and stochastic problems [3], and numerical analysis and scientific computing [10, 20, 23]).”
QTT approximation of elliptic solution operators in higher dimensions (2011, methodology): “The numerical algorithms are based on the idea of truncated preconditioned iteration [15, 19, 21] via the TT-approximation method [30, 36], combined with the quantics reshaping of arising multidimensional arrays [21, 32, 33].”
Quantized-TT-Cayley transform to compute dynamics and spectrum of high-dimensional Hamiltonians (2011, methodology): “The time-and-space separation method via the QTT-Cayley-transform enables us to construct the global m-term separable (x, t)-representation of a solution on very fine time-space grid with complexity of order O(dm4 logNt logN), where Nt is the number of sampling points in time.”
Low-rank methods for high-dimensional approximation and model order reduction (2015, unknown): “ic setting, and to [60] for an application to parameter-dependent equations. Note that these iterative methods usually require the construction of good preconditioners in low-rank tensor formats (see [83, 50, 71, 41]). As an example, let us consider simple Richardson iterations for solving (7.2), wh”
An Adaptive Algebraic Multigrid Algorithm for Low-Rank Canonical Tensor Decomposition (2011, unknown): “A second class of problems is related to the decomposition of tensors arising from PDE discretization on high-dimensional regular lattices [27, 28, 17, 18].”