Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9662305 | Computers & Mathematics with Applications | 2005 | 12 Pages |
Abstract
We propose a “fast” algorithm for the construction of a data-sparse inverse of a generalToeplitz matrix. The computational cost for inverting an N Ã N Toeplitz matrix equals the cost of four length-N FFTs plus an O(N)-term. This cost should be compared to the O(N log2N) cost of previously published methods. Moreover, while those earlier methods are based on algebraic considerations, the procedure of this paper is analysis-based; as a result, its stability does not depend on the symmetry and positive-definiteness of the matrix being inverted. The performance of the scheme is illustrated with numerical examples.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
P.G. Martinsson, V. Rokhlin, M. Tygert,