Using an Efficient Sparse Minor Expansion Algorithm to Compute Polynomial Subresultants and the Greatest Common Denominator
- 1 October 1978
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-27 (10) , 945-950
- https://doi.org/10.1109/tc.1978.1674974
Abstract
In this paper, the use of an efficient sparse minor expansion method to directly compute the subresultants needed for the greatest common denominator (GCD) of two polynomials is described. The sparse minor expansion method (applied either to Sylvester's or Bezout's matrix) naturally computes the coefficients of the subresultants in the order corresponding to a polynomial remainder sequence (PRS), avoiding wasteful recomputation as much as possible. It is suggested that this is an efficient method to compute the resultant and GCD of sparse polynomials.Keywords
This publication has 10 references indexed in Scilit:
- Analysis of Algorithms, A Case Study: Determinants of Matrices with Polynomial EntriesACM Transactions on Mathematical Software, 1976
- The Algebraic Solution of Sparse Linear Systems via Minor ExpansionACM Transactions on Mathematical Software, 1976
- An efficient sparse minor expansion algorithmPublished by Association for Computing Machinery (ACM) ,1976
- The definition and use of data structures in REDUCEPublished by Association for Computing Machinery (ACM) ,1976
- On the subresultant PRS algorithmPublished by Association for Computing Machinery (ACM) ,1976
- An algorithm for GCF extraction from two multivariable polynomialsProceedings of the IEEE, 1976
- The theory and applications of the innersProceedings of the IEEE, 1975
- On Computing the Exact Determinant of Matrices with Polynomial EntriesJournal of the ACM, 1975
- A mode analyzing algebraic manipulation programPublished by Association for Computing Machinery (ACM) ,1974
- On Euclid's Algorithm and the Theory of SubresultantsJournal of the ACM, 1971