Report Number: CS-TR-79-748
Institution: Stanford University, Department of Computer Science
Title: Fast algorithms for solving Toeplitz systems of equations and finding rational Hermite interpolants
Author: Yun, David Y. Y.
Date: July 1979
Abstract: We present a new algorithm that reduces the computation for solving a Toeplitz system to O(n ${log}^2$ n) and automatically resolves all degenerate cases of the past. Our fundamental results show that all rational Hermite interpolants, including Pade approximants which is intimately related to this solution process, can be computed fast by an Euclidean algorithm. In this report we bring out all these relationships with mathematical justifications and mention important applications including decoding BCH codes.
http://i.stanford.edu/pub/cstr/reports/cs/tr/79/748/CS-TR-79-748.pdf