Back to Search
Start Over
A DIVIDE AND CONQUER ALGORITHM FOR THE SUPERFAST SOLUTION OF TOEPLITZ-LIKE SYSTEMS.
- Source :
-
SIAM Journal on Matrix Analysis & Applications . 2012, Vol. 33 Issue 4, p1039-1056. 18p. - Publication Year :
- 2012
-
Abstract
- In this paper a new O(N log³ N) solver for N x 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 2x2 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954798
- Volume :
- 33
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Matrix Analysis & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 89040458
- Full Text :
- https://doi.org/10.1137/110851407