DOI: https://doi.org/10.26089/NumMet.v16r453

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

Авторы

  • С.А. Харченко

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

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

Аннотация

Рассматривается параллельный алгоритм вычисления разреженного QR-разложения специальным образом упорядоченной прямоугольной матрицы на основе разреженных блочных преобразований Хаусхолдера. Для построения необходимого упорядочивания можно использовать столбцевое упорядочивание типа вложенных сечений, построенное по структуре матрицы ATA, где A – исходная прямоугольная матрица. Для сеточных задач упорядочивание может быть построено на основе известного объемного разбиения расчетной сетки. В качестве базового алгоритма для организации параллельных вычислений используется QR-разложение для наборов строк матрицы с дополнением в виде нулевого начального блока.

Новые вычислительные технологии

Загрузки

Опубликован

2015-10-02

Выпуск

Том 16 (2015): Выпуск 4.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

С.А. Харченко

ООО «ТЕСИС»
ул. Юннатов, 18, 127083, Москва
• ведущий программист

Библиографические ссылки

  1. E. E. Tyrtyshnikov, Methods of Numerical Analysis (Akademiya, Moscow, 2007) [in Russian].
  2. A. George and J. W.-H. Liu, Computer Solution of Large Sparse Positive Definite Systems (Prentice-Hall, Englewood Cliffs, 1981; Mir, Moscow, 1984).
  3. I. E. Kaporin, “High Quality Preconditioning of a General Symmetric Positive Definite Matrix Based on its U^T U+U^T R+R^T U-Decomposition,” Numer. Linear Algebra Appl. 5 (6), 483-509 (1998).
  4. T. A. Davis, “Algorithm 915: SuiteSparseQR, a Multifrontal Multithreaded Sparse QR Factorization Package,” ACM Trans. Math. Softw. 38 (1), 8: 1-8: 22 (2011).
  5. S. N. Yeralan, T. A. Davis, and S. Ranka, “Algorithm 9xx: Sparse QR Factorization on the GPU,” ACM Trans. Math. Softw. 1 (1) (2015).
    doi 10.1145/0000000.0000000
  6. N. Li and Y. Saad, “MIQR: A Multilevel Incomplete QR Preconditioner for Large Sparse Least-Squares Problems,” SIAM J. Matrix Anal. Appl. 28 (2), 524-550 (2006).
  7. S. A. Kharchenko and A. A. Yushchenko, “Parallel Implementation of Sparse QR Decomposition of a Rectangular Upper Quasitriangular Matrix with ND-Type Sparsity,” Vestn. South Ural State Univ. Ser. Vychisl. Mat. Inf., 2015 (in press).
  8. F. Rotella and I. Zambettakis, “Block Householder Transformation for Parallel QR Factorization,” Appl. Math. Lett. 12 (4), 29-34 (1999).
  9. A. Haidar, T. T. Dong, S. Tomov, et al., “A Framework for Batched and GPU-Resident Factorization Algorithms Applied to Block Householder Transformations,” in Lecture Notes in Computer Science (Springer, Heidelberg, 2015), Vol. 9137, pp. 31-47.