Open AccessA parallel algorithm for the sparse QR decomposition of a rectangular upper quasi-triangular matrix with ND-type sparsity
Author(s) -
С. А. Харченко
Publication year - 2015
Publication title -
vyčislitelʹnye metody i programmirovanie
Language(s) - English
Resource type - Journals
eISSN - 1726-3522
pISSN - 0507-5386
DOI - 10.26089/nummet.v16r453
Subject(s) - qr decomposition , triangular matrix , computation , sparse matrix , algorithm , lu decomposition , matrix (chemical analysis) , decomposition , block (permutation group theory) , mathematics , row and column spaces , block matrix , matrix decomposition , computer science , row , combinatorics , eigenvalues and eigenvectors , pure mathematics , materials science , physics , ecology , database , quantum mechanics , composite material , biology , invertible matrix , gaussian
Рассматривается параллельный алгоритм вычисления разреженного $QR$-разложения специальным образом упорядоченной прямоугольной матрицы на основе разреженных блочных преобразований Хаусхолдера. Для построения необходимого упорядочивания можно использовать столбцевое упорядочивание типа вложенныхсечений, построенное по структуре матрицы $A^{T}A$, где $A$ - исходная прямоугольная матрица. Для сеточных задач упорядочивание может быть построено на основе известного объемного разбиения расчетной сетки. В качестве базового алгоритма для организации параллельных вычислений используется $QR$-разложение для наборов строк матрицы с дополнением в виде нулевого начального блока. An algorithm for computing the sparse $QR$ decomposition of a specially ordered rectangular matrix is proposed. This decomposition is based on the block sparse Householder transformations. For ordering computations, the nested dissection ordering is used for the matrix $A^{T}A$, where $A$ is the original rectangular matrix. For mesh based problems, the orderingcan be constructed starting from an appropriate volume partitioning of the computational mesh. Parallel computations are based on sparse $QR$ decomposition for sets of rows with an additional initial zero block.