Параллельная реализация алгоритма разреженного QR разложения для прямоугольных верхних квазитреугольных матриц со структурой разреженности типа вложенных сечений

Сергей Александрович Харченко, Алексей Александрович Ющенко

Аннотация


В работе рассматривается параллельная MPI+threads+SIMD реализация алгоритма вычисления разреженного QR разложения специальным образом упорядоченной прямоугольной матрицы на основе разреженных блочных преобразований Хаусхолдера. В алгоритме производится предварительное независимое параллельное вычисление QR разложений для наборов строк матрицы. Затем в соответствии с деревом вычислений производится вычисление QR разложения матриц, составленных из R факторов строчных разложений. Приводятся результаты экспериментов, подтверждающие эффективность предложенной параллельной реализации для тестовых задач. Алгоритм также может быть эффективно реализован на гетерогенных кластерных архитектурах с ускорителями типа GPGPU.

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


разреженная прямоугольная матрица; верхняя квазитреугольная матрица; QR разложение; вложенные сечения; преобразования Хаусхолдера; MPI; многопоточность; SIMD

Полный текст:

PDF

Литература


Тыртышников, Е.Е. Методы численного анализа: учеб. пособие для студ. вузов / Е.Е. Тыртышников — М. : Издательский центр «Академия», 2007. — 320 с. — (Университетский учебник. Сер. Прикладная математика и информатика), ISBN 978-5-7695-3925-1.

Харченко С.А. Параллельный алгоритм разреженного QR разложения для прямо-угольных верхних квазитреугольных матриц со структурой типа вложенных сечений . "Вычислительные методы и программирование", 2015, т. 16, 566-577.

Davis T.A. Algorithm 915: SuiteSparseQR, a multifrontal multithreaded sparse QR factorization package / T.A. Davis // ACM Trans. Math. Softw. — Dec. 2011 — Vol. 38, No. 1 — P. 8:1–8:22.

Yeralan S.N. Algorithm 9xx: Sparse QR Factorization on the GPU / S.N Yeralan, T.A. Davis, S. Ranka // ACM Transactions on Mathematical Software — Jan. 2015 — Vol. 1, No. 1, Article 1.

Rotella F. Block Householder transformation for parallel QR factorization / F. Rotella, I. Zambettakis // Appl. Math. Letters, Vol. 12, I. 4, 1999, 29-34.

Li N. MIQR: A multilevel incomplete QR preconditioner for large sparse least-squares problems / N. Li, Y. Saad // SIAM. J. Matrix Anal. Appl., 28(2), 524–550.

George A. Computer Solution of Large Sparse Positive Definite Systems / A. George, J. W. Liu // Prentice Hall – 1981.

Андреев А.Е. Применение векторных инструкций в алгоритмах блочных операций линейной алгебры / А.Е. Андреев, В.А. Егунов, А.А. Насонов, А.А. Новокщенов // Известия ВолгГТУ. Серия «Актуальные проблемы управления, вычислительной техники и информатики в технических системах» — Вып. 21 : межвуз. сб. науч. ст. — ВолгГТУ. — Волгоград — 2014. — № 12 (139). — C. 5-11.




DOI: http://dx.doi.org/10.14529/cmse160203