General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Zh. Vychisl. Mat. Mat. Fiz.:

Personal entry:
Save password
Forgotten password?

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

This article is cited in 5 scientific papers (total in 5 papers)

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
Received: 10.03.2009

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
\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
\jour Comput. Math. Math. Phys.
\yr 2009
\vol 49
\issue 10
\pages 1662--1677

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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  crossref  mathscinet  zmath  isi  elib
    2. Oseledets I.V., “Tensor-train decomposition”, SIAM J. Sci. Comput., 33:5 (2011), 2295–2317  crossref  mathscinet  zmath  isi  elib
    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  crossref  mathscinet  zmath  isi
    4. Dolgov S., Khoromskij B., Savostyanov D., “Superfast Fourier transform using QTT approximation”, J. Fourier Anal. Appl., 18:5 (2012), 915–953  crossref  mathscinet  zmath  isi  elib
    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  crossref  mathscinet  zmath  isi  elib
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Number of views:
    This page:328
    Full text:63
    First page:13

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2018