Approximate multiplication of tensor matrices based on the individual filtering of factors

D. V. Savostyanov   ; E. E. Tyrtyshnikov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 10, pp. 1741-1756

Résumé

Algorithms are proposed for the approximate calculation of the matrix product $\tilde{\mathbf C}\approx\mathbf C=\mathbf A\cdot\mathbf B$, where the matrices $\mathbf A$ and $\mathbf B$ are given by their tensor decompositions in either canonical or Tucker format of rank $r$. The matrix $\mathbf C$ is not calculated as a full array; instead, it is first represented by a similar decomposition with a redundant rank and is then reapproximated (compressed) within the prescribed accuracy to reduce the rank. The available reapproximation algorithms as applied to the above problem require that an array containing $r^{2d}$ elements be stored, where d is the dimension of the corresponding space. Due to the memory and speed limitations, these algorithms are inapplicable even for the typical values $d=3$ and $r\sim30$. In this paper, methods are proposed that approximate the mode factors of $\mathbf C$ using individually chosen accuracy criteria. As an application, the three-dimensional Coulomb potential is calculated. It is shown that the proposed methods are efficient if r can be as large as several hundreds and the reapproximation (compression) of $\mathbf C$ has low complexity compared to the preliminary calculation of the factors in the tensor decomposition of $\mathbf C$ with a edundant rank.

Bibliographie

[1] Beylkin G., Mohlenkamp M. J., “Numerical operator calculus in higher dimensions”, Proc. Nat. Acad. Sci. USA, 99:16 (2002), 10246–10251 | DOI | MR | Zbl

[2] Ford J. M., Tyrtyshnikov E. E., “Combining Kronecker product approximation with discrete wavelet transforms to solve dense, function-related systems”, SIAM J. Sci. Comput., 25:3 (2003), 961–981 | DOI | MR | Zbl

[3] Tyrtyshnikov E. E., “Tenzornye approksimatsii matrits, porozhdennykh asimptoticheski gladkimi funktsiyami”, Matem. sb., 194:6 (2003), 147–160 | MR | Zbl

[4] Tyrtyshnikov E. E., “Kronecker-product approximations for some function-related matrices”, Linear Algebra Appl., 379 (2004), 423–437 | DOI | MR | Zbl

[5] Grasedyck L., “Existence and computation of low Kronecker-rank approximations for large systems in tensor product structure”, Computing, 72 (2004), 247–265 | DOI | MR | Zbl

[6] Hackbusch W., Khoromskij B. N., Tyrtyshnikov E. E., “Hierarchical Kronecker tensor-product approximations”, J. Numer. Math., 13 (2005), 119–156 | DOI | MR | Zbl

[7] Beylkin G., Mohlenkamp M. J., “Algorithms for numerical analysis in high dimensions”, SIAM J. Sci. Comput., 26:6 (2005), 2133–2159 | DOI | MR | Zbl

[8] Oseledets I. V., Tyrtyshnikov E. E., “Approximate inversion of matrices in the process of solving a hypersingular integral equation”, Comput. Math. and Math. Phys., 45:2 (2005), 302–313 | MR | Zbl

[9] Hackbusch W., Khoromskij B. N., Sauter S. A., Tyrtyshnikov E. E., Use of tensor formats in elliptic eigenvalue problems, Preprint 78, MIS MPI, Leipzig, 2008; http://www.mis.mpg.de/preprints/2008/preprint2008-7 8.pdf

[10] Flad H.-J., Khoromskij B. N., Savostyanov D. V., Tyrtyshnikov E. E., “Verification of the cross 3D algorithm on quantum chemistry data”, Rus. J. Numer. Analys. Math. Model., 23:4 (2008), 210–220 | MR

[11] Hackbusch W., Khoromskij B. N., Tyrtyshnikov E. E., “Approximate iterations for structured matrices”, Numer. Math., 109:3 (2008), 365–383 | DOI | MR | Zbl

[12] Oseledets I. V., Savostyanov D. V., Tyrtyshnikov E. E., “Linear algebra for tensor problems”, Computing, 85:3 (2009), 169–188 | DOI | MR | Zbl

[13] Harshman R. A., “Foundations of the Parafac procedure: models and conditions for an explanatory multimodal factor analysis”, UCLA Working Papers in Phonetics, 16 (1970), 1–84

[14] Tucker L. R., “Some mathematical notes on three-mode factor analysis”, Psychometrika, 31 (1966), 279–311 | DOI | MR

[15] Caroll J. D., Chang J. J., “Analysis of individual differences in multidimensional scaling via $n$-way generalization of Eckart-Young decomposition”, Psychometrika, 35 (1970), 283–319 | DOI

[16] Bro R., “PARAFAC: Tutorial and applications”, Chemometrics and Intelligent Lab. Systems, 38:2 (1997), 149–171 | DOI

