SMA research project



SMA: Structured Matrices and their Applications (01-01-2001 - 31-12-2004)


Sponsored by

FWO project G.0078.01

Short description

A lot of important practical problems can be transformed into equivalent problems in linear algebra. The matrices that appear in this way often have a special structure. For example, mathematical models of a lot of physical processes are based on partial differential equations. After discretization these equations can be tackled on a computer in a fast way by taking into account the sparse structure of the corresponding matrices, i.e., the large number of zero entries in the matrix. Different mathematical models lead to equivalent matrices having a completely different structure such as Toeplitz, Hankel or other related matrices. These matrices also appear in time series analysis, system identification and signal processing (e.g., speech decoding, deconvolution). Toeplitz matrices are matrices having the same entries on each diagonal. In other words, the element on row i and column j of a Toeplitz matrix is of the form ti-j. In general a Toeplitz matrix does not contain zeros. In this case the structure is not characterized by the position of the zeros but by the fact that the Toeplitz matrix can be written in terms of a small number of parameters (e.g., the numbers tk) where the number of parameters increases linearly with the size of the matrix. For an arbitrary matrix there is no connection between the different entries and the number of parameters increases quadratically with the size of the matrix. Other examples of structured matrices that appear in many applications are: the Hankel matrix having entries hi+j, the Vandermonde matrix having entries zji, the Loewner matrix having entries (ci-dj)/(yi-zj), ...

Researchers

In collaboration with

Related research

This project has the following aims: to analyse the properties of the above mentioned and other types of structured matrices, to explore the connections between different kinds of structured matrices, to solve the linear algebra problems in which these matrices appear in a fast and accurate way, to interpret these results in other domains of (numerical) mathematics and to apply the knowledge thus gained to applications. Because these structured linear algebra problems (solving systems of equations, eigenvalue and singular value decompositions, (total) least squares,...) are kernel problems in a variety of applications of system identification and signal processing, the attention will be focused on the development of numerically robust and efficient software for these computations. Selected basic modules will be made available to the users via web computing.

Proposed research:
  • Exploit the complementary knowledge present in NALAG and SISTA/COSIC.
  • Solving structured TLS problems, which arise in input-output and time series modelling, involves to solve a linearly constrained least-squares problem recursively. Special algorithms will be developed which exploit the structure (consisting of (block) Toeplitz and Hankel, diagonal and zero submatrices) of the kernel data matrix, thereby improving the computational speed with a factor 1.000 to 10.000 . The stability and the reliability of the new TLS algorithms will be investigated.
  • Especially kernel problems in system identification, control and signal processing, in which structured matrix problems frequently arise, will be tackled. In identification we mention 4 different types of data collection: impulse response, input-output pairs, frequency response and covariance data. In each of those, the identification problem can be rewritten in terms of structured matrix problems for which fast decompositions are required (increasing the speed with a factor 100 to 1000). For these problems structure preserving algorithms will be developed. Special attention wil be focused on subspace identification, a popular technique in mathematical modelling where the matrices can be quite large (e.g., up to multiples of 1000). We will develop fast and stable algorithms for the most time-consuming part, namely the QR factorization of the concatenated ill-conditioned input-output block Hankel matrices. A second field is the analysis and design of special problems in systems and control theory (optimal feedback, periodic systems) which requires the eignenvalue decomposition of cyclic, Hamiltonian and symplectic matrices. For those problems we will develop structure preserving software which improve the numerical accuracy as well as the computational efficiency. Finally, we mention the analysis of closeness and robustness problems in which one needs to solve optimisation problems with constraints related to some particular structure. This includes structured TLS and structured singular value problems, for which special algorithms will be developed.
  • In addition to the study of the numerical properties, we will implement the new algorithms into numerically reliable and efficient software and apply these to practical problems such as online speech compression, speech coding, quantification of individual MRS signals and images, etc. Moreover, the algorithms will be integrated in software packages such as SLICOT and in toolboxes for system identification (N4SID). In order to improve user-friendliness, these algorithms will also be integrated into Matlab and Scilab via appropriate MEX files. Moreover, the basic modules which solve kernel problems such as the computation of the QR factorisation of block Hankel/Toeplitz matrices, will be implemented on the web and made available to the users via web computing.
  • We will develop software for specific applications but also general purpose algorithms and techniques that can be used in a wide variety of applications (rational approximations, moment problems, etc).
keyboard_arrow_up