Warning: pg_query(): Query failed: ERROR: unexpected chunk number 1 (expected 0) for toast value 29512337 in pg_toast_2619 in /dati/webiit-old/includes/database.pgsql.inc on line 138 Warning: ERROR: unexpected chunk number 1 (expected 0) for toast value 29512337 in pg_toast_2619 query: SELECT data, created, headers, expire, serialized FROM cache_page WHERE cid = 'https://www-old.iit.cnr.it/node/12087' in /dati/webiit-old/includes/database.pgsql.inc on line 159 Warning: pg_query(): Query failed: ERROR: unexpected chunk number 1 (expected 0) for toast value 29512337 in pg_toast_2619 in /dati/webiit-old/includes/database.pgsql.inc on line 138 Warning: ERROR: unexpected chunk number 1 (expected 0) for toast value 29512337 in pg_toast_2619 query: SELECT data, created, headers, expire, serialized FROM cache_page WHERE cid = 'https://www-old.iit.cnr.it/node/12087' in /dati/webiit-old/includes/database.pgsql.inc on line 159 Superfast solution of Toeplitz-like systems | IIT - CNR - Istituto di Informatica e Telematica
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.


2011

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