Параллельная реализация матричного крестового метода
Желтков Д.А., Тыртышников Е.Е.

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

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

Название статьи, аннотация и ключевые слова на английском языке

  • Желтков Д.А. – Московский государственный университет им. М.В. Ломоносова, факультет вычислительной математики и кибернетики, Ленинские горы, 119992, Москва; аспирант, e-mail: dmitry.zheltkov@gmail.com
  • Тыртышников Е.Е. – Институт вычислительной математики РAH, ул. Губкина, д. 8, 119333, г. Москва; директор, e-mail: eugene.tyrtyshnikov@gmail.com