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

Chapter 2 The representation of semiseparable and related matrices In the previous chapter it was shown that, when one wants to solve the eigenvalue problem by means of the QR-algorithm, the definition of semiseparable matrices with generators has some disadvantages. Therefore we proposed the more elaborate definition, in terms of the structured rank. This class of semiseparable matrices is closed under any suitable chosen norm, just as the class of quasiseparable and tridiagonal matrices is closed. However, these classes of matrices can only be used efficiently if we have also an efficient representation as indicated by Corollary 1.11. The representations for the different classes of matrices as defined in the previous chapter are the subject of this chapter. Different types of representations will be investigated, e.g., the generator representation , the representation with a diagonal and a subdiagonal, the representation with a sequence of Givens transformations and a vector and finally the quasiseparable representation. In fact all the above-mentioned representations are just specific parameterizations for a part of a matrix having low rank. Hence we can use all the representations above for representing all the different classes of matrices previously defined. Moreover we will briefly discuss the question: “Are there more representations then the ones discussed in this chapter?” Before defining the different types of representations, we indicate properly what in this book is meant by a ‘representation’. We base this definition on the representation of tridiagonal matrices, using only the diagonal, subdiagonal and the superdiagonal. The viewpoint of a representation is ‘just’ a representation is also clarified. In brief one could summarize this as stating that the choice of a representation for a specific matrix depends on external parameters and is not necessarily always linked to the intrinsic matrix structure. Under external parameters, one might classify the problem, the application one is dealing with, knowledge about the problems origin, ... In Sections 2.2 to 2.5, four types of representations for the symmetric case are considered. One considers the generator representation, the diagonal subdiagonal representation, the Givens-vector representation and the quasiseparable represen53 54 Chapter 2. The representation of semiseparable and related matrices tation. Each of these representations is investigated with regard to the definition of a representation as proposed before, and we try to use this representation for ef- ficiently representing the class of semiseparable matrices. Moreover, for every type of representation we investigate in which way the representation can be used for representing the other classes of structured rank matrices from the first chapter. We conclude the part of the symmetric representations with Section 2.6, containing some examples. The nonsymmetric case is more difficult than the symmetric one and is therefore covered in the Sections 2.7 to 2.9. The diagonal subdiagonal representation is not covered anymore, as it will not be used for representing nonsymmetric semiseparable or related matrices. The last type of representation considered is a special type of representation for the nonsymmetric case, the so-called decoupled representation. This representation explicitly does not take into account the extra structure posed on the diagonal by, e.g., semiseparable and generator representable semiseparable matrices. In fact this representation uses order O(n) more parameters, but it covers also a slightly more general class than the class of semiseparable and/or generator representable semiseparable matrices. This representation is also quite often used for actual implementations of algorithms related to structured rank matrices. In the last section of this chapter, several algorithms are presented for the different types of representations. Firstly, it is shown that the different representations for a specific matrix admit an O(n)14 multiplication between this matrix and a vector. Secondly, some manners are presented to change from one representation to another. ✎ This chapter focuses on some different representations for structured rank parts in matrices. Subsection 2.1.3 briefly explains in words the different types of representation. This gives a good idea of the different types. The representations are first applied to semiseparable matrices to clearly distinguish between the types of representations. At the end of each section covering a representation, the representation is adapted for quasiseparable, semiseparable plus diagonal and other matrices. In Section 2.2 the generator representation is explained. Equation (2.1) presents the structure of the matrix in case this representation is used. We remark that the generator representation...

Share