## 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

## Additional Information

**Boris N. Khoromskij**- Affiliation: Max-Planck-Institute for Mathematics in the Sciences, Inselstr. 22-26, D-04103 Leipzig, Germany
- Email: bokh@mis.mpg.de
- Received by editor(s): February 22, 2005
- Received by editor(s) in revised form: October 4, 2005
- Published electronically: February 16, 2007
- © Copyright 2007 American Mathematical Society
- Journal: Math. Comp.
**76**(2007), 1291-1315 - MSC (2000): Primary 65F50, 65F30; Secondary 15A24, 15A99
- DOI: https://doi.org/10.1090/S0025-5718-07-01901-1
- MathSciNet review: 2299775