Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

Author: Boris N. Khoromskij
Journal: Math. Comp. 76 (2007), 1291-1315
MSC (2000): Primary 65F50, 65F30; Secondary 15A24, 15A99
Published electronically: February 16, 2007
MathSciNet review: 2299775
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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.
  • 2. G. Beylkin and M.J. Mohlenkamp: Numerical operator calculus in higher dimensions. Proc. Natl. Acad. Sci. USA 99 (2002), 10246-10251.MR 1918798 (2003h:65071)
  • 3. G. Bird: Molecular Gas Dynamics and the Direct Simulation of Gas Flow. Claredon Press, Oxford, 1994.MR 1352466 (97e:76078)
  • 4. A.V. Bobylev and S. Rjasanow: Fast deterministic method of solving the Boltzmann equation for hard spheres. Eur. J. Mech. B/Fluids 18 (1999) 869-887.MR 1728639 (2001c:76109)
  • 5. D. Braess: Nonlinear Approximation Theory. Springer-Verlag, Berlin, 1986.MR 0866667 (88e:41002)
  • 6. D. Braess and W. Hackbusch: Approximation of $ 1/x$ by Exponential Sums in $ [1,\infty)$. Preprint 83, Max-Planck-Institut für Mathematik in den Naturwissenschaften, Leipzig 2004. IMA J. Numer. Anal. 25 (2005), 685-697. MR 2170519
  • 7. Cercignani, C., Illner, R., Pulvirenti, M.: The Mathematical Theory of Dilute Gases. Springer, New York, 1994. MR 1307620 (96g:82046)
  • 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.
  • 9. 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).
  • 10. I.P. Gavrilyuk, W. Hackbusch, and B.N. Khoromskij: Data-sparse approximation to operator-valued functions of elliptic operators. Math. Comp. 73 (2004), no. 247, 1297-1324. MR 2047088 (2005b:47086)
  • 11. I.P. Gavrilyuk, W. Hackbusch, and B.N. Khoromskij: Data-sparse approximation to a class of operator-valued functions. Math. Comp. 74 (2005), 681-708. MR 2114643 (2005i:65068)
  • 12. I. P. Gavrilyuk, W. Hackbusch and B. N. Khoromskij: Tensor-Product Approximation to Elliptic and Parabolic Solution Operators in Higher Dimensions. Computing 74 (2005), 131-157. MR 2133692
  • 13. I.S. Gradshteyn and I.M. Ryzhik: Table of Integrals, Series and Products (6th edition), Academic Press, San Diego, 2000. MR 1773820 (2001c:00002)
  • 14. 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.
  • 15. W. Hackbusch: Hierarchische Matrizen - Algorithmen und Analysis. Vorlesungsmanuskript, MPI MIS, Leipzig 2004.
  • 16. 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).
  • 17. W. Hackbusch, B.N. Khoromskij, and R. Kriemann: Hierarchical matrices based on a weak admissibility criterion. Computing 73 (2004), 207-243. MR 2106249
  • 18. W. Hackbusch, B.N. Khoromskij and E. Tyrtyshnikov: Hierarchical Kronecker tensor-product approximation. Preprint 35, Max-Planck-Institut für Mathematik in den Naturwissenschaften, Leipzig, 2003; J. Numer. Math. 13 (2005), 119-156. MR 2149863 (2006d:65152)
  • 19. I. Ibragimov and S. Rjasanow: Numerical Solution of the Boltzmann Equation on the Uniform Grid. Computing 69(2002), 163-186. MR 1954793 (2004i:82060)
  • 20. H. Koch and A.S. de Merás: Size-intensive decomposition of orbital energy denominators. Journal of Chemical Physics, 113 (2) 508-513 (2000).
  • 21. F. Stenger: Numerical methods based on Sinc and analytic functions. Springer-Verlag, 1993. MR 1226236 (94k:65003)
  • 22. E. E. Tyrtyshnikov: Tensor approximations of matrices generated by asymptotically smooth functions. Sbornik: Mathematics, Vol. 194, No. 5-6 (2003), 941-954 (translated from Mat. Sb., Vol. 194, No. 6 (2003), 146-160.)MR 1992182 (2004d:41036)
  • 23. E. E. Tyrtyshnikov: Kronecker-product approximations for some function-related matrices. Linear Algebra Appl., 379 (2004), 423-437. MR 2039752 (2005d:15005)
  • 24. C. Van Loan: The ubiquitous Kronecker product. J. of Comp. and Applied Mathematics 123 (2000), 85-100. MR 1798520 (2001i:65055)
  • 25. T. Zhang and G.H. Golub: Rank-one approximation to high order tensors. SIAM J. Matrix Anal. Appl. 23 (2001), 534-550. MR 1871328 (2002j:15039)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65F50, 65F30, 15A24, 15A99

Retrieve articles in all journals with MSC (2000): 65F50, 65F30, 15A24, 15A99

Additional Information

Boris N. Khoromskij
Affiliation: Max-Planck-Institute for Mathematics in the Sciences, Inselstr. 22-26, D-04103 Leipzig, Germany

Keywords: Boltzmann equation, hierarchical matrices, Kronecker tensor product, high order tensors, $sinc$ interpolation and quadratures.
Received by editor(s): February 22, 2005
Received by editor(s) in revised form: October 4, 2005
Published electronically: February 16, 2007
Article copyright: © Copyright 2007 American Mathematical Society

American Mathematical Society