# Matrix Computations and Semiseparable Matrices

Eigenvalue and Singular Value Methods

Publication Year: 2008

Published by: The Johns Hopkins University Press

#### Cover

#### Title Page, Copyright Page

#### Contents

Download PDF (119.5 KB)

pp. v-x

#### Preface

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

#### Notation

Download PDF (86.6 KB)

pp. xv

#### Chapter 1 Introduction to semiseparable matrices

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

#### Part I The reduction of matrices

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

#### Chapter 2 Algorithms for reducing matrices

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

#### Chapter 3 Convergence properties of the reduction algorithms

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

#### Chapter 4 Implementation of the algorithms and numerical experiments

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

#### Part II *QR*-algorithms
(eigenvalue problems)

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

#### Chapter 5 Introduction: traditional
sparse *QR*-algorithms

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

#### Chapter 6 Theoretical results for
structured rank
*QR*-algorithms

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

#### Chapter 7 Implicit *QR*-methods for
semiseparable matrices

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

#### Chapter 8 Implementation and numerical experiments

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

#### Chapter 9 More on *QR*-related
algorithms

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

#### Part III Some generalizations and miscellaneous topics

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

#### Chapter 10 Divide-and-conquer algorithms for the eigendecomposition

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

#### Chapter 11 A Lanczos-type algorithm and rank revealing

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

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

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

#### Chapter 12 Orthogonal polynomials and discrete least squares

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

#### Chapter 13 Orthonormal polynomial vectors

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

#### Chapter 14 Orthogonal rational functions

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

#### Chapter 15 Concluding remarks & software

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

#### Bibliography

Download PDF (157.0 KB)

pp. 471-486

#### Author/Editor Index

Download PDF (420.1 KB)

pp. 487-491

#### Subject Index

Download 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