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

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

Авторы

  • Д.А. Желтков
  • Е.Е. Тыртышников

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

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

Аннотация

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

Новые вычислительные технологии

Загрузки

Опубликован

2015-07-11

Выпуск

Том 16 (2015): Выпуск 3.

Раздел

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

Авторы

Д.А. Желтков

Московский государственный университет имени М.В. Ломоносова,
факультет вычислительной математики и кибернетики
Ленинские горы, 119992, Москва
• аспирант

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

Институт вычислительной математики имени Г.И. Марчука РАН (ИВМ РАН)
ул. Губкина, 8, 119333, Москва
• директор

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

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

Лицензия

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

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.