[17] Comon P., Tensor decomposition: state of the art and applications, IMA Conf. Math. in Signal. Proc., Warwick, UK, 2000

[18] de Lathauwer L., de Moor B., Vandewalle J., “Computing of Canonical decomposition by means of a simultaneous generalized Schur decomposition”, SIAM J. Matrix Analys. Appl., 26 (2004), 295–327 | DOI | MR | Zbl

[19] Espig M., Grasedick L., Hackbusch W., Black box low tensor rank approximation using fibre-crosses. Constr. appr., , 2009 http://www.mis.mpg.de/preprints/2008/preprint2008-60.pdf | MR | Zbl

[20] Oseledets I. V., Savostyanov D. V., Tyrtyshnikov E. E., “Fast simultaneous orthogonal reduction to triangular matrices”, SIAM J. Matrix Analys. Appl., 31:2 (2009), 316–330 | DOI | MR

[21] de Lathauwer L., de Moor B., Vandewalle J., “A multlinear singular value decomposition”, SIAM J. Matrix Analys. Appl., 21 (2000), 1253–1278 | DOI | MR | Zbl

[22] de Lathauwer L., de Moor B., Vandewalle J., “On best rank-1 and rank-$(R_1,R_2,\dots,R_N)$ approximation of highorder tensors”, SIAM J. Matrix Analys. Appl., 21 (2000), 1324–1342 | DOI | Zbl

[23] Savostyanov D. V., Polilineinaya approksimatsiya matrits i integralnye uravneniya, Dis. $\dots$ kand. fiz.-matem. nauk, IVM RAN, M., 2006

[24] Oseledets I. V., Savostianov D. V., Tyrtyshnikov E. E., “Tucker dimensionality reduction of three-dimensional arrays in linear time”, SIAM J. Matrix Analys. Appl., 30:3 (2008), 939–956 | DOI | MR

[25] Goreinov C. A., “O krestovoi approksimatsii mnogoindeksnogo massiva”, Dokl. RAN, 420:4 (2008), 439–441 | MR | Zbl

[26] Khoromskij B. N., Khoromskaia V., “Multigrid accelerated two-level tensor approximation”, SIAM J. Sci. Comput., 31:4 (2009), 3002–3026 | DOI | MR

[27] Khoromskij B. N., “On tensor approximation of Green iterations for Kohn–Sham equations”, Comput. and Visualization in Sci., 11:4–6 (2008), 259–271 | DOI | MR

[28] Goreinov C. A., Tyrtyshnikov E. E., Zamarashkin H. L., “Psevdoskeletnaya approksimatsiya matrits”, Dokl. RAN, 342:2 (1995), 151–153 | MR

[29] Goreinov S. A., Tyrtyshnikov E. E., Zamarashkin N. L., “A theory of pseudo-skeleton approximations”, Lineal Algebra Appl., 261 (1997), 1–21 | DOI | MR | Zbl

[30] Goreinov S. A., Tyrtyshnikov E. E., “The maximal-volume concept in approximation by low-rank matrices”, Contemporary Math., 208 (2001), 47–51 | MR

[31] Tyrtyshnikov E. E., “Incomplete cross approximation in the mosaic-skeleton method”, Computing, 64:4 (2000), 367–380 | DOI | MR | Zbl

[32] Goreinov S. A., Oseledets I. V., Savostyanov D. V. et al., How to find a good submatrix, Res. Rept 08-10, ICM HKBU, Kowloon Tong, Hong Kong, 2008; http://www.math.hkbu.edu.hk/ICM/pdf/08-10.pdf

[33] Bebendorf M., “Approximation of boundary element matrices”, Numer. Math., 86:4 (2000), 565–589 | DOI | MR | Zbl

[34] Savostyanov D. V., Mozaichno-skeletonnye approksimatsii: Rabota na stepen bakalavra, IVM RAN, M., 2001

[35] Oseledets I. V., Savostyanov D. V., Tyrtyshnikov E. E., “Cross approximation in tensor electron density computations”, J. Numer. Linear Algebra Appl., 2009; http://www.math.hkbu.edu.hk/ICM/pdf/09-04.pdf

[36] Braess D., Hackbusch W., On the efficient computation of high-dimensional integrals and the approximation by exponential sums, Preprint 3, MPI MIS, Leipzig, 2009; http://www.mis.mpg.de/preprints/2009/preprint2009-3.pdf

[37] Hackbusch W., Kuhn S., A new scheme for the tensor representation, Preprint 2, MPI MIS, Leipzig, 2009 ; http://www.mis.mpg.de/preprints/2009/preprint2009-2.pdf | MR

[38] Oseledets I. V., Tyrtyshnikov E. E., “Breaking the curse of dimensionality, or how to use SVD in many dimensions”, SIAM J. Sci. Comput., 2009 ; http://www.math.hkbu.edu.hk/ICM/pdf/09-03.pdf | MR