Matrix Computations and Semiseparable Matrices: Linear Systems

11 A Levinson-like solver for structured rank matrices

Chapter 11 A Levinson-like solver for structured rank matrices The second part of this book was dedicated to solving systems of equations for the easy classes of structured rank matrices, such as semiseparable, quasiseparable, semiseparable plus diagonal and so forth. The chapter on the Levinson-like solver, restricted its examples to these easy classes. To deal with all these problems at once a unified framework was presented, covering the classes of semiseparable, both generator representable as well as Givens-vector representable, quasiseparable of order 1, etc. But also new combinations seemed to fit perfectly in this scheme, e.g., companion matrices, arrowhead matrices, arrowhead matrices plus a tridiagonal matrix. The general framework as proposed in that chapter is also capable of dealing with more general classes of structured rank matrices, more precisely classes of a higher order structured rank. These examples were naturally omitted in the first part. Here, we revisit the Levinson-like solver and apply it to more general examples. As no more theoretical results are needed to apply the algorithm to these matrices, this chapter is the shortest one in the book. For a clear understanding of the examples below, one might want to reread Section 6.3 of Chapter 6. We will cover different examples here. First, a method is proposed to solve higher order generator representable semiseparable systems of equations. Second, we will cover the class of quasiseparable matrices in their general form as defined in Chapter 8. Band matrices also seem to fit perfectly in this scheme. They are covered in Section 11.3. This is followed by some new examples of matrices having an unsymmetric structure. Having an unsymmetric structure means that the upper triangular part might have a different rank structure than the lower triangular part. In Section 11.5 higher order rank structured matrices which are summations of Levinson-conform matrices are presented. The titles of these sections resemble the titles of the sections in Chapter 6. The examples provided here, however, are more focused on the classes of higher order structured rank matrices. Notes and references are not included for this chapter; they were discussed in Chapter 6. 473 474 Chapter 11. A Levinson-like solver for structured rank matrices ✎ The main ideas for solving systems of equations via a Levinson-like technique were already discussed in Chapter 6. This chapter contains examples related to higher order classes of structured rank matrices. The title of the sections mentions the class of matrices considered. 11.1 Higher order generator representable semiseparable matrices In this section we will develop a Levinson-like solver for higher order generator representable semiseparable matrices. This is another, higher order example of the general framework as we discussed it earlier. Suppose we have the following higher order generator representable semiseparable matrix S(U, V, P, Q): S(U, V, P, Q) = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ qT 1 p1 qT 2 p1 . . . qT n p1 uT 2 v1 qT 2 p2 . . . . . . ... qT n pn−1 uT n v1 . . . uT n vn−1 qT n pn ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ , for which all the row vectors uT i and vT i are of length p and the row vectors pT i and qT i are of length q. This matrix is called a {p, q}-generator representable semiseparable matrix. We will prove now that this matrix is simple {q, p}-Levinson conform. To make the block decomposition of the matrix S = S(U, V, P, Q) more comprehensible , we rewrite the matrix S as follows, thereby reordering the inner products : S = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ pT 1 q1 pT 1 q2 . . . pT 1 qn vT 1 u2 pT 2 q2 . . . . . . ... pT n−1qn vT 1 un . . . vT n−1un pnqT n ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ , Let us define the matrices Rk and Sk as follows: Rk = ⎡ ⎢ ⎣ pT 1 . . . pT k ⎤ ⎥ ⎦ and Sk = ⎡ ⎢ ⎣ vT 1 . . . vT k ⎤ ⎥ ⎦ . Defining Pk = Iq, Qk = Ip, ηk = vk and ξk = pk gives us the following relations (these are Conditions 2 and 3 of Definition 6.4): Rk+1 = & Rk pT k+1 ' and Sk+1 = & Sk vT k+1 ' . 11.2. General quasiseparable matrices 475 Moreover the upper left (k+1)×(k+1) block of A is of the following form (Condition 1 of Definition 6.4): Ak+1 = & Ak Rkqk+1 uT k+1ST k pk+1qT k+1 ' . This coefficient matrix satisfies all the properties to come to the desired O(pqn) Levinson-like solver. Using the operation count as...