Separable type representations of matrices and fast algorithms
Almost five years after Israel Gohberg passed away in 2009, his coauthors have finished this extensive round-up of their results on separable matrices. It has grown out to a thick manuscript that has been published as two volumes in the Birkhäuser series Operator Theory: Advances and Applications, Vols. 234, 235.
It all started with the Toeplitz and Hankel matrices for which special algorithms existed in diverse branches of mathematics. The Levinson algorithm for Toeplitz matrices was published in 1945 and later connected with the Schur algorithm from 1917 and with Szego recurrence relation for orthogonal polynomials on the unit circle from 1921. A similar history is connected with Hankel matrices which can be connected with recurrence relations for orthogonal polynomials on the real line and with continued fractions. Systems with Hankel or Toeplitz matrices have the property that they can be stored in O(n) memory and solved in O(n²) computations rather than the usual O(n²) memory and O(n³) computations for general matrices.
Around mid 1980s a new interest in such fast algorithms was enforced by the applications in signal processing and systems theory. Soon other matrices were discovered having a so-called low displacement rank, which could also be stored by some generators in O(n) memory and inverted in O(n²) computations. So the notion grew of matrices that were sparse not because they contain many zeros, but sparse because the information they store is sparse, although not by a visible pattern. This brought about a flourishing research area in linear algebra studying matrices that have some structured information that can be exploited for efficient storage and computation. The separable matrices as discussed in these books are such a class.
The simplest form are the separable matrices. That is when A = UV* with A of size N × N but U and V of size N × n with n ≪ N. Only 2nN elements are needed to store it. Direct generalizations are semi-separable matrices whose lower and upper triangular parts are the lower and upper triangular parts of possibly different separable matrices. Also quasi-separable matrices are characterized by the maximal rank that a submatrix can have when all its elements are in the upper or lower triangular part of the matrix. There is often a relation with classical structures like being the inverse of a tridiagonal matrix, etc. Unitary upper or lower Hessenberg matrices is another class of structured matrices. The latter can be represented as a sequence of 2 by 2 Givens rotations applied to certain rows or columns. This is again a useful sparse representation. Some of these problems are related to minimal rank matrix completion problems: find the missing elements in a partially prescribed matrix that keeps the rank as small as possible.
The authors have published about this subject during the last decades and their results are collected in these two volumes. In the first volume the basic elements are collected: definitions, fast matrix vector and matrix matrix multiplication, LDU, QR and other factorizations, inversion etc. for all kinds of structured matrices: separable, semiseparable, semiseparable-plus-diagonal, quasiseparable, Green matrices, unitary Hessenberg,... Much attention is given to obtaining the proper generators and to the completion problem.
The second volume is reserved for eigenvalue problems. The structure of quasipseparable matrices, divide and conquer techniques, and QR based methods for Hermitean and unitary Hessenberg matrices, and for companion matrices as a special case.
This is mainly a survey of the results of the authors. The two books are intimately coupled. It has no sense to start with volume 2 without having volume 1 available. The numbering of parts and chapters in volume 2 is continuing the numbering of volume 1. A similar two volume set was published before by R. Vandebril, M. Van Barel, and N. Mastronardi. Matrix Computations and Semiseparable Matrices. Volume I: Linear Systems and Volume II: Eigenvalues and Singular Value Methods (The John Hopkins University Press, Baltimore, 2008). Research is still extending the algebraic analysis as well as the numerical implementation of the algorithms for classes of matrices with structured information.