Параллельная реализация алгоритма разреженного QR разложения для прямоугольных верхних квазитреугольных матриц со структурой разреженности типа вложенных сечений
Автор: Харченко Сергей Александрович, Ющенко Алексей Александрович
Рубрика: Вычислительная математика
Статья в выпуске: 2 т.5, 2016 года.
Бесплатный доступ
В работе рассматривается параллельная MPI+threads+SIMD реализация алгоритма вычисления разреженного QR разложения специальным образом упорядоченной прямоугольной матрицы на основе разреженных блочных преобразований Хаусхолдера. В алгоритме производится предварительное независимое параллельное вычисление QR разложений для наборов строк матрицы. Затем в соответствии с деревом вычислений производится вычисление QR разложения матриц, составленных из R факторов строчных разложений. Приводятся результаты экспериментов, подтверждающие эффективность предложенной параллельной реализации для тестовых задач. Алгоритм также может быть эффективно реализован на гетерогенных кластерных архитектурах с ускорителями типа GPGPU.
Разреженная, прямоугольная матрица, верхняя квазитреугольная матрица, qr разложение, вложенные сечения, преобразования хаусхолдера, многопоточность
Короткий адрес: https://sciup.org/147160590
IDR: 147160590 | DOI: 10.14529/cmse160203
Список литературы Параллельная реализация алгоритма разреженного QR разложения для прямоугольных верхних квазитреугольных матриц со структурой разреженности типа вложенных сечений
- Тыртышников Е.Е. Методы численного анализа: учеб. пособие для студ. вузов. М.: Издательский центр «Академия», 2007. 320 с.
- Харченко С.А. Параллельный алгоритм разреженного QR разложения для прямоугольных верхних квазитреугольных матриц со структурой типа вложенных сечений//Вычислительные методы и программирование. 2015. Т. 16. С. 566-577.
- Davis T.A. Algorithm 915: SuiteSparseQR, a multifrontal multithreaded sparse QR factorization package//ACM Trans. Math. Softw. Dec. 2011 Vol. 38, No. 1 P. 8:1-8:22
- Yeralan S.N., Davis T.A., Ranka S. Algorithm 9xx: Sparse QR Factorization on the GPU//ACM Transactions on Mathematical Software. Jan. 2015. Vol. 1, No. 1, Article 1. P. 1-28
- Rotella F., Zambettakis I. Block Householder transformation for parallel QR factorization//Appl. Math. Letters. Vol. 12, I. 4. 1999. P. 29-34
- Li N., Saad Y. MIQR: A multilevel incomplete QR preconditioner for large sparse leastsquares problems//SIAM. J. Matrix Anal. Appl. 28(2). 2006. P. 524-550
- George A., Liu J.W. Computer Solution of Large Sparse Positive Definite Systems. Prentice Hall, 1981. 324 p
- Андреев А.Е., Егунов В.А., Насонов А.А., Новокщенов А.А. Применение векторных инструкций в алгоритмах блочных операций линейной алгебры//Известия ВолгГТУ. Серия: Актуальные проблемы управления, вычислительной техники и информатики в технических системах. 2014. № 12 (139). C. 5-11
