Институт вычислительной математики
и математической геофизики

The International Conference on Computational Mathematics


Computational algebra

Fast algorithms for Structured Matrices and Applications

Olshevsky V.

Department of Mathematics (Storrs)

Many matrices encountered in various applications often have a special structure, e.g., a Toeplitz, a Hankel, a Vandermonde, a Cauchy, or a Pick structure, etc. It is now well-understood that exploiting such structures typically allows us to design efficient algorithms, i.e., those outperforming standard algorithms in terms of the amount of computations, or accuracy, or amenability to parallel implementations. Time permitting, I shall try to briefly describe a number of recent results: - a new and fairly general algorithm for fast structured matrix-vector multiplication. It generalizes several well-known algorithms, such as the FFT, an algorithm for computing convolutions, and methods for polynomial and rational interpolation, as well as for polynomial and rational multi-point evaluation; - a new superfast algorithm for solving passive tangential interpolation problems of the Nevanlinna-Pick type; - how bad are Pick matrices and how they can be effectively preconditioned by Cauchy matrices; - a new algorithm for factorizations of p.d. Hankel matrices that is the first provably backward stable algorithm; - a new algorithm for factorization of matrices with what we suggest to call ``Hessenberg displacement structure;'' - a new algorithm for list decoding of Reed-Solomon codes.

Note. Abstracts are published in author's edition

Mail to Webmaster
|Home Page| |English Part| [SBRAS]
Go to Home
© 1996-2000, Siberian Branch of Russian Academy of Sciences, Novosibirsk
    Last update: 06-Jul-2012 (11:52:06)