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

Abstract

We present a new algorithm that reduces the computation for solving a Toeplitz system to o(n 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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1979
Accession Number
ADA075376

Entities

People

  • David Y. Y. Yun

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Analytic Functions
  • Coefficients
  • Computations
  • Computer Science
  • Computers
  • Decoding
  • Equations
  • Interpolation
  • Military Research
  • Polynomials
  • Rational Functions
  • Security
  • Sequences
  • Shift Registers

Readers

  • Approximation Theory.
  • Calculus or Mathematical Analysis