Browse Prior Art Database

Fast Algorithm for Solving Toeplitz Systems of Equations Disclosure Number: IPCOM000055128D
Original Publication Date: 1980-May-01
Included in the Prior Art Database: 2005-Feb-13

Publishing Venue


Related People

Gustavson, FG Yun, DY [+details]


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 [4].) Let matrix an consider solving Tz=b. Previous methods [1] 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).