A Divide and Conquer Algorithm for the Superfast solution of Toeplitz-like Systems (Articolo in rivista)

Type
Label
  • A Divide and Conquer Algorithm for the Superfast solution of Toeplitz-like Systems (Articolo in rivista) (literal)
Anno
  • 2012-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1137/110851407 (literal)
Alternative label
  • Favati Paola, Lotti Grazia, Menchi Ornella (2012)
    A Divide and Conquer Algorithm for the Superfast solution of Toeplitz-like Systems
    in SIAM journal on matrix analysis and applications (Print)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Favati Paola, Lotti Grazia, Menchi Ornella (literal)
Pagina inizio
  • 1039 (literal)
Pagina fine
  • 1056 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#altreInformazioni
  • ID_PUMA: cnr.iit/2012-A0-023 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 33 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroFascicolo
  • 4 (literal)
Note
  • ISI Web of Science (WOS) (literal)
  • Scopu (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • CNR-IIT, Pisa, Italy; Department of Mathematics, Università di Parma, Italy; Department of Computer Science, Pisa, Italy (literal)
Titolo
  • A Divide and Conquer Algorithm for the Superfast solution of Toeplitz-like Systems (literal)
Abstract
  • 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. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
Insieme di parole chiave di
data.CNR.it