×

Numerical tensor calculus. (English) Zbl 1396.65091

Summary: 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 \(n^d\) 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 \(n^d = 1000^{1000}\) 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.

MSC:

65F30 Other matrix algorithms (MSC2010)
15A69 Multilinear algebra, tensor calculus
65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Affleck, I.; Kennedy, T.; Lieb, E. H.; Tasaki, H., Rigorous results on valence-bond ground states in antiferromagnets, Phys. Rev. Lett., 59, 799-802, (1987)
[2] Andersson, C. A.; Bro, R., The N-way toolbox for MATLAB, Chemometrics Intelligent Lab. Syst., 52, 1-4, (2000)
[3] Appellof, C. J.; Davidson, E. R., Strategies for analyzing data from video fluorometric monitoring of liquid-chromatographic effluents, Anal. Chem., 13, 2053-2056, (1981)
[4] Arnold, A.; Jahnke, T., On the approximation of high-dimensional differential equations in the hierarchical Tucker format, (2012), KIT, Karlsruhe
[5] Bader, B. W.; Kolda, T. G., (2007)
[6] Ballani, J., Fast evaluation of singular BEM integrals based on tensor approximations, Numer. Math., 121, 433-460, (2012) · Zbl 1261.65026
[7] Ballani, J.; Grasedyck, L., A projection method to solve linear systems in tensor format, Numer. Linear Algebra Appl., 20, 27-43, (2013) · Zbl 1289.65049
[8] Ballani, J.; Grasedyck, L.; Kluge, M., Black box approximation of tensors in hierarchical Tucker format, Linear Algebra Appl., 438, 639-657, (2013) · Zbl 1260.65037
[9] Bebendorf, M., Adaptive cross approximation of multivariate functions, Constr. Approx., 34, 149-179, (2011) · Zbl 1248.41049
[10] Benedikt, U.; Auer, A. A.; Espig, M.; Hackbusch, W., Tensor decomposition in post-Hartree-Fock methods I: two-electron integrals and MP2, J. Chem. Phys., 134, 054118, (2011)
[11] Benner, P.; Breiten, T., Low rank methods for a class of generalized Lyapunov equations and related issues, Numer. Math., 124, 441-470, (2013) · Zbl 1266.65068
[12] Beylkin, G.; Mohlenkamp, M. J., Algorithms for numerical analysis in high dimensions, SIAM J. Sci. Comput., 26, 2133-2159, (2005) · Zbl 1085.65045
[13] Beylkin, G.; Monzon, L., Approximation by exponential sums revisited, Appl. Comput. Harmon. Anal., 28, 131-149, (2010) · Zbl 1189.65035
[14] Beylkin, G.; Mohlenkamp, M. J.; Perez, F., Approximating a wavefunction as an unconstrained sum of Slater determinants, J. Math. Phys., 49, 032107, (2008) · Zbl 1153.81322
[15] Bini, D.; Lotti, G.; Romani, F., Approximate solutions for the bilinear form computational problem, SIAM J. Comput., 9, 692-697, (1980) · Zbl 0446.68035
[16] Braess, D., Nonlinear Approximation Theory, (1986), Springer · Zbl 0656.41001
[17] Braess, D.; Hackbusch, W., Approximation of 1/x by exponential sums in [1, ∞), IMA J. Numer. Anal., 25, 685-697, (2005) · Zbl 1082.65025
[18] Braess, D.; Hackbusch, W.; Devore, R. A.; Kunoth, A., Multiscale, Nonlinear and Adaptive Approximation, On the efficient computation of high-dimensional integrals and the approximation by exponential sums, 39-74, (2009), Springer
[19] Buczyński, J.; Landsberg, J. M., On the third secant variety, J. Algebraic Combin., (2014) · Zbl 1325.14069
[20] Bungartz, H.-J.; Griebel, M., Acta Numerica, 13, Sparse grids, 147-269, (2004), Cambridge University Press
[21] Cattell, R. B., Parallel proportional profiles and other principles for determining the choice of factors by rotation, Psychometrika, 9, 267-283, (1944)
[22] Chiantini, L.; Ottaviani, G., On generic identifiability of 3-tensors of small rank, SIAM J. Matrix Anal. Appl., 33, 1018-1037, (2012) · Zbl 1263.14053
[23] Chinnamsetty, S. R.; Espig, M.; Flad, H.-J.; Hackbusch, W., Canonical tensor products as a generalization of Gaussian-type orbitals, Z. Phys. Chem., 224, 681-694, (2010)
[24] Comon, P.; Mcwhirter, J. G.; Proudler, I. K., Mathematics in Signal Processing V, Tensor decomposition: State of the art and applications, 1-24, (2002), Oxford University Press
[25] Lathauwer, L. De, Decompositions of a higher-order tensor in block terms II: definitions and uniqueness, SIAM J. Matrix Anal. Appl., 30, 1033-1066, (2008) · Zbl 1177.15032
[26] Lathauwer, L. De; Moor, B. De; Vandewalle, J., A multilinear singular value decomposition, SIAM J. Matrix Anal. Appl., 21, 1253-1278, (2000) · Zbl 0962.15005
[27] Lathauwer, L. De; Moor, B. De; Vandewalle, J., An introduction to independent component analysis, J. Chemometrics, 14, 123-149, (2000)
[28] Lathauwer, L. De; Moor, B. De; Vandewalle, J., On the best rank-1 and rank-(R_{1},R_{2},…,R_{n}) approximation of higher order tensors, SIAM J. Matrix Anal. Appl., 21, 1324-1342, (2000) · Zbl 0958.15026
[29] Silva, V. De; Lim, L.-H., Tensor rank and the ill-posedness of the best low-rank approximation problem, SIAM J. Matrix Anal. Appl., 30, 1084-1127, (2008) · Zbl 1167.14038
[30] Dolgov, S.; Kazeev, V. A.; Khoromskij, B., The tensor-structured solution of one-dimensional elliptic differential equations with high-dimensional parameters, (2012), Max-Planck-Institut für Mathematik in den Naturwissenschaften, Leipzig
[31] Dolgov, S.; Khoromskij, B.; Savostyanov, D. V., Superfast Fourier transform using QTT approximation, J. Fourier Anal. Appl., 18, 915-953, (2012) · Zbl 1260.65114
[32] Eldhen, L.; Savas, B., 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, (2009) · Zbl 1205.65161
[33] Espig, M.; Hackbusch, W., A regularized Newton method for the efficient approximation of tensors represented in the canonical tensor format, Numer. Math., 122, 489-525, (2012) · Zbl 1264.65087
[34] Espig, M.; Grasedyck, L.; Hackbusch, W., Black box low tensor-rank approximation using fiber-crosses, Constr. Approx., 30, 557-597, (2009) · Zbl 1181.65064
[35] Espig, M.; Hackbusch, W.; Handschuh, S.; Schneider, R., Optimization problems in contracted tensor networks, Comput. Vis. Sci., 14, 271-285, (2012) · Zbl 1380.49059
[36] Espig, M.; Hackbusch, W.; Litvinenko, A.; Matthies, H. G.; Wüahnert, P., Efficient low-rank approximation of the stochastic Galerkin matrix in tensor formats, Comput. Math. Appl., 67, 818-829, (2014) · Zbl 1350.65005
[37] Espig, M.; Hackbusch, W.; Litvinenko, A.; Matthies, H. G.; Zander, E.; Garcke; Griebel, Efficient analysis of high dimensional data in tensor formats, 31-56, (2013)
[38] Espig, M.; Hackbusch, W.; Rohwedder, T.; Schneider, R., Variational calculus with sums of elementary tensors of fixed rank, Numer. Math., 122, 469-488, (2012) · Zbl 1259.65090
[39] Falcó, A.; Nouy, A., Proper generalized decomposition for nonlinear convex problems in tensor Banach spaces, Numer. Math., 121, 503-530, (2012) · Zbl 1264.65095
[40] Falcó, A.; Hackbusch, W.; Nouy, A., Geometric structures in tensor representations, (2013), Max-Planck-Institut fuür Mathematik in den Naturwissenschaften, Leipzig
[41] Flad, H.-J.; Hackbusch, W.; Schneider, R., Best N-term approximation in electronic structure calculations I: one-electron reduced density matrix, M2AN, 40, 49-61, (2006) · Zbl 1100.81050
[42] Flad, H.-J.; Hackbusch, W.; Schneider, R., Best N-term approximation in electronic structure calculations II: jastrow factors, M2AN, 41, 261-279, (2007) · Zbl 1135.81029
[43] Flad, H.-J.; Hackbusch, W.; Khoromskij, B.; Schneider, R.; Olshevsky, V.; Tyrtyshnikov, E. E., Matrix Methods: Theory, Algorithms, Applications, Concept of data-sparse tensor-product approximation in many-particle modelling, 313-343, (2010), World Scientific
[44] Garcke, J.; Garcke; Griebel, Sparse grids in a nutshell, 57-80, (2013)
[45] Garcke, J.; Griebel, M., Lecture Notes in Computational Science and Engineering, 88, Sparse Grids and Applications, (2013), Springer
[46] Gavrilyuk, I. P.; Hackbusch, W.; Khoromskij, B., ℋ-matrix approximation for the operator exponential with applications, Numer. Math., 92, 83-111, (2002) · Zbl 1005.65113
[47] Grasedyck, L., 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, (2004) · Zbl 1058.65036
[48] Grasedyck, L., Hierarchical singular value decomposition of tensors, SIAM J. Matrix Anal. Appl., 31, 2029-2054, (2010) · Zbl 1210.65090
[49] Grasedyck, L., Polynomial approximation in hierarchical Tucker format by vector-tensorization, (2010), Philipps-Universitaüt Marburg
[50] Grasedyck, L.; Hackbusch, W., An introduction to hierarchical (ℋ-) rank and TT-rank of tensors with examples, Comput. Methods Appl. Math., 11, 291-304, (2011) · Zbl 1283.15075
[51] Grasedyck, L.; Kressner, D.; Tobler, C., A literature survey of low-rank tensor approximation techniques, GAMM-Mitteilungen, 36, (2013) · Zbl 1279.65045
[52] Greub, W. H., Linear Algebra, (1975), Springer
[53] Hackbusch, W., Iterative Solution of Large Sparse System of Equations, (1994), Cambridge University Press
[54] Hackbusch, W., Entwicklungen nach Exponentialsummen. Techn, (2005), Max-Planck-Institut fuür Mathematik in den Naturwissenschaften, Leipzig
[55] Hackbusch, W., Hierarchische Matrizen: Algorithmen und Analysis, (2009), Springer
[56] Hackbusch, W., Tensorisation of vectors and their efficient convolution, Numer. Math., 119, 465-488, (2011) · Zbl 1236.15054
[57] Hackbusch, W., Springer Series in Computational Mathematics, 42, Tensor Spaces and Numerical Tensor Calculus, (2012), Springer
[58] Hackbusch, W., L∞ estimation of tensor truncations, Numer. Math., 125, 419-440, (2013) · Zbl 1282.65046
[59] Hackbusch, W.; Khoromskij, B., Tensor-product approximation to operators and functions in high dimensions, J. Complexity, 23, 697-714, (2007) · Zbl 1141.65032
[60] Hackbusch, W.; Kuühn, S., A new scheme for the tensor representation, J. Fourier Anal. Appl., 15, 706-722, (2009) · Zbl 1188.15022
[61] Hackbusch, W.; Khoromskij, B.; Tyrtyshnikov, E. E., Hierarchical Kronecker tensor-product approximations, J. Numer. Math., 13, 119-156, (2005) · Zbl 1081.65035
[62] Hackbusch, W.; Khoromskij, B.; Tyrtyshnikov, E. E., Approximate iterations for structured matrices, Numer. Math., 109, 365-383, (2008) · Zbl 1144.65029
[63] Handschuh, S., Changing the topology of tensor networks, (2012), MaxPlanck-Institut fuür Mathematik in den Naturwissenschaften, Leipzig
[64] Harshman, R., Foundations of PARAFAC procedure: models and conditions for an “exploratory” multi-mode analysis, UCLA Working Papers in Phonetics, 16, 1-84, (1970)
[65] Håstad, J., Tensor rank is NP-complete, J. Algorithms, 11, 644-654, (1990) · Zbl 0716.65043
[66] Henrion, R., N-way principal component analysis: theory, algorithm and applications, Chemometrics Intelligent Lab. Syst., 25, 1-23, (1994)
[67] Higham, N. J., Functions of Matrices: Theory and Computation, (2008), SIAM · Zbl 1167.15001
[68] Hitchcock, F. L., The expression of a tensor or a polyadic as a sum of products, J. Math. Phys., 6, 164-189, (1927) · JFM 53.0095.01
[69] Holtz, S.; Rohwedder, T.; Schneider, R., On manifolds of tensors of fixed TT-rank, Numer. Math., 120, 701-731, (2012) · Zbl 1242.15022
[70] Holtz, S.; Rohwedder, T.; Schneider, R., The alternating linear scheme for tensor optimization in the tensor train format, SIAM J. Sci. Comput., 34, A683-A713, (2012) · Zbl 1252.15031
[71] Howell, T. D., Global properties of tensor rank, Linear Algebra Appl., 22, 923, (1978)
[72] Hiibener, R.; Nebendahl, V.; Dür, W., Concatenated tensor network states, New J. Phys., 12, 025004, (2010)
[73] Huckle, T.; Waldherr, K.; Schulte-Herbrüggen, T., Computations in quantum tensor networks, Linear Algebra Appl., 438, 750-781, (2013) · Zbl 1259.81088
[74] Ishteva, M.; Lathauwer, L. De; Absil, P.-A.; Huffel, S. Van, Differentialgeometric Newton method for the best rank-(r_{1},r_{2},r_{3}) approximation of tensors, Numer. Algorithms, 51, 179-194, (2009) · Zbl 1166.65334
[75] Khoromskij, B., Tensor-structured preconditioners and approximate inverse of elliptic operators in rd, Constr. Approx., 30, 599-620, (2009) · Zbl 1185.65051
[76] Khoromskij, B., O(dlogN)-quantics approximation of N - d tensors in high-dimensional numerical modeling, Constr. Approx., 34, 257-280, (2011) · Zbl 1228.65069
[77] Khoromskij, B.; Schwab, C., Tensor-structured Galerkin approximation of parametric and stochastic elliptic pdes, SIAM J. Sci. Comput., 33, 364-385, (2011) · Zbl 1243.65009
[78] Khoromskij, B.; Khoromskaia, V.; Flad, H.-J., Numerical solution of the Hartree-Fock equation in multilevel tensor-structured format, SIAM J. Sci. Comput., 33, 45-65, (2011) · Zbl 1227.65113
[79] Koch, O.; Lubich, C., Dynamical tensor approximation, SIAM J. Matrix Anal. Appl., 31, 2360-2375, (2010) · Zbl 1214.15017
[80] Kolda, T. G.; Bader, B. W., Tensor decompositions and applications, SIAM Rev., 51, 455-500, (2009) · Zbl 1173.65029
[81] Kressner, D.; Tobler, C., Krylov subspace methods for linear systems with tensor product structure, SIAM J. Matrix Anal. Appl., 31, 1688-1714, (2010) · Zbl 1208.65044
[82] Kressner, D.; Tobler, C., Low-rank tensor Krylov subspace methods for parametrized linear systems, SIAM J. Matrix Anal. Appl., 32, 1288-1316, (2011) · Zbl 1237.65034
[83] Kressner, D.; Tobler, C., Preconditioned low-rank methods for high-dimensional elliptic PDE eigenvalue problems, Comput. Methods Appl. Math., 11, 363-381, (2011) · Zbl 1283.65025
[84] Kressner, D.; Tobler, C., (2012)
[85] Kroonenberg, P. M., Applied Multiway Data Analysis, (2008), Wiley · Zbl 1160.62002
[86] Kruskal, J. B., Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics, Linear Algebra Appl., 18, 95-138, (1977) · Zbl 0364.15021
[87] Landsberg, J. M., Tensors: Geometry and Applications, (2012), AMS · Zbl 1238.15013
[88] Lubich, C., On variational approximations in quantum molecular dynamics, Math. Comp., 74, 765-779, (2005) · Zbl 1059.81188
[89] Lubich, C., From Quantum to Classical Molecular Dynamics: Reduced Models and Numerical Analysis, (2008), EMS, Zürich · Zbl 1160.81001
[90] Lubich, C.; Oseledets, I. V., (2013)
[91] Lubich, C.; Rohwedder, T.; Schneider, R.; Vandereycken, B., Dynamical approximation of hierarchical Tucker and tensor-train tensors, SIAM J. Matrix Anal. Appl., 34, 470-494, (2013) · Zbl 1391.15087
[92] Mohlenkamp, M. J., A center-of-mass principle for the multiparticle schroidinger equation, J. Math. Phys., 51, 022112, (2010) · Zbl 1309.81083
[93] Mohlenkamp, M. J., Musing on multilinear Fitting, Linear Algebra Appl., 438, 834-852, (2013) · Zbl 1258.15010
[94] Oseledets, I. V., Approximation of matrices using tensor decomposition, SIAM J. Matrix Anal. Appl., 31, 2130-2145, (2010) · Zbl 1200.15005
[95] Oseledets, I. V., DMRG approach to fast linear algebra in the TT-format, Comput. Methods Appl. Math., 11, 382-393, (2011) · Zbl 1283.15041
[96] Oseledets, I. V., Tensor-train decomposition, SIAM J. Sci. Comput., 33, 2295-2317, (2011) · Zbl 1232.15018
[97] Oseledets, I. V.; Tyrtyshnikov, E. E., Approximate inversion of matrices in the process of solving a hypersingular integral equation, Comput. Math. Math. Phys., 45, 302-313, (2005) · Zbl 1073.65569
[98] Oseledets, I. V.; Tyrtyshnikov, E. E., Breaking the curse of dimensionality, or how to use SVD in many dimensions, SIAM J. Sci. Comput., 31, 3744-3759, (2009) · Zbl 1200.65028
[99] Oseledets, I. V.; Tyrtyshnikov, E. E., Tensor tree decomposition does not need a tree, (2009), RAS, Moscow
[100] Oseledets, I. V.; Savostyanov, D. V.; Tyrtyshnikov, E. E., Linear algebra for tensor problems, Computing, 85, 169-188, (2009) · Zbl 1172.65018
[101] Oseledets, I. V.; Savostyanov, D. V.; Tyrtyshnikov, E. E., Cross approximation in tensor electron density computations, Numer. Linear Algebra Appl., 17, 935-952, (2010) · Zbl 1240.81002
[102] Oseledets, I. V.; Tyrtyshnikov, E. E.; Zamarashkin, N. L., Tensor-train ranks for matrices and their inverses, Comput. Methods Appl. Math., 11, 394-403, (2011) · Zbl 1283.15023
[103] Savas, B.; Elden, L., Krylov-type methods for tensor computations I, Linear Algebra Appl., 438, 891-918, (2013) · Zbl 1258.65032
[104] Savostyanov, D. V.; Tyrtyshnikov, E. E.; Zamarashkin, N. L., Fast truncation of mode ranks for bilinear tensor operations, Numer. Linear Algebra Appl., 19, 103-111, (2012) · Zbl 1274.15041
[105] Schwab, C.; Gittelson, C. J., Acta Numerica, 20, Sparse tensor discretizations of highdimensional parametric and stochastic PDEs, 291-467, (2011), Cambridge University Press · Zbl 1269.65010
[106] Shi, Y.; Duan, L.; Vidal, G., Classical simulation of quantum many-body systems with a tree tensor network, Phys. Rev., 74, 022320, (2006)
[107] Smilde, A.; Bro, R.; Geladi, P., Multi-way Analysis: Applications in the Chemical Sciences, (2004), Wiley
[108] Sørensen, M.; Lathauwer, L. De; Comon, P.; Icart, S.; Deneire, L., Canonical polyadic decomposition with a columnwise orthonormal factor matrix, SIAM J. Matrix Anal. Appl., 33, 1190-1213, (2012) · Zbl 1263.15011
[109] Stegeman, A., 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, (2010) · Zbl 1214.15006
[110] Stenger, F., Numerical Methods Based on Sinc and Analytic Functions, (1993), Springer · Zbl 0803.65141
[111] Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 354-356, (1969) · Zbl 0185.40101
[112] Tucker, L. R., Some mathematical notes on three-mode factor analysis, Psychometrika, 31, 279-311, (1966)
[113] Uschmajew, A., Convex maximization problems on non-compact Stiefel manifolds with application to orthogonal tensor approximations, Numer. Math., 115, 309-331, (2010) · Zbl 1192.65086
[114] Uschmajew, A., Local convergence of the alternating least squares algorithm for canonical tensor approximation, SIAM J. Matrix Anal. Appl., 33, 639-652, (2012) · Zbl 1252.65085
[115] Verstraete, F.; Cirac, J. I., Matrix product states represent ground states faithfully, Phys. Rev., 73, 094423, (2006)
[116] Winograd, S., On multiplication of 2 × 2 matrices, Linear Algebra Appl., 4, 381-388, (1971) · Zbl 0225.68018
[117] Yserentant, H., Lecture Notes in Mathematics, 2000, Regularity and Approximability of Electronic Wave Functions, (2010), Springer · Zbl 1204.35003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.