Параллельная реализация матричного крестового метода
DOI:
https://doi.org/10.26089/NumMet.v16r336Ключевые слова:
малоранговые аппроксимации, матричный крестовый метод, параллельные алгоритмыАннотация
Матричный крестовый метод является быстрым методом аппроксимации матриц матрицами малого ранга, его сложность составляет O((m+n)r2) операций. Важной особенностью является то, что если матрица задана не как хранящийся в памяти массив, а как функция от двух целочисленных аргументов, то можно найти еe малоранговое приближение, вычислив лишь O((m+n)r) значений этой функции. Однако в случае сверхбольших размеров матрицы или крайней затратности вычисления еe элементов аппроксимация может занимать существенное время. Ускорить метод для подобных случаев можно с помощью параллельных алгоритмов. В настоящей статье предложен эффективный параллельный алгоритм для случая одинаковой сложности вычисления любого элемента матрицы.
Библиографические ссылки
- 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)].
- S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, “A Theory of Pseudoskeleton Approximations,” Linear Algebra Appl. 261 (1-3), 1-21 (1997).
- E. Tyrtyshnikov, “Incomplete Cross Approximation in the Mosaic-Skeleton Method,” Computing 64 (4), 367-380 (2000).
- S. A. Goreinov and E. E. Tyrtyshnikov, “The Maximum-Volume Concept in Approximation by Low-Rank Matrices,” Contemp. Math. 280, 47-51 (2001).
- 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.
- 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.
- 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).
- 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)].
- 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).
- I. Oseledets and E. Tyrtyshnikov, “TT-Cross Approximation for Multidimensional Arrays,” Linear Algebra Appl. 432 (1), 70-88 (2010).
- 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).
- 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 «Attribution» («Атрибуция») 4.0 Всемирная.
