Fast argorithms for matrices with low displacement rank structure

Researchers

and formerly...

Collaboration with

formerly with the Academy of Sciences (Prague, Czech Republic).

Description

The solution of most problems in applied mathematics reduces to solving a linear algebra problem: a set of linear equations or a (generalized) eigenvalue problem. The matrices involved are often structured, e.g., discretizing a partial differential equation leads to a sparse matrix having a lot of zero elements. Another type of structure is exhibited by the so-called low-displacement rank matrices. When applying a displacement operator on the matrix, the result is another matrix of low rank. Examples of these are Hankel, Toeplitz, Vandermonde, Cauchy, ... matrices. In structured linear algebra one tries to exploit the structure to reduce the computational complexity. E.g., a Toeplitz n by n system can be solved in a fast way using O( n² ) floating point operations (flops) and even superfast using Fast Fourier Transformations in O(n log² n) flops compared to the `classical methods' like Gaussian elimination involving O( n³ ) flops. However, several of these methods are not numerically stable. There are several remedies. One possibility is to use `look-ahead'. The fast methods solve systems coupled to submatrices of increasing order of the original structured one.
Look-ahead methods jump over the ill-conditioned subsystems.
Another cure is to transform the original problem into another structured one where pivoting can be used without destroying the structure. The study of the connections between different classes of low-displacement rank matrices plays a significant role. A third way, is to embed the original problem into a larger one which can be solved by the 'classical' methods. After a finite number of steps the solution is found. A very important set are those methods approximating the solution in an iterative way. Our research concentrates on the study of all these different methods and their connections. The insight is interpreting the structured problems as belonging to the field of rational approximation, orthogonal systems, linear system theory and signal processing.
The fast solution is essentially based on recurrence relations between the solutions of subsystems. These recurrence relations can be viewed as relations between rational interpolants, orthogonal polynomials, minimal partial realizations, digital filters, etc. By the interplay of these different fields, the best of all of them can be combined to design numerically stable and fast methods not only for low displacement rank problems as such but also for the corresponding problems in all the other fields. Also more theoretical results appear easily from this unified viewpoint, e.g., the generalization of the companion matrix from scalar to matrix polynomials. This leads to insight into linear difference and differential equations whose characteristic polynomial is a matrix instead of a scalar.