Matrix Computations and Semiseparable Matrices: Linear Systems

10 A Gauss solver for higher order structured rank systems

Chapter 10 A Gauss solver for higher order structured rank systems In the previous chapter we studied thoroughly the QR-factorization of structured rank matrices. Special attention was paid to the rank structure of all involved matrices. The matrix Q was factored as a product of Givens transformations and theorems were proven predicting the structure of the upper triangular matrix R. In this chapter we will derive similar theorems for working with Gauss transforms instead of Givens transformations. We already know that the LU-factorization of such a structured rank matrix is not always easy to compute, in particular, pivoting seemed to be troublesome. In this chapter we will go into a little more detail and investigate what the effect of sequences of Gauss transforms (including pivoting) can be on structured rank matrices. In the first section attention will be given to the basic sequences, namely the sequences from bottom to top. We investigate first the effect of these sequences on the lower triangular structure of structured rank matrices. We will show that the performance of such a sequence of Gauss transforms has no effect on the rank structure of the upper triangular structure. This is very interesting, but unfortunately we cannot guarantee in general the existence of such a sequence of Gauss transforms. Following this ascending sequence of transformations, we discuss a sequence of descending transformations for expanding the rank structure of the lower triangular part. Also these transformations leave the rank structure of the upper triangular part unchanged, but again we cannot guarantee their existence in general. In Section 10.2, we discuss pivoting. First, we see what the effect of pivoting is on a structured rank matrix. Second, we will combine pivoting with Gauss transforms to guarantee the existence of rank-decreasing or rank-expanding sequences of transformations. We will deduce general theorems predicting the rank structure of a structured rank matrix after having applied a sequence of Gauss transforms involving pivoting or not. Section 10.3 pays attention to the existence of other Gauss transforms. The Gauss transforms considered in the previous sections were lower Gauss transforms applied on the left side of the matrix. In this section we will briefly investigate upper Gauss transforms and also the application of transformations on the right of 435 436 Chapter 10. A Gauss solver for higher order structured rank systems a matrix. Solving systems of equations using sequences of Gauss transforms is the subject of Section 10.4. First, we discuss how to use the above-discussed techniques for efficiently transforming a matrix to upper triangular form. Unfortunately, we will see that using pivoting in the sequences of transformations will generally destroy the lower or upper triangular form of the factors. This means that in general we will not obtain an LU-factorization anymore, but we will see that we can still use this technique for solving systems of equations. To conclude we show also the existence of some other decompositions such as the UL-decomposition and the L1UL2-decomposition. To conclude this chapter we present similarly as we did in the case of the QR-factorizations a graphical scheme to work with Givens transformations. We will also give a generalization of the nullity theorem and some other interesting relations between lower/upper Gauss transforms and pivoting matrices. ✎ The idea in this chapter is to solve systems of equations by using Gauss transforms. It will be shown that systems can be solved via Gauss transforms, but the computed factorization will not necessarily be linked to the LU-factorization anymore. In a similar way as it was proved and shown in the previous chapter, the effect of a sequence of Gauss transforms on a structured rank matrix is stated in this chapter. The types of sequences involved are annihilating sequences of Gauss transforms (Definition 10.2) and their extension to rank-decreasing sequences of Gauss transforms (Subsection 10.1.4). The effect of such a sequence is discussed in Corollary 10.9 followed by a clarifying explanation. Before being able to explain the effect of a sequence of rank expanding Gauss transformations (Subsection 10.1.7), explanations of the difference between an ascending and a descending sequence of Gauss transforms, discussed in Subsection 10.1.5, and the effect of a zero-creating sequence of Gauss transforms (Subsection 10.1.6) are necessary. Corollary 10.15 summarizes the effect of a rank-expanding sequence of Gauss...