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

и математической геофизики

# The International Conference on Computational Mathematics

ICCM-2004

June, 21-25, 2004
Novosibirsk, Academgorodok

## Abstracts

*Computational algebra*

## Fast algorithms for Structured Matrices and Applications

**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*

© 1996-2000, Siberian Branch of Russian Academy of Sciences, Novosibirsk

Last update: 06-Jul-2012 (11:52:06)