Matrix Computations and Semiseparable Matrices: Eigenvalue and Singular Value Methods

Chapter 15 Concluding remarks & software

Chapter 15 Concluding remarks & software 15.1 Software 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 to semiseparable matrices is called SSPack, the Semiseparable Software Package. The package is still under development, hence it is good to check the site on a regular base. Important to remark is that currently the MaSe-team is implementing several of the routines in C++, using thereby GLAS (Generic Linear Algebra Software), which exploits BLAS and so forth. The above site will also discuss progress in this project. Let us provide an example of a routine in Matlab, to illustrate the global package. For example the routine: CSS: Construction of a semiseparable matrix Providing Matlab the following command: >> help CSS will provide the following output: % CSS Construction of a semiseparable matrix % % [G,d]=CSS(S) % produces the representation of a semiseparable % matrix from the symmetric matrix S. % The fastest Householder implementation is used. % G represents a sequence of givens % d represents a diagonal % % [G,d]=CSS(S,’h’) % performs the computation with a more stable, but 467 468 Chapter 15. Concluding remarks & software % slower Householder implementation. % % [G,d]=CSS(S,’g’) % performs the computation with Givens transformations. % This is the most stable but also the slowest. % % Software of the MaSe - Group % mase@cs.kuleuven.be % Revision Date: 16/12/2003 This routine transforms a symmetric matrix into a similar semiseparable one. The package contains many other implementations of proposed algorithms, such as for example the multishift QR-step, the singular value decomposition based on upper triangular semiseparable matrices, the divide-and-conquer algorithm and many others. For example the routine which computes the eigenvalues and eigenvectors of semiseparable matrices is of the following form. % EIGSS Eigenvalues and eigenvectors of semiseparable matrices % % E = EIGSS(G,d,cutoff) is a vector containing the eigenvalues of % the symmetric semiseparable matrix S constructed with G,d. % (Check BSS and CSS for info on the representation G,d.) % Remark that the matrix has to be in unreduced form. % (Check REDSS for info about unreducedness.) % % % [V,D] = EIGSS(G,d,cutoff) produces a diagonal matrix D of % eigenvalues and a full matrix V whose columns are the % corresponding eigenvectors so that S*V = V*D, % with S the semiseparable matrix constructed with G,d. % % The variable cutoff stands for the cutting off criterion. % If the subdiagonal element is smaller than cutoff the % corresponding eigenvalue is separated. % % % Software of the MaSe - Group % mase@cs.kuleuven.be % Revision Date: 30/05/2003 15.2 Conclusions The first volume of this book focused onto solving systems of linear equations, involving structured rank matrices. This volume was dedicated to direct and inverse eigenvalue problems related to and based on, structured rank matrices. 15.2. Conclusions 469 The first part of the book discussed different algorithms for transforming matrices to structured rank form. Transitions to semiseparable, semiseparable plus diagonal , Hessenberg-like, upper triangular semiseparable form were explored. Moreover also the convergence properties of these methods were studied extensively, showing how to tune this convergence. Being able to transform matrices to structured rank form is not enough to compute eigenvalues and/or singular values. The second part of the book discusses therefore all necessary tools and theoretical results for developing QR-algorithms, computing the eigenvalues of the previously mentioned structured rank matrices. An extra chapter also presented a new kind of algorithm for computing the eigendecomposition via a QH-factorization. The third part of the book briefly discussed some miscellaneous topics such as the reduction to semiseparable form in an iterative (Lanczos-like) way and how to exploit the rank-revealing properties of the reduction algorithms. Also the divideand -conquer algorithm for computing the eigendecomposition was discussed. The fourth part of the book discussed some inverse eigenvalue problems, showing relations between structured rank matrices and orthogonal polynomials. We hope that the two volumes give the reader a thorough introduction in the field of structured rank matrices and can lead to a standardization of the notation in this strongly evolving field of research and applications. This page intentionally left blank ...