Parallel Implementation of the Sparse QR Decomposition for Rectangular Upper Quasi Triangular Matrix with ND-type Sparsity
DOI:
https://doi.org/10.14529/cmse160203Keywords:
sparse rectangular matrix, upper quasi triangular matrix, nested dissection, QR decomposition, Householder transformations, MPI, multithreading, SIMDAbstract
The paper considers parallel MPI+threads+SIMD implementation of the algorithm for computing sparse QR decomposition of a specially ordered rectangular matrix. Decomposition is based on block sparse Householder transformations. The algorithm starts with independent parallel QR decompositions for sets of matrix rows; and then, according to the computations tree, the QR decomposition is performed for matrices, combined with elements of R factors of rows decompositions. The results of numerical experiments for test problems show efficiency of the parallel implementation. The algorithm can also be efficiently implemented on heterogeneous cluster architectures with GPGPU accelerators.References
Тыртышников, Е.Е. Методы численного анализа: учеб. пособие для студ. вузов / Е.Е. Тыртышников — М. : Издательский центр «Академия», 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.
