IIT Home Page CNR Home Page

Superfast solution of Toeplitz-like systems

In this paper a new $O(N \,\log^3N)$ solver for $N\times N$ Toeplitz-like systems,
based on a divide and conquer technique, is presented. Similarly to the
superfast algorithm MBA for the inversion of a Toeplitz-like matrix
\cite{Bit, morf}, it exploits the displacement properties.
In order to avoid the well known numerical instability of the explicit
inversion,  the new algorithm relies on the triangular factorization and
back-substitution formula for the system seen as a $2\times 2$ block system
with blocks of half size. The same idea has been used in \cite{Ste1} to improve
the numerical stability of superfast methods based on the generalized Schur
algorithm for positive definite Toeplitz matrices,
but the algorithm we propose can be applied also to nonsymmetric  Toeplitz-like
systems. The stability of the algorithm is examined through numerical experiments.


Autori esterni: Grazia Lotti (Dip. di Matematica, University of Parma), Ornella Menchi (Dip. di Informatica, University of Pisa)
Autori IIT:

Tipo: TR Rapporti tecnici
Area di disciplina: Mathematics
IIT TR-24-2011

Attività: Metodi numerici per problemi di grandi dimensioni