In lieu of an abstract, here is a brief excerpt of the content:

Chapter 6 A Levinson-like and Schur-like solver Different algorithms for solving systems of equations with semiseparable plus diagonal coefficient matrices have been proposed in the previous chapters. The method proposed in this chapter is based on the underlying idea of the Durbin and the Levinson algorithm for solving Toeplitz systems of equations. Assume we would like to solve the system Ax = b with A of dimension n. The Levinson idea is to solve n systems of equations of increasing size. At step k of the Levinson algorithm a system of dimension k × k is solved with as coefficient matrix the upper left k × k block of the matrix A, and right-hand side the first k elements of the vector b. In the next step, step k + 1, we use the solution of step k to construct the solution of step k + 1. The Levinson algorithm for Toeplitz matrices is widespread and described, for example, in [152, 191, 205]. It takes O(k) operations in each step of the loop. The overall complexity to solve the Toeplitz equations using the Levinson algorithm is therefore O(n2 ). In this chapter, we will derive a similar algorithm for solving systems of equations involving structured rank matrices. Indeed, examples will show that the method is suitable for different types of structured rank matrices, including, for example, band, higher order semiseparable, band plus higher order semiseparable and different other classes. The scope of this second part of the book, however, is limited to the easy classes of structured rank matrices such as semiseparable, quasiseparable, semiseparable plus diagonal and so on. Further on in the text, starting in Part III, higher order structured rank matrices will also be considered. The part on Levinson in this chapter consists of 4 sections. The first section is concerned with a description of the Levinson algorithm for Toeplitz systems. The Yule-Walker equation, the Durbin and the Levinson method are briefly revisited to understand better the following sections involving the structured rank matrices . Section 6.2 covers a Levinson-like method for solving generator representable semiseparable plus diagonal matrices. The considered matrices are symmetric and positive definite. This easy example illustrates the basic ideas of the general method, which is constructed in the third section. This section constructs a Levinson-like 205 206 Chapter 6. A Levinson-like and Schur-like solver solver framework for general matrices. Examples of matrices for which this framework is applicable are provided in the last section. As told earlier, only the simplest classes are discussed. In Chapter 11 we will reconsider this solver and illustrate its power by applying the general framework to different types of structured rank matrices. The last section in this chapter is dedicated to the design of a Schur-like algorithm for generator representable quasiseparable matrices. After the description of the algorithm a more general theorem is proven for the preservation of the rank under Schur complementation. This theorem proves, for example, that the Schur complement of a semiseparable and a quasiseparable matrix inherits the rank structure of the original matrix. Due to this theorem we know the existence of Schur-like algorithms for these classes of matrices. ✎ This chapter discusses a Levinson-like algorithm for solving systems of equations. Section 6.2 proposes a Levinson-like method for generator representable semiseparable plus diagonal matrices. This is a very specific example, but it helps in creating the general picture; however, without loss of generality, one can immediately switch to the general case. The Levinson framework as discussed in Section 6.3 contains the algorithm to which this chapter is dedicated. Definition 6.3 and Definition 6.4 contain an abstract formulation of a matrix block decomposition . Matrices satisfying this decomposition will admit a Levinson-like solver. Section 6.3.2 contains the derivation of the algorithm. The first two subtitles, namely the Yule-Walker-like system and the Levinson-like solver present the main ideas. A first method is presented, but this approach is further tuned, reducing the computational complexity. Algorithm 6.9 proposes then the real Levinson-like algorithm, with reduced complexity. Section 6.3.3 discusses the connection with an upper triangular factorization of the involved matrix, which might come in handy later on when inverting structured rank matrices. Numerical stability issues are discussed in Subsection 6.3.4. Section 6.4 contains examples related to different types of structured rank matrices to...

Share