Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-28T05:34:05.089Z Has data issue: false hasContentIssue false
  • English
  • Français

Numerical tensor calculus*

Published online by Cambridge University Press:  12 May 2014

Wolfgang Hackbusch
Wolfgang Hackbusch*
Affiliation:
Max-Planck-Institut für Mathematik in den Naturwissenschaften, Inselstr. 22, D-04103 Leipzig, Germany, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The usual large-scale discretizations are applied to two or three spatial dimensions. The standard methods fail for higher dimensions because the data size increases exponentially with the dimension. In the case of a regular grid with n grid points per direction, a spatial dimension d yields nd grid points. A grid function defined on such a grid is an example of a tensor of order d. Here, suitable tensor formats help, since they try to approximate these huge objects by a much smaller number of parameters, which increases only linearly in d. In this way, data of size nd = 10001000 can also be treated.

This paper introduces the algebraic and analytical aspects of tensor spaces. The main part concerns the numerical representation of tensors and the numerical performance of tensor operations.

Type
Research Article
Information
Acta Numerica , Volume 23 , May 2014 , pp. 651 - 742
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

Colour online for monochrome figures available at journals.cambridge.org/anu.

References

REFERENCES

Affleck, I., Kennedy, T., Lieb, E. H. and Tasaki, H. (1987), ‘Rigorous results on valence-bond ground states in antiferromagnets’, Phys. Rev. Lett. 59, 799–802.Google Scholar
Andersson, C. A. and Bro, R. (2000), ‘The N-way toolbox for MATLAB’, Chemometrics Intelligent Lab. Syst. 52, 1–4.Google Scholar
Appellof, C. J. and Davidson, E. R. (1981), ‘Strategies for analyzing data from video fluorometric monitoring of liquid-chromatographic effluents’, Anal. Chem. 13, 2053–2056.Google Scholar
Arnold, A. and Jahnke, T. (2012), On the approximation of high-dimensional differential equations in the hierarchical Tucker format. Preprint 12/09, KIT, Karlsruhe.Google Scholar
Bader, B. W. and Kolda, T. G. (2007), MATLAB tensor toolbox, version 2.3. Technical report: http://csmr.ca.sandia.gov/~tgkolda/TensorToolboxGoogle Scholar
Ballani, J. (2012), ‘Fast evaluation of singular BEM integrals based on tensor approximations’, Numer. Math. 121, 433–460.Google Scholar
Ballani, J. and Grasedyck, L. (2013), ‘A projection method to solve linear systems in tensor format’, Numer. Linear Algebra Appl. 20, 27–43.CrossRefGoogle Scholar
Ballani, J., Grasedyck, L. and Kluge, M. (2013), ‘Black box approximation of tensors in hierarchical Tucker format’, Linear Algebra Appl. 438, 639–657.Google Scholar
Bebendorf, M. (2011), ‘Adaptive cross approximation of multivariate functions’, Constr. Approx. 34, 149–179.Google Scholar
Benedikt, U., Auer, A. A., Espig, M. and Hackbusch, W. (2011), ‘Tensor decomposition in post-Hartree-Fock methods I: Two-electron integrals and MP2’, J. Chem. Phys. 134, 054118.CrossRefGoogle ScholarPubMed
Benner, P. and Breiten, T. (2013), ‘Low rank methods for a class of generalized Lyapunov equations and related issues’, Numer. Math. 124, 441–470.CrossRefGoogle Scholar
Beylkin, G. and Mohlenkamp, M. J. (2005), ‘Algorithms for numerical analysis in high dimensions’, SIAM J. Sci. Comput. 26, 2133–2159.Google Scholar
Beylkin, G. and Monzon, L. (2010), ‘Approximation by exponential sums revisited’, Appl. Comput. Harmon. Anal. 28, 131–149.Google Scholar
Beylkin, G., Mohlenkamp, M. J. and Perez, F. (2008), ‘Approximating a wavefunction as an unconstrained sum of Slater determinants’, J. Math. Phys. 49, 032107.CrossRefGoogle Scholar
Bini, D., Lotti, G. and Romani, F. (1980), ‘Approximate solutions for the bilinear form computational problem’, SIAM J. Comput. 9, 692–697.Google Scholar
Braess, D. (1986), Nonlinear Approximation Theory, Springer.Google Scholar
Braess, D. and Hackbusch, W. (2005), ‘Approximation of 1/x by exponential sums in [1, ∞)’, IMA J. Numer. Anal. 25, 685–697.CrossRefGoogle Scholar
Braess, D. and Hackbusch, W. (2009), On the efficient computation of high-dimensional integrals and the approximation by exponential sums. In Multiscale, Nonlinear and Adaptive Approximation (DeVore, R. A. and Kunoth, A., eds), Springer, pp. 39–74.Google Scholar
Buczyński, J. and Landsberg, J. M. (2014), ‘On the third secant variety’, J. Algebraic Combin., to appear.Google Scholar
Bungartz, H.-J. and Griebel, M. (2004), Sparse grids. In Acta Numerica, Vol. 13, Cambridge University Press, pp. 147–269.Google Scholar
Cattell, R. B. (1944), ‘Parallel proportional profiles and other principles for determining the choice of factors by rotation,’ Psychometrika 9, 267–283.CrossRefGoogle Scholar
Chiantini, L. and Ottaviani, G. (2012), ‘On generic identifiability of 3-tensors of small rank,’ SIAM J. Matrix Anal. Appl. 33, 1018–1037.Google Scholar
Chinnamsetty, S. R., Espig, M., Flad, H.-J. and Hackbusch, W. (2010), ‘Canonical tensor products as a generalization of Gaussian-type orbitals,’ Z. Phys. Chem. 224, 681–694.Google Scholar
Comon, P. (2002), Tensor decomposition: State of the art and applications. In Mathematics in Signal Processing V (McWhirter, J. G. and Proudler, I. K., eds), Oxford University Press, pp. 1–24.Google Scholar
Lathauwer, L. De (2008), ‘Decompositions of a higher-order tensor in block terms II: Definitions and uniqueness’, SIAM J. Matrix Anal. Appl. 30, 1033–1066.Google Scholar
Lathauwer, L. De, Moor, B. De and Vandewalle, J. (2000 a), ‘A multilinear singular value decomposition’, SIAM J. Matrix Anal. Appl. 21, 1253–1278.CrossRefGoogle Scholar
Lathauwer, L. De, Moor, B. De and Vandewalle, J. (2000 b), ‘An introduction to independent component analysis’, J. Chemometrics 14, 123–149.3.0.CO;2-1>CrossRefGoogle Scholar
Lathauwer, L. De, Moor, B. De and Vandewalle, J. (2000 c), ‘On the best rank-1 and rank-(R 1,R 2,…,Rn) approximation of higher order tensors’, SIAM J. Matrix Anal. Appl. 21, 1324–1342.Google Scholar
Silva, V. De and Lim, L.-H. (2008), ‘Tensor rank and the ill-posedness of the best low-rank approximation problem’, SIAM J. Matrix Anal. Appl. 30, 1084–1127.Google Scholar
Dolgov, S., Kazeev, V. A. and Khoromskij, B. (2012 a), The tensor-structured solution of one-dimensional elliptic differential equations with high-dimensional parameters. Preprint 51, Max-Planck-Institut für Mathematik in den Naturwissenschaften, Leipzig.Google Scholar
Dolgov, S., Khoromskij, B. and Savostyanov, D. V. (2012b), ‘Superfast Fourier transform using QTT approximation’, J. Fourier Anal. Appl. 18, 915–953.Google Scholar
Eldhen, L. and Savas, B. (2009), ‘A Newton-Grassmann method for computing the best multilinear rank-(r 1,r 2,r 3) approximation of a tensor’, SIAM J. Matrix Anal. Appl. 31, 248–271.CrossRefGoogle Scholar
Espig, M. and Hackbusch, W. (2012), ‘A regularized Newton method for the efficient approximation of tensors represented in the canonical tensor format,’ Numer. Math. 122, 489–525.Google Scholar
Espig, M., Grasedyck, L. and Hackbusch, W. (2009), ‘Black box low tensor-rank approximation using fiber-crosses’, Constr. Approx. 30, 557–597.CrossRefGoogle Scholar
Espig, M., Hackbusch, W., Handschuh, S. and Schneider, R. (2012 a), ‘Optimization problems in contracted tensor networks,’ Comput. Vis. Sci. 14, 271–285.Google Scholar
Espig, M., Hackbusch, W., Litvinenko, A., Matthies, H. G. and Wüahnert, P. (2014), ‘Efficient low-rank approximation of the stochastic Galerkin matrix in tensor formats’, Comput. Math. Appl. 67, 818–829.Google Scholar
Espig, M., Hackbusch, W., Litvinenko, A., Matthies, H. G. and Zander, E. (2013), Efficient analysis of high dimensional data in tensor formats. In Garcke, and Griebel, (2013), pp. 31–56.Google Scholar
Espig, M., Hackbusch, W., Rohwedder, T. and Schneider, R. (2012 b), ‘Variational calculus with sums of elementary tensors of fixed rank’, Numer. Math. 122, 469–488.Google Scholar
Falcó, A. and Nouy, A. (2012), ‘Proper generalized decomposition for nonlinear convex problems in tensor Banach spaces,’ Numer. Math. 121, 503–530.CrossRefGoogle Scholar
Falcó, A., Hackbusch, W. and Nouy, A. (2013), Geometric structures in tensor representations. Preprint 9, Max-Planck-Institut fuür Mathematik in den Naturwissenschaften, Leipzig.Google Scholar
Flad, H.-J., Hackbusch, W. and Schneider, R. (2006), ‘Best N-term approximation in electronic structure calculations I: One-electron reduced density matrix,’ M2AN 40, 49–61.Google Scholar
Flad, H.-J., Hackbusch, W. and Schneider, R. (2007), ‘Best N-term approximation in electronic structure calculations II: Jastrow factors’, M2AN 41, 261–279.Google Scholar
Flad, H.-J., Hackbusch, W., Khoromskij, B. and Schneider, R. (2010), Concept of data-sparse tensor-product approximation in many-particle modelling. In Matrix Methods: Theory, Algorithms, Applications (Olshevsky, V. and Tyrtyshnikov, E. E., eds), World Scientific, pp. 313–343.CrossRefGoogle Scholar
Garcke, J. (2013), Sparse grids in a nutshell. In Garcke, and Griebel, (2013), pp. 57–80.Google Scholar
Garcke, J. and Griebel, M., eds (2013), Sparse Grids and Applications, Vol. 88 of Lecture Notes in Computational Science and Engineering, Springer.Google Scholar
Gavrilyuk, I. P., Hackbusch, W. and Khoromskij, B. (2002), ‘ℋ-matrix approximation for the operator exponential with applications,’ Numer. Math. 92, 83–111.Google Scholar
Grasedyck, L. (2004), ‘Existence and computation of a low Kronecker-rank approximant to the solution of a tensor system with tensor right-hand side,’ Computing 72, 247–266.Google Scholar
Grasedyck, L. (2010 a), ‘Hierarchical singular value decomposition of tensors,’ SIAM J. Matrix Anal. Appl. 31, 2029–2054.Google Scholar
Grasedyck, L. (2010 b), Polynomial approximation in hierarchical Tucker format by vector-tensorization. DFG-SPP 1324. Preprint 43, Philipps-Universitaüt Marburg.Google Scholar
Grasedyck, L. and Hackbusch, W. (2011), ‘An introduction to hierarchical (ℋ-) rank and TT-rank of tensors with examples,’ Comput. Methods Appl. Math. 11, 291–304.Google Scholar
Grasedyck, L., Kressner, D. and Tobler, C. (2013), ‘A literature survey of low-rank tensor approximation techniques,’ GAMM-Mitteilungen 36.CrossRefGoogle Scholar
Greub, W. H. (1975), Linear Algebra, Springer.Google Scholar
Hackbusch, W. (1994), Iterative Solution of Large Sparse System of Equations, Cambridge University Press.Google Scholar
Hackbusch, W. (2005), Entwicklungen nach Exponentialsummen. Techn. Bericht 25, Max-Planck-Institut fuür Mathematik in den Naturwissenschaften, Leipzig.Google Scholar
Hackbusch, W. (2009), Hierarchische Matrizen: Algorithmen und Analysis, Springer.CrossRefGoogle Scholar
Hackbusch, W. (2011), ‘Tensorisation of vectors and their efficient convolution’, Numer. Math. 119, 465–488.Google Scholar
Hackbusch, W. (2012), Tensor Spaces and Numerical Tensor Calculus, Vol. 42 of Springer Series in Computational Mathematics, Springer.Google Scholar
Hackbusch, W. (2013), ‘L ∞ estimation of tensor truncations’, Numer. Math. 125, 419–440.Google Scholar
Hackbusch, W. and Khoromskij, B. (2007), ‘Tensor-product approximation to operators and functions in high dimensions’, J. Complexity 23, 697–714.Google Scholar
Hackbusch, W. and Kuühn, S. (2009), ‘A new scheme for the tensor representation’, J. Fourier Anal. Appl. 15, 706–722.Google Scholar
Hackbusch, W., Khoromskij, B. and Tyrtyshnikov, E. E. (2005), ‘Hierarchical Kronecker tensor-product approximations’, J. Numer. Math. 13, 119–156.Google Scholar
Hackbusch, W., Khoromskij, B. and Tyrtyshnikov, E. E. (2008), ‘Approximate iterations for structured matrices’, Numer. Math. 109, 365–383.CrossRefGoogle Scholar
Handschuh, S. (2012), Changing the topology of tensor networks. Preprint 15, MaxPlanck-Institut fuür Mathematik in den Naturwissenschaften, Leipzig.Google Scholar
Harshman, R. (1970), ‘Foundations of PARAFAC procedure: Models and conditions for an “exploratory” multi-mode analysis’, UCLA Working Papers in Phonetics 16, 1–84.Google Scholar
Håstad, J. (1990), ‘Tensor rank is NP-complete’, J. Algorithms 11, 644–654.Google Scholar
Henrion, R. (1994), ‘N-way principal component analysis: Theory, algorithm and applications’, Chemometrics Intelligent Lab. Syst. 25, 1–23.Google Scholar
Higham, N. J. (2008), Functions of Matrices: Theory and Computation, SIAM.Google Scholar
Hitchcock, F. L. (1927), ‘The expression of a tensor or a polyadic as a sum of products’, J. Math. Phys. 6, 164–189.Google Scholar
Holtz, S., Rohwedder, T. and Schneider, R. (2012 a), ‘On manifolds of tensors of fixed TT-rank’, Numer. Math. 120, 701–731.Google Scholar
Holtz, S., Rohwedder, T. and Schneider, R. (2012 b), ‘The alternating linear scheme for tensor optimization in the tensor train format’, SIAM J. Sci. Comput. 34, A683–A713.Google Scholar
Howell, T. D. (1978), ‘Global properties of tensor rank’, Linear Algebra Appl. 22, 923.Google Scholar
Hiibener, R., Nebendahl, V. and Dür, W. (2010), ‘Concatenated tensor network states’, New J. Phys. 12, 025004.Google Scholar
Huckle, T., Waldherr, K. and Schulte-Herbrüggen, T. (2013), ‘Computations in quantum tensor networks’, Linear Algebra Appl. 438, 750–781.Google Scholar
Ishteva, M., Lathauwer, L. De, Absil, P.-A. and Huffel, S. Van (2009), ‘Differentialgeometric Newton method for the best rank-(r 1,r 2,r 3) approximation of tensors’, Numer. Algorithms 51, 179–194.CrossRefGoogle Scholar
Khoromskij, B. (2009), ‘Tensor-structured preconditioners and approximate inverse of elliptic operators in Rd’, Constr. Approx. 30, 599–620.CrossRefGoogle Scholar
Khoromskij, B. (2011), ‘O(dlogN)-quantics approximation of N – d tensors in high-dimensional numerical modeling’, Constr. Approx. 34, 257–280.Google Scholar
Khoromskij, B. and Schwab, C. (2011), ‘Tensor-structured Galerkin approximation of parametric and stochastic elliptic PDEs’, SIAM J. Sci. Comput. 33, 364–385.Google Scholar
Khoromskij, B., Khoromskaia, V. and Flad, H.-J. (2011), ‘Numerical solution of the Hartree-Fock equation in multilevel tensor-structured format’, SIAM J. Sci. Comput. 33, 45–65.Google Scholar
Koch, O. and Lubich, C. (2010), ‘Dynamical tensor approximation’, SIAM J. Matrix Anal. Appl. 31, 2360–2375.Google Scholar
Kolda, T. G. and Bader, B. W. (2009), ‘Tensor decompositions and applications’, SIAM Rev. 51, 455–500.Google Scholar
Kressner, D. and Tobler, C. (2010), ‘Krylov subspace methods for linear systems with tensor product structure’, SIAM J. Matrix Anal. Appl. 31, 1688–1714.CrossRefGoogle Scholar
Kressner, D. and Tobler, C. (2011 a), Low-rank tensor Krylov subspace methods for parametrized linear systems’, SIAM J. Matrix Anal. Appl. 32, 1288–1316.Google Scholar
Kressner, D. and Tobler, C. (2011 b), ‘Preconditioned low-rank methods for high-dimensional elliptic PDE eigenvalue problems’, Comput. Methods Appl. Math. 11, 363–381.CrossRefGoogle Scholar
Kressner, D. and Tobler, C. (2012), htucker: A Matlab toolbox for tensors in hierarchical Tucker format. Technical report, MATHICSE, EPF Lausanne.Google Scholar
Kroonenberg, P. M. (2008), Applied Multiway Data Analysis, Wiley.Google Scholar
Kruskal, J. B. (1977), ‘Three-way arrays: Rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics’, Linear Algebra Appl. 18, 95–138.Google Scholar
Landsberg, J. M. (2012), Tensors: Geometry and Applications, AMS.Google Scholar
Lubich, C. (2005), ‘On variational approximations in quantum molecular dynamics’, Math. Comp. 74, 765–779.Google Scholar
Lubich, C. (2008), From Quantum to Classical Molecular Dynamics: Reduced Models and Numerical Analysis, EMS, Zürich.Google Scholar
Lubich, C. and Oseledets, I. V. (2013), A projector-splitting integrator for dynamical low-rank approximation. arXiv 1301.1058Google Scholar
Lubich, C., Rohwedder, T., Schneider, R. and Vandereycken, B. (2013), ‘Dynamical approximation of hierarchical Tucker and tensor-train tensors’, SIAM J. Matrix Anal. Appl. 34, 470–494.Google Scholar
Mohlenkamp, M. J. (2010), ‘A center-of-mass principle for the multiparticle Schroidinger equation’, J. Math. Phys. 51, 022112.Google Scholar
Mohlenkamp, M. J. (2013), ‘Musing on multilinear fitting’, Linear Algebra Appl. 438, 834–852.Google Scholar
Oseledets, I. V. (2010), ‘Approximation of matrices using tensor decomposition’, SIAM J. Matrix Anal. Appl. 31, 2130–2145.Google Scholar
Oseledets, I. V. (2011 a), ‘DMRG approach to fast linear algebra in the TT-format’, Comput. Methods Appl. Math. 11, 382–393.Google Scholar
Oseledets, I. V. (2011 b), ‘Tensor-train decomposition’, SIAM J. Sci. Comput. 33, 2295–2317.Google Scholar
Oseledets, I. V. and Tyrtyshnikov, E. E. (2005), ‘Approximate inversion of matrices in the process of solving a hypersingular integral equation’, Comput. Math. Math. Phys. 45, 302–313.Google Scholar
Oseledets, I. V. and Tyrtyshnikov, E. E. (2009 a), ‘Breaking the curse of dimensionality, or how to use SVD in many dimensions’, SIAM J. Sci. Comput. 31, 3744–3759.Google Scholar
Oseledets, I. V. and Tyrtyshnikov, E. E. (2009 b), Tensor tree decomposition does not need a tree. Preprint 2009-08, RAS, Moscow.Google Scholar
Oseledets, I. V., Savostyanov, D. V. and Tyrtyshnikov, E. E. (2009), ‘Linear algebra for tensor problems’, Computing 85, 169–188.CrossRefGoogle Scholar
Oseledets, I. V., Savostyanov, D. V. and Tyrtyshnikov, E. E. (2010), ‘Cross approximation in tensor electron density computations’, Numer. Linear Algebra Appl. 17, 935–952.Google Scholar
Oseledets, I. V., Tyrtyshnikov, E. E. and Zamarashkin, N. L. (2011), ‘Tensor-train ranks for matrices and their inverses’, Comput. Methods Appl. Math. 11, 394–403.Google Scholar
Savas, B. and Elden, L. (2013), ‘Krylov-type methods for tensor computations I’, Linear Algebra Appl. 438, 891–918.Google Scholar
Savostyanov, D. V., Tyrtyshnikov, E. E. and Zamarashkin, N. L. (2012), ‘Fast truncation of mode ranks for bilinear tensor operations’, Numer. Linear Algebra Appl. 19, 103–111.Google Scholar
Schwab, C. and Gittelson, C. J. (2011), 'Sparse tensor discretizations of highdimensional parametric and stochastic PDEs. In Acta Numerica, Vol. 20, Cambridge University Press, pp. 291–467.Google Scholar
Shi, Y., Duan, L. and Vidal, G. (2006), ‘Classical simulation of quantum many-body systems with a tree tensor network’, Phys. Rev. A 74, 022320.Google Scholar
Smilde, A., Bro, R. and Geladi, P. (2004), Multi-way Analysis: Applications in the Chemical Sciences, Wiley.CrossRefGoogle Scholar
Sørensen, M., Lathauwer, L. De, Comon, P., Icart, S. and Deneire, L. (2012), ‘Canonical polyadic decomposition with a columnwise orthonormal factor matrix’, SIAM J. Matrix Anal. Appl. 33, 1190–1213.Google Scholar
Stegeman, A. (2010), ‘On the uniqueness of the nth order tensor decomposition into rank-1 terms with linear independence in one mode’, SIAM J. Matrix Anal. Appl. 31, 2498–2516.Google Scholar
Stenger, F. (1993), Numerical Methods Based on Sinc and Analytic Functions, Springer.Google Scholar
Strassen, V. (1969), ‘Gaussian elimination is not optimal’, Numer. Math. 13, 354–356.Google Scholar
Tucker, L. R. (1966), ‘Some mathematical notes on three-mode factor analysis’, Psychometrika 31, 279–311.Google Scholar
Uschmajew, A. (2010), ‘Convex maximization problems on non-compact Stiefel manifolds with application to orthogonal tensor approximations’, Numer. Math. 115, 309–331.Google Scholar
Uschmajew, A. (2012), ‘Local convergence of the alternating least squares algorithm for canonical tensor approximation’, SIAM J. Matrix Anal. Appl. 33, 639–652.Google Scholar
Verstraete, F. and Cirac, J. I. (2006), ‘Matrix product states represent ground states faithfully’, Phys. Rev. B 73, 094423.Google Scholar
Winograd, S. (1971), ‘On multiplication of 2 × 2 matrices’, Linear Algebra Appl. 4, 381–388.Google Scholar
Yserentant, H. (2010), Regularity and Approximability of Electronic Wave Functions, Vol. 2000 of Lecture Notes in Mathematics, Springer.Google Scholar