-
Chapter 7 Implicit QR-methods for semiseparable matrices
- Johns Hopkins University Press
- Chapter
- Additional Information
Chapter 7 Implicit QR-methods for semiseparable matrices In the previous chapters some of the well-known results for QR-algorithms related to sparse matrices, such as tridiagonal and Hessenberg matrices, were recapitulated. Also interesting theorems connected to QR-algorithms for Hessenberg-like matrices were provided. Starting with a Hessenberg-like matrix we know how to transform it to unreduced form. The structure of a Hessenberg-like matrix after an explicit step of the QR-algorithm is known and an implicit Q-theorem for Hessenberg-like matrices was proved. To construct an implicit algorithm, similarly as for the sparse matrix case, only the implicit step of the QR-method is missing. In this chapter we will provide this step for Hessenberg-like matrices and for symmetric semiseparable matrices. Moreover, we will translate this implicit QR-step such that we can use it to calculate the singular values of an upper triangular semiseparable matrix. The results provided in this chapter can be combined in a straightforward way with the reduction algorithms presented in Part I. Using this combination we can compute the eigenvalues of symmetric and unsymmetric matrices via intermediate semiseparable and Hessenberg-like matrices and we can also compute the singular values of arbitrary matrices via intermediate upper triangular semiseparable matrices. In the first section an implicit QR-algorithm for semiseparable matrices will be designed. Brief discussions about the unreducedness and the type of shift are included. One should make use of the symmetry of the matrix when transforming it to unreduced form. We will consider the Wilkinson shift. The actual implicit QR-algorithm consists of two main parts. In a first part a step of QR without shift will be performed on the semiseparable matrix. The resulting matrix is again semiseparable. In a second part a similarity Givens transformation will be applied on the first two columns and first two rows of the new semiseparable matrix. This will disturb the semiseparable structure. From now on we switch to the implicit approach to restore the semiseparable structure. We will prove that the combination of these two steps corresponds to performing one step of the explicit QR-algorithm. In the third section we focus on the development of an implicit QR-algorithm for Hessenberg-like matrices. The approach followed is similar to the symmetric 199 200 Chapter 7. Implicit QR-methods for semiseparable matrices case. First a step of QR-step without shift is performed. Afterwards a similarity Givens transformation is applied. The resulting disturbed Hessenberg-like matrix will then be reduced back to Hessenberg-like form. Using the implicit Q-theorem one can easily prove that it corresponds to performing an explicit step of QR. In this section we do not yet cover the double shift approach as in Chapter 9 the more general multishift strategy will be discussed. The last section focuses on the computation of singular values of upper triangular semiseparable matrices Su. The implicit approach will be deduced by looking at the implicit QR-algorithm applied to the symmetric matrix S = ST u Su. We will explain what the structure of an unreduced upper triangular semiseparable matrix is and how we can transform it to this form. It will be shown that one step of the QR-method applied to the upper triangular semiseparable matrix Su corresponds to four main steps: transforming the upper triangular semiseparable matrix to lower triangular form; creating a disturbance in the lower triangular semiseparable matrix; transforming the matrix back to lower triangular semiseparable form; finally transforming the resulting semiseparable matrix back to upper triangular semiseparable form. ✎ In this chapter the chasing techniques for restoring the rank structure are developed. Initially we start with symmetric semiseparable matrices. Extra information on unreduced symmetric semiseparable matrices is provided in Subsection 7.1.1. This is however not essential for understanding the remainder of the book. The essential ideas on this algorithm are contained in Subsection 7.1.3. It explains how to perform the two sequences of Givens transformations, the computation of the shift and the different transformations needed for restoring the structure in the matrix. Even though the proof of Theorem 7.6 is though it gives insight into the inner structured rank relations. A brief summary of the algorithm and a proof of correctness are presented in Subsection 7.1.4 for the interested reader. Similar ideas as for the symmetric case can be applied to the Hessenberg-like case. The most important propositions on structure restoration are presented in Subsection 7...