RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Zh. Vychisl. Mat. Mat. Fiz.: Year: Volume: Issue: Page: Find

 Zh. Vychisl. Mat. Mat. Fiz., 2009, Volume 49, Number 10, Pages 1741–1756 (Mi zvmmf4765)

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

D. V. Savostyanov, E. E. Tyrtyshnikov

Institute of Numerical Mathematics, Russian Academy of Sciences, ul. Gubkina 8, Moscow, 119333, Russia

Abstract: 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.

Key words: multidimensional arrays, ultidimensional operators, low-parameter representations, canonical decomposition, Tucker decomposition, skeleton approximation, low-rank matrices, data compression, fast recompression, Coulomb potential.

Full text: PDF file (2057 kB)
References: PDF file   HTML file

English version:
Computational Mathematics and Mathematical Physics, 2009, 49:10, 1662–1677

Bibliographic databases:

Document Type: Article
UDC: 519.61

Citation: D. V. Savostyanov, E. E. Tyrtyshnikov, “Approximate multiplication of tensor matrices based on the individual filtering of factors”, Zh. Vychisl. Mat. Mat. Fiz., 49:10 (2009), 1741–1756; Comput. Math. Math. Phys., 49:10 (2009), 1662–1677

Citation in format AMSBIB
\Bibitem{SavTyr09} \by D.~V.~Savostyanov, E.~E.~Tyrtyshnikov \paper Approximate multiplication of tensor matrices based on the individual filtering of factors \jour Zh. Vychisl. Mat. Mat. Fiz. \yr 2009 \vol 49 \issue 10 \pages 1741--1756 \mathnet{http://mi.mathnet.ru/zvmmf4765} \elib{http://elibrary.ru/item.asp?id=12902195} \transl \jour Comput. Math. Math. Phys. \yr 2009 \vol 49 \issue 10 \pages 1662--1677 \crossref{https://doi.org/10.1134/S0965542509100029} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000270979900002} \elib{http://elibrary.ru/item.asp?id=15299656} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-76349097551} 

• http://mi.mathnet.ru/eng/zvmmf4765
• http://mi.mathnet.ru/eng/zvmmf/v49/i10/p1741

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Oseledets I.V., Savostyanov D.V., Tyrtyshnikov E.E., “Cross approximation in tensor electron density computations”, Numer. Linear Algebra Appl., 17:6 (2010), 935–952
2. Oseledets I.V., “Tensor-train decomposition”, SIAM J. Sci. Comput., 33:5 (2011), 2295–2317
3. Goreinov S.A., Oseledets I.V., Savostyanov D.V., “Wedderburn rank reduction and Krylov subspace method for tensor approximation. Part 1: Tucker case”, SIAM J. Sci. Comput., 34:1 (2012), A1–A27
4. Dolgov S., Khoromskij B., Savostyanov D., “Superfast Fourier transform using QTT approximation”, J. Fourier Anal. Appl., 18:5 (2012), 915–953
5. Rakhuba M.V., Oseledets I.V., “Fast Multidimensional Convolution in Low-Rank Tensor Formats Via Cross Approximation”, SIAM J. Sci. Comput., 37:2 (2015), A565–A582
•  Number of views: This page: 348 Full text: 66 References: 33 First page: 13