Fast Algorithms for Solving Toeplitz System of Equations and Finding Rational Hermite Interpolants.

reportActive / Technical Report | Accession Number: ADA075376 | Open PDF

Abstract:

We present a new algorithm that reduces the computation for solving a Toeplitz system to on log2 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 relationship with mathematical justifications and mention important applications including decoding BCH codes. Author

Author(s):
Yun, David Y. Y.
Author Organization(s):
STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Descriptive Note:
Technical rept.,
Pagination:
0012

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
STAN-CS-79-748
Contract/Grant Number(s):
N00014-76-C-0330, NSF-MCS77-23738
 Subject Terms
Joint Capability Areas:
JCA_1.2_Force Preparation; JCA_1_Force Support
Communities of Interest:
No COI(s) Identified
Descriptor(s):
*INTERPOLATION, *LINEAR ALGEBRA, ALGORITHMS, SOLUTIONS(GENERAL), POLYNOMIALS, SEQUENCES(MATHEMATICS), MATRIX THEORY, DECODING
Field(s)/Group(s):
Theoretical Mathematics
Keyword(s):
Toeplitz matrices, Pade approximants, Hermetian matrices
Report Date:
1979 Jul 01