On the fast computation of high dimensional volume potentials

Lanzara, Flavia; Maz’ya, Vladimir; Schmidt, Gunther

doi:10.1090/S0025-5718-2010-02425-1

On the fast computation of high dimensional volume potentials
HTML articles powered by AMS MathViewer

by Flavia Lanzara, Vladimir Maz’ya and Gunther Schmidt PDF

Math. Comp. 80 (2011), 887-904 Request permission

Abstract:

A fast method of an arbitrary high order for approximating volume potentials is proposed, which is effective also in high dimensional cases. Basis functions introduced in the theory of approximate approximations are used. Results of numerical experiments, which show approximation order $O(h^8)$ for the Newton potential in high dimensions, for example, for $n= 200 000$, are provided. The computation time scales linearly in the space dimension. New one-dimensional integral representations with separable integrands of the potentials of advection-diffusion and heat equations are obtained.

References

M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions, Dover Publ., New York, 1968.
Gregory Beylkin, Robert Cramer, George Fann, and Robert J. Harrison, Multiresolution separated representations of singular and weakly singular operators, Appl. Comput. Harmon. Anal. 23 (2007), no. 2, 235–253. MR 2344613, DOI 10.1016/j.acha.2007.01.001
Gregory Beylkin and Martin J. Mohlenkamp, Numerical operator calculus in higher dimensions, Proc. Natl. Acad. Sci. USA 99 (2002), no. 16, 10246–10251. MR 1918798, DOI 10.1073/pnas.112329799
Gregory Beylkin and Martin J. Mohlenkamp, Algorithms for numerical analysis in high dimensions, SIAM J. Sci. Comput. 26 (2005), no. 6, 2133–2159. MR 2196592, DOI 10.1137/040604959
C. Bertoglio and B. N. Khoromskij, Low rank tensor-product approximation of projected Green kernels via sinc-quadratures, Preprint 79, MPI MiS 2008.
Ivan P. Gavrilyuk, Wolfgang Hackbusch, and Boris N. Khoromskij, Hierarchical tensor-product approximation to the inverse and related operators for high-dimensional elliptic problems, Computing 74 (2005), no. 2, 131–157. MR 2133692, DOI 10.1007/s00607-004-0086-y
W. Hackbusch, Efficient convolution with the Newton potential in $d$ dimensions, Numer. Math. 110 (2008), no. 4, 449–489. MR 2447246, DOI 10.1007/s00211-008-0171-9
Wolfgang Hackbusch and Boris N. Khoromskij, Tensor-product approximation to multidimensional integral operators and Green’s functions, SIAM J. Matrix Anal. Appl. 30 (2008), no. 3, 1233–1253. MR 2447450, DOI 10.1137/060657017
B. N. Khoromskij, Fast and accurate tensor approximation of multivariate convolution with linear scaling in dimension, Preprint 36, MPI MiS 2008: J. Comp. Appl. Math., 2010, DOI:10.1016/j.cam.2010.02.004, to appear.
F. Lanzara, V. Maz’ya, and G. Schmidt, Tensor product approximations of high dimensional potentials, Preprint 1403, WIAS Berlin 2009.
V. Maz′ya, Approximate approximations, The mathematics of finite elements and applications (Uxbridge, 1993) Wiley, Chichester, 1994, pp. 77–104. MR 1291219
Vladimir Maz′ya and Gunther Schmidt, “Approximate approximations” and the cubature of potentials, Atti Accad. Naz. Lincei Cl. Sci. Fis. Mat. Natur. Rend. Lincei (9) Mat. Appl. 6 (1995), no. 3, 161–184 (English, with English and Italian summaries). MR 1363785
V. Maz’ya and G. Schmidt, Approximate Approximations, Math. Surveys and Monographs vol. 141, AMS 2007.
Vladimir Maz′ya and Gunther Schmidt, Potentials of Gaussians and approximate wavelets, Math. Nachr. 280 (2007), no. 9-10, 1176–1189. MR 2334668, DOI 10.1002/mana.200510544
J. Waldvogel, Towards a general error theory of the trapezoidal rule. Approximation and Computation 2008. Nis, Serbia, August 25-29, 2008: http://www.math.ethz.ch/~waldvoge/Projects/integrals.html