Accession Number:

AD0729520

Title:

On Euclid's Algorithm and the Theory of Subresultants,

Descriptive Note:

Corporate Author:

WASHINGTON UNIV SEATTLE COMPUTER SCIENCE GROUP

Personal Author(s):

Report Date:

1971-08-09

Pagination or Media Count:

28.0

Abstract:

A key ingredient for systems which perform symbolic computer manipulation of multivariate rational functions are efficient algorithms for calculating polynomial greatest common divisors. Euclids algorithm cannot be used directly because of problems with coefficient growth. The search for better methods leads naturally to the theory of subresultants. This paper presents an elementary treatment of the theory of subresultants, and examines the relationship of the subresultants of a given pair of polynomials to their polynomial remainder sequence as determined by Euclids algorithm. This relation is expressed in the fundamental theorem of this paper. The results are essentially the same as those of Collins but the presentation is briefer, simpler, and somewhat more general. The fundamental theorem finds further applications in the proof that the modular algorithm for polynomial GCD terminates. Author

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE