Matrix Computations and Semiseparable Matrices: Linear Systems

9 A QR-factorization for structured rank matrices

Chapter 9 A QR-factorization for structured rank matrices In the beginning of the book we discussed the QR-factorization for the easiest classes of structured rank matrices, e.g., semiseparable, semiseparable plus diagonal and quasiseparable matrices. For quasiseparable matrices, we investigated the computation of the Givens transformations from bottom to top for reducing the rank 1 structure, and then we needed to perform an extra sequence of Givens transformations from top to bottom to bring the Hessenberg structure to upper triangular form. In this chapter we will investigate the QR-decomposition for higher order structured rank matrices in more detail. Even though this might seem much more complicated at first glance, we will try to present easy admissible techniques to tackle this problem. We will, however, in contradiction to the easy case, not present ready-to-use algorithms. We chose not to overload this part of the book with cluttered formulas, but we did choose to present a theory giving insight in the structural behavior of these matrices during the reduction to upper triangular form. This viewpoint will hand the reader interesting tools and will help him to program his own QR-solver for higher order structured rank matrices in an efficient way. The most important idea used throughout this chapter is the decomposition of a structured rank part in a matrix into a sum of lower order structured rank matrices. Even though this decomposition might not be known, in general, the ideas remain valid and are valuable tools in the computation of the QR-factorization. Working on each of the matrices in the decomposition separately gives insight in the complete reduction algorithm. Hence, to investigate in detail the structure of the factors Q and R, of the QR-factorization of structured rank matrices, we decompose the original matrix and investigate in detail the structure of the terms in this decomposition separately. The transformations used for making the involved structured rank matrix of upper triangular form are Givens transformations. In Section 9.1 we investigate the effect of sequences of Givens transformations on order 1 structured rank matrices. Based on these observations we derive general theorems for the performance of a sequence of Givens transformations on a general structured rank matrix. As in the 347 348 Chapter 9. A QR-factorization for structured rank matrices quasiseparable case, sequences are often also needed from top to bottom and we investigate the effect of such sequences on structured rank matrices. To conclude the first section we investigate the application of Givens transformations on the right of the matrix in sequences from left to right and right to left. In Section 9.2, we will combine our gained knowledge to effectively reduce a structured rank matrix to upper triangular form by combining sequences from bottom to top and sequences from top to bottom. We analyze the number of ascending as well as descending sequences of transformations that are essential for bringing the matrix to its desired, upper triangular form. In Section 9.3 we investigate the order of the different sequences of transformations . In the previous section we introduced a pattern of Givens transformations consisting of a number of ascending sequences of transformations, followed by a number of descending sequences of transformations. But it seems that we can change the order of the Givens transformations involved. This gives us, for example , the leaf and pyramid form for removing the rank structure, as well as the leaf and diamond form for removing the subdiagonals. More important is the shift through lemma. This lemma proves that we can rearrange the order of some specifically ordered Givens transformations. This lemma is very interesting as it creates the possibility to perform first the sequences of descending Givens transformations, followed by the sequences of ascending Givens transformations. A lot of flexibility in creating the upper triangular matrix R is created by this lemma. Section 9.4 investigates in more detail the structure of the Givens transformations , if one performs first the sequence of descending Givens transformations for making the matrix upper triangular. It is proven that these Givens transformations do not decrease the rank of the lower part, but in some sense they expand the structure of the lower structured rank part. This means that after performing a sequence of rank expanding Givens transformations from top to bottom, the rank structure in the lower triangular part has grown. Theorems related to the existence of this transformation and its effect on a...