We cannot verify your location
Browse Book and Journal Content on Project MUSE

Matrix Computations and Semiseparable Matrices

Eigenvalue and Singular Value Methods

Raf Vandebril, Marc Van Barel, and Nicola Mastronardi

Publication Year: 2008

The general properties and mathematical structures of semiseparable matrices were presented in volume 1 of Matrix Computations and Semiseparable Matrices. In volume 2, Raf Vandebril, Marc Van Barel, and Nicola Mastronardi discuss the theory of structured eigenvalue and singular value computations for semiseparable matrices. These matrices have hidden properties that allow the development of efficient methods and algorithms to accurately compute the matrix eigenvalues. This thorough analysis of semiseparable matrices explains their theoretical underpinnings and contains a wealth of information on implementing them in practice. Many of the routines featured are coded in Matlab and can be downloaded from the Web for further exploration.

Published by: The Johns Hopkins University Press

Title Page, Copyright Page

pdf iconDownload PDF (71.4 KB)


pdf iconDownload PDF (119.5 KB)
pp. v-x

read more


pdf iconDownload PDF (90.3 KB)
pp. xi-xiv

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...


pdf iconDownload PDF (86.6 KB)
pp. xv-

read more

Chapter 1 Introduction to semiseparable matrices

pdf iconDownload PDF (241.2 KB)
pp. 1-14

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...

read more

Part I The reduction of matrices

pdf iconDownload PDF (83.6 KB)
pp. 15-18

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...

read more

Chapter 2 Algorithms for reducing matrices

pdf iconDownload PDF (423.4 KB)
pp. 19-66

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...

read more

Chapter 3 Convergence properties of the reduction algorithms

pdf iconDownload PDF (450.9 KB)
pp. 67-108

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...

read more

Chapter 4 Implementation of the algorithms and numerical experiments

pdf iconDownload PDF (831.3 KB)
pp. 109-148

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,...

read more

Part II QR-algorithms (eigenvalue problems)

pdf iconDownload PDF (90.5 KB)
pp. 149-154

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...

read more

Chapter 5 Introduction: traditional sparse QR-algorithms

pdf iconDownload PDF (243.9 KB)
pp. 155-170

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...

read more

Chapter 6 Theoretical results for structured rank QR-algorithms

pdf iconDownload PDF (320.4 KB)
pp. 171-198

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...

read more

Chapter 7 Implicit QR-methods for semiseparable matrices

pdf iconDownload PDF (388.9 KB)
pp. 199-238

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...

read more

Chapter 8 Implementation and numerical experiments

pdf iconDownload PDF (424.3 KB)
pp. 239-276

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...

read more

Chapter 9 More on QR-related algorithms

pdf iconDownload PDF (705.7 KB)
pp. 277-362

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...

read more

Part III Some generalizations and miscellaneous topics

pdf iconDownload PDF (78.1 KB)
pp. 363-366

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...

read more

Chapter 10 Divide-and-conquer algorithms for the eigendecomposition

pdf iconDownload PDF (1.1 MB)
pp. 367-392

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...

read more

Chapter 11 A Lanczos-type algorithm and rank revealing

pdf iconDownload PDF (274.5 KB)
pp. 393-410

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...

read more

Part IV Orthogonal (rational) functions (Inverse eigenvalue problems)

pdf iconDownload PDF (94.9 KB)
pp. 411-414

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...

read more

Chapter 12 Orthogonal polynomials and discrete least squares

pdf iconDownload PDF (250.3 KB)
pp. 415-428

...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...

read more

Chapter 13 Orthonormal polynomial vectors

pdf iconDownload PDF (284.9 KB)
pp. 429-446

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...

read more

Chapter 14 Orthogonal rational functions

pdf iconDownload PDF (285.0 KB)
pp. 447-466

...However, like the polynomial (Vandermonde) case [132], 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...

read more

Chapter 15 Concluding remarks & software

pdf iconDownload PDF (91.9 KB)
pp. 467-470

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...


pdf iconDownload PDF (157.0 KB)
pp. 471-486

Author/Editor Index

pdf iconDownload PDF (420.1 KB)
pp. 487-491

Subject Index

pdf iconDownload PDF (258.2 KB)
pp. 492-498

E-ISBN-13: 9780801896804
E-ISBN-10: 0801896800
Print-ISBN-13: 9780801890529
Print-ISBN-10: 0801890527

Page Count: 520
Illustrations: 93 line drawings
Publication Year: 2008