OT00 research project


OT-00-16 SLAP: Structured Linear Algebra Package (1-10-2000 to 30-09-2004)

Short description

To model a speech or music signal, use is made of the frequency content of these signals (spectral data). By making a simple model of the signal, it is possible to compress and process the signal digitally. Such a model can be obtained by solving a system of equationswith a special structure. The matrix of an arbitrary system of n equations usually contains n*n different numbers. In our model there turn out to be only n different elements because the matrix of the system has a so called Toeplitz structure.

There are many other similar examples for processing medical data, for images, in digital communication, and more generally in the modelling of a system, where matrices of this structure or some other structure do show up. They can be written with a number of parameters that is lower than n*n.

Researchers

Sponsored by

OT Research Fund K.U.Leuven

With the increase in dimension (n can be several thousands up to 1 million) of the applications of such problems, these problems can not be solved in a reasonable time, not even on the fastest available computers. Therefore specially designed methods that exploit the structure of the problem have to be used to decrease the computational time by at least an order of magnitude.

Also, overdetermined problems are being considered. This means that there are many more equations than there are unknowns. For example in antenna problems on can have some hundreds of equations while there are only 10 unknowns. Also here the special structure of the problem should be exploited.

There do exist a number of such techniques that work well on subclasses of such structured problems. Most often the theory does exist, but software is not really available. Recently, many new techniques and ideas emerged in the literature that should also be implemented. many so called "fast" and "superfast" algorithms are not numerically stable. This means that the simplicity (and speed) of the computations has been obtained at the expense of accuracy. The design of fast and accurate algorithms is the big challenge at this very moment.

The research group NALAG has already contributed to the development of the theory and the software for several such problems. The group has expertise not only in this kind of problems, but also in related problems that appear in a completely different context like orthogonal polynomials, rational approximation etc. Therefor ideas from these different areas can be combined to design good algorithms for structured problems.

In this project, the group will elaborate on this expertise and valorise it. An inventory will be made of this kind of problems with structure and of problems that can be reduced to it. The application does not only dictates the nature of the data and the structure. For some applications some parameters may or may not be important, and may therefor be required to be computed explicitly. Sometimes these problems appear as subproblems of larger ones, by which they are tied by strict side conditions.

The next step is the design of a software package where the fundamental building blocks of such a family of problems are worked out. The most common problems should be solved by a robust numerically sound routine. For a number of standard problems, the theory has already been set up, so that now is the time to develop the software for it. For other problems, especially the overdetermined systems, there is a lot of research that should still be done to arrive at good algorithms. Even for problems for which a certain analysis has been published, it requires a lot of brain teasing before a operational software routine will result.