Matrix Computations and Semiseparable Matrices
Eigenvalue and Singular Value Methods
Publication Year: 2008
Published by: The Johns Hopkins University Press
Title Page, Copyright Page
Download PDF (119.5 KB)
Download PDF (90.3 KB)
In this volume of the book, eigenvalue problems related to structured rank matrices are studied. The first volume considered mainly two goals: introducing structured rank matrices and investigating their properties, and secondly discussing several methods for solving systems of equations involving these structured rank...
Download PDF (86.6 KB)
Chapter 1 Introduction to semiseparable matrices
Download PDF (241.2 KB)
This chapter is included to make the book consistent and for those who didn’t read the first volume of this book entitled: ‘Matrix Computations and Semiseparable Matrices: Linear Systems’. For the people who did read the first volume, it might...
Part I The reduction of matrices
Download PDF (83.6 KB)
The first and second part of this book focus on the translation of traditional eigenvalue algorithms, based on sparse matrices, towards a structured rank approach. Let us specify this. For example, a traditional method for computing the eigenvalues of a symmetric matrix first transforms this symmetric matrix to a similar tridiagonal one, and then the eigenvalues of this similar tridiagonal...
Chapter 2 Algorithms for reducing matrices
Download PDF (423.4 KB)
It is known from the introductory chapter that semiseparable and tridiagonal matrices are closely related to each other. Invertible semiseparable matrices have as an inverse a tridiagonal matrix and vice versa. One might wonder whether this close relation between these two classes of matrices can be extended, for example...
Chapter 3 Convergence properties of the reduction algorithms
Download PDF (450.9 KB)
In the previous chapter, several types of reduction algorithms to either sparse or structured rank matrices were presented. It was stated there that the orthogonal similarity reduction to a similar semiseparable matrix could also be achieved by first transforming the matrix to a similar tridiagonal one and then transforming the tridiagonal matrix into a similar semiseparable one. It is a known result...
Chapter 4 Implementation of the algorithms and numerical experiments
Download PDF (831.3 KB)
In Chapter 2 we proposed several algorithms to reduce matrices to semiseparable form. To calculate the computational complexity of these algorithms we always assumed that the part of the matrix already in semiseparable form could be represented in an efficient way. This efficient representation will be used in this chapter,...
Part II QR-algorithms (eigenvalue problems)
Download PDF (90.5 KB)
Traditional QR-algorithms for computing the eigenvalues of (dense) matrices consist of two main parts. In a first part the matrices in question are reduced to a specific form, which will be advantageous in the second part. This reduction was considered in the first part of this book, namely the reductions to semiseparable...
Chapter 5 Introduction: traditional sparse QR-algorithms
Download PDF (243.9 KB)
This chapter is merely a repetition of the theory of QR-algorithms for sparse matrices. All the ingredients needed for designing such algorithms will be investigated. In a first section we will reconsider what is meant by a QR-factorization and a QR-algorithm. It turns out that applying the QR-algorithm directly onto dense...
Chapter 6 Theoretical results for structured rank QR-algorithms
Download PDF (320.4 KB)
In Chapter 7 of this book we will design different types of implicit QR-algorithms for matrices of semiseparable form. More precisely the chasing techniques will be developed in that chapter. Before we are able to construct these algorithms some theoretical results are needed. In this chapter we will provide answers...
Chapter 7 Implicit QR-methods for semiseparable matrices
Download PDF (388.9 KB)
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...
Chapter 8 Implementation and numerical experiments
Download PDF (424.3 KB)
In the previous chapters of this part, different theoretical results were combined and developed in order to build implicit QR-algorithms for semiseparable matrices. We know how such an algorithm should be designed. Also details on the implementation of the designed algorithms will be given. In the previous chapters, nothing was...
Chapter 9 More on QR-related algorithms
Download PDF (705.7 KB)
In the previous chapters, the basic traditional QR-algorithms for structured rank matrices were designed. The singular value decomposition and single shift QR methods for semiseparable, semiseparable plus diagonal and Hessenberg-like matrices...
Part III Some generalizations and miscellaneous topics
Download PDF (78.1 KB)
In the first two parts of this book the standard algorithms for computing the eigendecomposition of matrices were discussed. Reduction algorithms to structured rank matrices were discussed, as well as the accompanying QR-methods. In this part we will discuss some topics that are slightly more general than the ones from...
Chapter 10 Divide-and-conquer algorithms for the eigendecomposition
Download PDF (1.1 MB)
This chapter will be devoted to the description of divide-and-conquer techniques to compute the eigendecomposition of some special symmetric structured rank matrices. More precisely we will describe divide-and-conquer methods for both tridiagonal and quasiseparable matrices. The divide-and-conquer techniques for structured...
Chapter 11 A Lanczos-type algorithm and rank revealing
Download PDF (274.5 KB)
In this chapter we will present two main topics. First we will present a Lanczos version for constructing a semiseparable matrix similar to a given symmetric matrix, and secondly we will show how one can exploit the rank-revealing properties of the...
Part IV Orthogonal (rational) functions (Inverse eigenvalue problems)
Download PDF (94.9 KB)
Eigenvalue problems and inverse eigenvalue problems for structured rank matrices are connected to several other domains of mathematics. In this part, we show the relationship between the inverse eigenvalue problem involving different structured rank matrices and orthonorma...
Chapter 12 Orthogonal polynomials and discrete least squares
Download PDF (250.3 KB)
...the orthonormal basis and the Fourier coefficients. As we shall see in the following sections, the parameters of the recurrence relation for the sequence of these orthonormal polynomials can be stored in a structured rank matrix, more precisely...
Chapter 13 Orthonormal polynomial vectors
Download PDF (284.9 KB)
In the previous chapter we have studied orthonormal polynomials and least squares polynomial approximants with respect to a discrete inner product. In this chapter, we investigate the generalization into orthonormal polynomial vectors. In this case the parameters of the recurrence relation are contained in a matrix with a...
Chapter 14 Orthogonal rational functions
Download PDF (285.0 KB)
...However, like the polynomial (Vandermonde) case , these fast algorithms turn out to be quite sensitive to roundoff errors so that the computed functions are far from orthogonal. Therefore, in this chapter we...
Chapter 15 Concluding remarks & software
Download PDF (91.9 KB)
In several chapters of this book implementations of various algorithms were discussed. Several of these methods are implemented and freely available for download at the following site: http://www.cs.kuleuven.be/∼mase/books/ The package containing several routines related...
Download PDF (157.0 KB)
Download PDF (420.1 KB)
Download PDF (258.2 KB)
Page Count: 520
Illustrations: 93 line drawings
Publication Year: 2008