Параллельная реализация матричного крестового метода

Авторы

  • Д.А. Желтков Московский государственный университет имени М.В. Ломоносова
  • Е.Е. Тыртышников Институт вычислительной математики имени Г.И. Марчука РАН (ИВМ РАН)

DOI:

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

Ключевые слова:

малоранговые аппроксимации, матричный крестовый метод, параллельные алгоритмы

Аннотация

Матричный крестовый метод является быстрым методом аппроксимации матриц матрицами малого ранга, его сложность составляет O((m+n)r2) операций. Важной особенностью является то, что если матрица задана не как хранящийся в памяти массив, а как функция от двух целочисленных аргументов, то можно найти еe малоранговое приближение, вычислив лишь O((m+n)r) значений этой функции. Однако в случае сверхбольших размеров матрицы или крайней затратности вычисления еe элементов аппроксимация может занимать существенное время. Ускорить метод для подобных случаев можно с помощью параллельных алгоритмов. В настоящей статье предложен эффективный параллельный алгоритм для случая одинаковой сложности вычисления любого элемента матрицы.

Авторы

Д.А. Желтков

Е.Е. Тыртышников

Библиографические ссылки

  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).

Загрузки

Опубликован

2015-07-11

Как цитировать

Желтков Д.А., Тыртышников Е.Е. Параллельная реализация матричного крестового метода // Вычислительные методы и программирование. 2015. 16. 369-375. doi 10.26089/NumMet.v16r336

Выпуск

Раздел

Раздел 1. Вычислительные методы и приложения

Наиболее читаемые статьи этого автора (авторов)