Back to Search
Start Over
Superfast solution of Toeplitz-like systems
- Publication Year :
- 2011
-
Abstract
- In this paper a new O(N log3 N) solver for N £ N Toeplitz-like sys- tems, based on a divide and conquer technique, is presented. Similarly to the superfast algorithm MBA for the inversion of a Toeplitz-like matrix [2, 16], 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. The same idea has been used in [19] to improve the numerical stability of superfast meth- ods based on the generalized Schur algorithm for positive de¯nite Toeplitz matrices, but the algorithm we propose can be applied also to nonsym- metric Toeplitz-like systems. The stability of the algorithm is examined through numerical experiments.
- Subjects :
- Toeplitz systems
linear algebra
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.cnr...........73c2610efeb0a9ddd79105e9b39ec7f9