Volume 30, pp. 144-167, 2008.

A parallel QR-factorization/solver of quasiseparable matrices

Raf Vandebril, Marc Van Barel, and Nicola Mastronardi

Abstract

This manuscript focuses on the development of a parallel $QR$-factorization of structured rank matrices, which can then be used for solving systems of equations. First, we will prove the existence of two types of Givens transformations, named rank decreasing and rank expanding Givens transformations. Combining these two types of Givens transformations leads to different patterns for annihilating the lower triangular part of structured rank matrices. How to obtain different annihilation patterns, for computing the upper triangular factor $R$, such as the $\vee$ and $\wedge$ pattern will be investigated. Another pattern, namely the $\times$-pattern, will be used for computing the $QR$-factorization in a parallel way. As an example of such a parallel $QR$-factorization, we will implement it for a quasiseparable matrix. This factorization can be run on 2 processors, with one step of intermediate communication in which one row needs to be sent from one processor to the other and back. Another example, showing how to deduce a parallel $QR$-factorization for a more general rank structure will also be discussed. Numerical experiments are included for demonstrating the accuracy and speed of this parallel algorithm w.r.t. the existing factorization of quasiseparable matrices. Also some numerical experiments on solving systems of equations using this approach will be given.

Full Text (PDF) [300 KB], BibTeX

Key words

parallel $QR$-factorization, structured rank matrices, quasiseparable matrix

AMS subject classifications

65F05

Links to the cited ETNA articles

[2]	Vol. 18 (2004), pp. 137-152 Dario A. Bini, Francesco Daddi, and Luca Gemignani: On the shifted QR iteration applied to companion matrices