IIT Home Page CNR Home Page

A Divide and Conquer Algorithm for the Superfast solution of Toeplitz-like Systems

In this paper a new O(N log3 N) solver for N × 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 [R. R. Bitmead and B. D. O. Anderson, Linear Algebra Appl., 34 (1980), pp. 103–116; M. Morf, Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, 1980, pp. 954–959], 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×2 block system with blocks of half size. This idea is the one used in [M. Stewart, SIAM J. Matrix Anal. Appl., 25 (2003), pp. 669–693] 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.

SIAM. J. Matrix Anal. & Appl., 2012

Autori esterni: Grazia Lotti (Department of Mathematics, Universita’ di Parma, 43100 Parma, Italy ), Ornella Menchi (Department of Computer Science, Universita’ di Pisa, 56127 Pisa, Italy)
Autori IIT:

Tipo: Articoli su riviste ISI
Area di disciplina: Mathematics
Da pagina 1039 a pagina 1056

Attività: Metodi numerici per problemi di grandi dimensioni