Abstract
In 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(n 2), 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abramowitz, M., Stegun, I.A.: Handbook of Mathematical Functions. Dover, New York (1968)
Bertoglio, C., Khoromskij, B.N.: Low rank tensor-product approximation of the projected Green kernels via Sinc-quadratures. Preprint MPI MIS 79/2008, Leipzig, 2008 (submitted)
Beylkin, G., Mohlenkamp, M.J.: Numerical operator calculus in higher dimensions. Proc. Natl. Acad. Sci. USA 99, 10246–10251 (2002)
Beylkin, G., Mohlenkamp, M.J., Pérez, F.: Approximating a wavefunction as an unconstrained sum of Slater determinants. J. Math. Phys. 49, 032107 (2008)
Beylkin, G., Kurcz, Ch., Monzón, L.: Fast algorithms for Helmholtz Green’s function. Proc. R. Soc., Ser. A 464, 3301–3326 (2008)
Beylkin, G., Kurcz, Ch., Monzón, L.: Fast Convolution with the Free Space Helmholtz Green’s function. University of Colorado at Bolder, http://amath.colorado.edu/pub/wavelets/papers/BE-KU-MO-2008P.pdf
De Lathauwer, L., De Moor, B., Vandewalle, J.: On the best rank-1 and rank-(R 1,…,R N ) approximation of higher-order tensors. SIAM J. Matrix Anal. Appl. 21, 1324–1342 (2000)
De Lathauwer, L., De Moor, B., Vandewalle, J.: A multilinear singular value decomposition. SIAM J. Matrix Anal. Appl. 21, 1253–1278 (2000)
Gavrilyuk, I.P., Hackbusch, W., Khoromskij, B.N.: ℋ-matrix approximation for the operator exponential with applications. Numer. Math. 92, 83–111 (2002)
Gavrilyuk, I.P., Hackbusch, W., Khoromskij, B.N.: Tensor-product approximation to elliptic and parabolic solution operators in higher dimensions. Computing 74, 131–157 (2005)
Griebel, M., Hamaekers, J.: Sparse grids for the Schrödinger equation. ESAIM: M2AN 41, 215–247 (2007)
Hackbusch, W., Khoromskij, B.N.: Low-rank Kronecker product approximation to multi-dimensional nonlocal operators, part I: separable approximation of multi-variate functions. Computing 76, 177–202 (2006)
Hackbusch, W., Khoromskij, B.N., Sauter, S., Tyrtyshnikov, E.: Tensor formats in elliptic problems. Preprint MPI MIS 78/2008, Leipzig, 2008 (SINUM, submitted)
Hackbusch, W., Khoromskij, B.N., Tyrtyshnikov, E.: Hierarchical Kronecker tensor-product approximation. J. Numer. Math. 13, 119–156 (2005)
Hackbusch, W., Khoromskij, B.N., Tyrtyshnikov, E.E.: Approximate Iterations for Structured Matrices. Numer. Math. 109, 365–383 (2008)
Harrison, R.J., Fann, G.I., Yanai, T., Gan, Z., Beylkin, G.: Multiresolution quantum chemistry: basic theory and initial applications. J. Chem. Phys. 121(23), 11587–11598 (2004)
Khoromskij, B.N.: An Introduction to Structured Tensor-Product Representation of Discrete Nonlocal Operators, vol. 27. Max-Planck-Institut für Mathematik in den Naturwissenschaften, Leipzig (2005)
Khoromskij, B.N.: Structured rank-(r 1,…,r d ) decomposition of function-related tensors in ℝd. Comput. Methods Appl. Math. 6(2), 194–220 (2006)
Khoromskij, B.N.: On tensor approximation of green iterations for Kohn–Sham equations. Comput. Vis. Sci. 11, 259–271 (2008). doi:10.1007/s00791-008-0097-x
Khoromskij, B.N.: Fast and accurate tensor approximation of multivariate convolution with linear scaling in dimension. Preprint MPI MIS 36, Leipzig, 2008. J. Comput. Appl. Math. (accepted)
Khoromskij, B.N., Khoromskaia, V., Chinnamsetty, S.R., Flad, H.-J.: Tensor decomposition in electronic structure calculations on 3D Cartesian grids. J. Comput. Phys. 228, 5749–5762 (2009).
Khoromskij, B.N., Khoromskaia, V.: Low rank tucker-type tensor approximation to classical potentials. Cent. Eur. J. Math. 5(3), 1–28 (2007)
Khoromskij, B.N., Khoromskaia, V.: Multigrid accelerated tensor approximation of function related multi-dimensional arrays. SIAM J. Sci. Comput. 31(4), 3002–3028 (2009)
Khoromskij, B.N., Schwab, Ch.: Tensor approximation of multi-parametric elliptic problems in stochastic PDEs. ETH Zurich, 2009 (in preparation)
Khoromskij, B.N., Wittum, G.: Numerical Solution of Elliptic Differential Equations by Reduction to the Interface. LNCSE, vol. 36. Springer, Berlin (2004)
Maz’ya, V., Schmidt, G.: Approximate Approximations. Math. Surveys and Monographs, vol. 141. AMS, Providence (2007)
Mohlenkamp, M., Young, M.J.: Convergence of Green’s iterations for Schrödinger equations. Preprint 2007 (to appear)
Reed, M., Simon, B.: Methods of Modern Mathematical Physics, I: Functional Analysis. Academic Press, New York (1972)
Stenger, F.: Numerical Methods Based on Sinc and Analytic Functions. Springer, Berlin (1993)
Todor, R.-A., Schwab, Ch.: Convergence rate for sparse approximation of elliptic problems with stochastic coefficients. IMA J. Numer. Anal. 27, 232–261 (2007)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Christoph Schwab.
Dedicated to Prof. I. Gavrilyuk on the occasion of his 60th birthday.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License ( https://creativecommons.org/licenses/by-nc/2.0 ), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Khoromskij, B.N. Tensor-Structured Preconditioners and Approximate Inverse of Elliptic Operators in ℝd . Constr Approx 30, 599–620 (2009). https://doi.org/10.1007/s00365-009-9068-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00365-009-9068-9
Keywords
- Preconditioning
- High dimensions
- Boundary value problems
- Spectral problems
- Tensor approximation
- Green’s kernels
- Elliptic resolvent