Matrix Computations and Semiseparable Matrices: Linear Systems

7 Inverting semiseparable and related matrices

Chapter 7 Inverting semiseparable and related matrices The inverses of semiseparable and semiseparable plus diagonal matrices have often been used in statistical applications; hence, the extensive list of references related to this subject. In this chapter, we will not discuss all inversion methods, but we will present some techniques/ideas for inverting semiseparable and related matrices. We will not go too deep into detail, as quite often the matrices one wants to invert in a specific application have a very specific rank structure. It is impossible to discuss all possible inversion methods, so we choose to present some general methods based on factorization, and some, in our opinion, interesting direct inversion methods. We start by discussing the use of factorization methods for inverting structured rank matrices. We mention the use of the QR-factorization, the LU-decomposition and the Levinson idea. All three methods will provide a factored form for the inverse of the considered structured rank matrix. In Section 7.2 we discuss some direct inversion methods. We start with inverting symmetric tridiagonal and semiseparable matrices, and we finish with unsymmetric tridiagonal and semiseparable matrices. For inverting tridiagonal matrices we discuss different representations, in which we want to obtain our final semiseparable matrix. Section 7.3 provides some standard formulas, which might come in handy when inverting slightly perturbed structured rank matrices. In Section 7.4 we discuss the optimal scaling of a semiseparable matrix. To scale a semiseparable matrix optimally, we need to compute the diagonal elements of its inverse, that is why this section has been placed in this chapter. Section 7.5 discusses the decay rates of the elements of semiseparable matrices coming from the inverse of diagonally dominant tridiagonal matrices. It will be shown that these elements decay exponentially when going away from the diagonal. ✎ This chapter is concerned with the inversion of structured rank matrices and different aspects related to these structured rank matrices. Inversion of structured rank matrices via factorizations is discussed in Section 7.1. Of course this results in a factored form of the inverse. If one is interested in a direct inversion 257 258 Chapter 7. Inverting semiseparable and related matrices method, several algorithms are presented in Section 7.3. One method for symmetric generator representable matrices was already presented in Chapter 3, Section 3.1. These methods discuss the inversion of specific structured rank matrices, depending on their specific representation. Algorithms are presented for inverting symmetric tridiagonal matrices (for which the inverse is represented with the Givens-vector and the generator representation), the inverse of a Givens-vector represented symmetric semiseparable matrix, two methods for inverting a general tridiagonal matrix and the inverse of a specific generator represented semiseparable matrix. If one wants to invert a matrix, perturbed by a low rank matrix, one needs to read Section 7.3, which presents some standard equations for inverting (low rank) perturbed matrices. Throughout Section 7.5, the most important theorems are the final ones, from Theorem 7.13 to Theorem 7.15, discussing the decay of the elements in the semiseparable inverse of diagonally dominant tridiagonal matrices. 7.1 Known factorizations Based on factorizations, one can often easily invert matrices. In this section we briefly discuss some factorizations developed for the class of structured rank matrices . 7.1.1 Inversion via the QR-factorization Suppose a structured rank matrix A is given, and its QR-factorization is computed. It is straightforward that the following relation also holds: A = QR, A−1 = R−1 Q−1 . Hence, if one has computed the QR-factorization, inversion of Q and R leads to a factored form of the inverse of the matrix A. Let us shortly investigate now in more detail the inverses of the factors Q and R. The inversion of the factor Q is simple. The matrix Q is an orthogonal matrix given in factored form, namely as a product of successive Givens transformations. In total maximum 2n − 1 Givens transformations are involved for computing the QR-factorization of either a semiseparable, quasiseparable or semiseparable plus diagonal matrix. Instead of computing the full matrix Q, it is more efficient to store these Givens transformations and invert them. The inversion of a Givens transformation is trivial. Computing the inverse of the factor R can be done via several methods. In case no structure is involved in the matrix R, e.g., when computing the QR-factorization of a Hessenberg-like matrix, one can...