DOI: https://doi.org/10.26089/NumMet.v16r336

A parallel implementation of the matrix cross approximation method

Authors

  • D.A. Zheltkov
  • E.E. Tyrtyshnikov

Keywords:

low-rank matrix approximations
matrix cross approximation method
parallel algorithms

Abstract

The matrix cross approximation method is a fast method based on low-rank matrix approximations with complexity O((m+n)r2) arithmetic operations. Its main feature consists in the following: if a matrix is not given as an array but is given as a function of two integer arguments, then this method allows one to compute the low-rank approximation of the given matrix by evaluating only O((m+n)r) values of this function. However, if the matrix is extremely large or the evaluation of its elements is computationally expensive, then such an approximation becomes timeconsuming. For such cases, the performance of the method can be improved via parallelization. In this paper we propose an efficient parallel algorithm for the case of an equal computational cost for the evaluation of each matrix element.

New computational technologies

Downloads

Published

2015-07-11

Issue

Vol. 16 (2015): Issue 3.

Section

Section 1. Numerical methods and applications

Author Biographies

D.A. Zheltkov

Lomonosov Moscow State University,
Faculty of Computational Mathematics and Cybernetics
• PhD Student

E.E. Tyrtyshnikov

Institute of Numerical Mathematics of RAS (INM RAS)
• Director

References

  1. S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, “Pseudoskeleton Approximations of Matrices,” Dokl. Akad. Nauk 343 (2), 151-152 (1995) [Dokl. Math. 52 (1), 18-19 (1995)].
  2. S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, “A Theory of Pseudoskeleton Approximations,” Linear Algebra Appl. 261 (1-3), 1-21 (1997).
  3. E. Tyrtyshnikov, “Incomplete Cross Approximation in the Mosaic-Skeleton Method,” Computing 64 (4), 367-380 (2000).
  4. S. A. Goreinov and E. E. Tyrtyshnikov, “The Maximum-Volume Concept in Approximation by Low-Rank Matrices,” Contemp. Math. 280, 47-51 (2001).
  5. S. A. Goreinov, I. V. Oseledets, D. V. Savostyanov, et al., “How to Find a Good Submatrix,” in Matrix Methods: Theory, Algorithms, Applications (World Scientific, Hackensack, 2010), pp. 247-256.
  6. S. L. Stavtsev and E. E. Tyrtyshnikov, “Application of Mosaic-Skeleton Approximations for Solving {EFIE},” in PIERS 2009 Moscow Proc., Moscow, Russia, August 18-21, 2009 (The Electromagnetics Academy, Cambridge, 2009). pp. 1752-1755.
  7. S. L. Stavtsev, “Application of the Method of Incomplete Cross Approximation to a Nonstationary Problem of Vortex Rings Dynamics,” Russ. J. Numer. Anal. Math. Modelling 27 (3), 303-320 (2012).
  8. S. A. Goreinov, “On Cross Approximation of Multi-Index Array,” Dokl. Akad. Nauk 420 (4), 439-441 (2008) [Dokl. Math. 77 (3), 404-406 (2008)].
  9. I. V. Oseledets, D. V. Savostianov, and E. E. Tyrtyshnikov, “Tucker Dimensionality Reduction of Three-Dimensional Arrays in Linear Time,” SIAM J. Matrix Anal. Appl. 30 (3), 939-956 (2008).
  10. I. Oseledets and E. Tyrtyshnikov, “TT-Cross Approximation for Multidimensional Arrays,” Linear Algebra Appl. 432 (1), 70-88 (2010).
  11. H.-J. Flad, B. N. Khoromskij, D. V. Savostyanov, and E. E. Tyrtyshnikov, “Verification of the Cross 3D Algorithm on Quantum Chemistry Data,” Rus. J. Numer. Anal. Math. Modelling 23 (4), 329-344 (2008).
  12. I. V. Oseledets, D. V. Savostyanov, and E. E. Tyrtyshnikov, “Cross Approximation in Tensor Electron Density Computations,” Numer. Linear Algebra Appl. 17 (6), 935-952 (2010).

License

Copyright (c) 2015 Вычислительные методы и программирование

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.