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