Fast Algorithm for Solving Toeplitz Systems of Equations
Original Publication Date: 1980-May-01
Included in the Prior Art Database: 2005-Feb-13
Disclosed herein is the first 0(n log/2/n) method to solve Toeplitz systems of equations which handles all degenerate and special cases. (The symbol 0 used in formulas in this and subsequent paragraphs refers to the constant "big Oh" defined in reference .) Let matrix an consider solving Tz=b. Previous methods  require 0(n/2/) operations to solve Tz=b. Algorithm Toeplitz described herein finds z, given T and b, in 0(n log/2/n).