Structured data-sparse approximation to high order tensors arising from the deterministic Boltzmann equation

Khoromskij, Boris

doi:10.1090/S0025-5718-07-01901-1

Structured data-sparse approximation to high order tensors arising from the deterministic Boltzmann equation
HTML articles powered by AMS MathViewer

by Boris N. Khoromskij PDF

Math. Comp. 76 (2007), 1291-1315 Request permission

Abstract:

We develop efficient data-sparse representations to a class of high order tensors via a block many-fold Kronecker product decomposition. Such a decomposition is based on low separation-rank approximations of the corresponding multivariate generating function. We combine the $Sinc$ interpolation and a quadrature-based approximation with hierarchically organised block tensor-product formats. Different matrix and tensor operations in the generalised Kronecker tensor-product format including the Hadamard-type product can be implemented with the low cost. An application to the collision integral from the deterministic Boltzmann equation leads to an asymptotical cost $O(n^4\log ^\beta n)$ - $O(n^5\log ^\beta n)$ in the one-dimensional problem size $n$ (depending on the model kernel function), which noticeably improves the complexity $O(n^6\log ^\beta n)$ of the full matrix representation.

References

M. Albrecht: Towards a frequency independent incremental ab initio scheme for the self energy. Preprint University Siegen, 2004; accepted by Theor. Chem. Acc. (2005); DOI:10.1007/S00214-006-0085-5.
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
G. A. Bird, Molecular gas dynamics and the direct simulation of gas flows, Oxford Engineering Science Series, vol. 42, The Clarendon Press, Oxford University Press, New York, 1995. Corrected reprint of the 1994 original; With 1 IBM-PC floppy disk (3.5 inch; DD); Oxford Science Publications. MR 1352466
A. V. Bobylev and S. Rjasanow, Fast deterministic method of solving the Boltzmann equation for hard spheres, Eur. J. Mech. B Fluids 18 (1999), no. 5, 869–887. MR 1728639, DOI 10.1016/S0997-7546(99)00121-1
Dietrich Braess, Nonlinear approximation theory, Springer Series in Computational Mathematics, vol. 7, Springer-Verlag, Berlin, 1986. MR 866667, DOI 10.1007/978-3-642-61609-9
Dietrich Braess and Wolfgang Hackbusch, Approximation of $1/x$ by exponential sums in $[1,\infty )$, IMA J. Numer. Anal. 25 (2005), no. 4, 685–697. MR 2170519, DOI 10.1093/imanum/dri015
Carlo Cercignani, Reinhard Illner, and Mario Pulvirenti, The mathematical theory of dilute gases, Applied Mathematical Sciences, vol. 106, Springer-Verlag, New York, 1994. MR 1307620, DOI 10.1007/978-1-4419-8524-8
G. Csanyi and T.A. Arias: Tensor product expansions for correlation in quantum many-body systems. Phys. Rev. B, v. 61, n. 11 (2000), 7348-7352.
H.-J. Flad, W. Hackbusch, B.N. Khoromskij, and R. Schneider: Concept of data-sparse tensor-product approximation in many-particle models. MPI MIS, Leipzig 2005 (in preparation).
Ivan P. Gavrilyuk, Wolfgang Hackbusch, and Boris N. Khoromskij, Data-sparse approximation to the operator-valued functions of elliptic operator, Math. Comp. 73 (2004), no. 247, 1297–1324. MR 2047088, DOI 10.1090/S0025-5718-03-01590-4
Ivan P. Gavrilyuk, Wolfgang Hackbusch, and Boris N. Khoromskij, Data-sparse approximation to a class of operator-valued functions, Math. Comp. 74 (2005), no. 250, 681–708. MR 2114643, DOI 10.1090/S0025-5718-04-01703-X
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
I. S. Gradshteyn and I. M. Ryzhik, Table of integrals, series, and products, 6th ed., Academic Press, Inc., San Diego, CA, 2000. Translated from the Russian; Translation edited and with a preface by Alan Jeffrey and Daniel Zwillinger. MR 1773820
L. Grasedyck: Existence and computation of a low Kronecker-rank approximation to the solution of a tensor system with tensor right-hand side. Computing 70 (2003), 121-165.
W. Hackbusch: Hierarchische Matrizen – Algorithmen und Analysis. Vorlesungsmanuskript, MPI MIS, Leipzig 2004.
W. Hackbusch and B.N. Khoromskij: Low-Rank Kronecker Tensor-Product Approximation to Multi-dimensional Nonlocal Operators. Parts I/II. Preprints 29/30, Max-Planck-Institut für Mathematik in den Naturwissenschaften, Leipzig 2005 (Computing, to appear).
W. Hackbusch, B. N. Khoromskij, and R. Kriemann, Hierarchical matrices based on a weak admissibility criterion, Computing 73 (2004), no. 3, 207–243. MR 2106249, DOI 10.1007/s00607-004-0080-4
W. Hackbusch, B. N. Khoromskij, and E. E. Tyrtyshnikov, Hierarchical Kronecker tensor-product approximations, J. Numer. Math. 13 (2005), no. 2, 119–156. MR 2149863, DOI 10.1163/1569395054012767
I. Ibragimov and S. Rjasanow, Numerical solution of the Boltzmann equation on the uniform grid, Computing 69 (2002), no. 2, 163–186. MR 1954793, DOI 10.1007/s00607-002-1458-9
H. Koch and A.S. de Merás: Size-intensive decomposition of orbital energy denominators. Journal of Chemical Physics, 113 (2) 508-513 (2000).
Frank Stenger, Numerical methods based on sinc and analytic functions, Springer Series in Computational Mathematics, vol. 20, Springer-Verlag, New York, 1993. MR 1226236, DOI 10.1007/978-1-4612-2706-9
E. E. Tyrtyshnikov, Tensor approximations of matrices generated by asymptotically smooth functions, Mat. Sb. 194 (2003), no. 6, 147–160 (Russian, with Russian summary); English transl., Sb. Math. 194 (2003), no. 5-6, 941–954. MR 1992182, DOI 10.1070/SM2003v194n06ABEH000747
Eugene Tyrtyshnikov, Kronecker-product approximations for some function-related matrices, Linear Algebra Appl. 379 (2004), 423–437. Tenth Conference of the International Linear Algebra Society. MR 2039752, DOI 10.1016/j.laa.2003.08.013
Charles F. Van Loan, The ubiquitous Kronecker product, J. Comput. Appl. Math. 123 (2000), no. 1-2, 85–100. Numerical analysis 2000, Vol. III. Linear algebra. MR 1798520, DOI 10.1016/S0377-0427(00)00393-9
Tong Zhang and Gene H. Golub, Rank-one approximation to high order tensors, SIAM J. Matrix Anal. Appl. 23 (2001), no. 2, 534–550. MR 1871328, DOI 10.1137/S0895479899352045