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 [3, 18], 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 same one used in [22] 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.

A divide and conquer algorithm for the superfast solution of Toeplitz-like systems / Favati, P; Lotti, Grazia; Menchi, O.. - In: SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. - ISSN 0895-4798. - 33-34:(2012), pp. 1039-1056. [10.1137/110851407]

A divide and conquer algorithm for the superfast solution of Toeplitz-like systems

LOTTI, Grazia;
2012-01-01

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 [3, 18], 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 same one used in [22] 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.
2012
A divide and conquer algorithm for the superfast solution of Toeplitz-like systems / Favati, P; Lotti, Grazia; Menchi, O.. - In: SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. - ISSN 0895-4798. - 33-34:(2012), pp. 1039-1056. [10.1137/110851407]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11381/2552445
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact