A simple algorithm for GCD of polynomials
Article Sidebar
Main Article Content
Abstract
Based on the Bezout approach we propose a simple algorithm to determine the gcd of two polynomials that don't need division, like the Euclidean algorithm, or determinant calculations, like the Sylvester matrix algorithm. The algorithm needs only n steps for polynomials of degree n. Formal manipulations give the discriminant or the resultant for any degree without needing division or determinant calculation.
Downloads
Article Details
Copyright (c) 2022 Nardone P, et al.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Knuth DE. The Art of Computer Programming. Addison-Wesley, Reading, Mass. 1969; 2.
Bini DA, Boito P. Structured matrix-based methods for polynomial -gcd: analysis and comparisons. In Proceedings of the 2007 international symposium on Symbolic and algebraic computation (ISSAC '07). Association for Computing Machinery, New York, NY. USA. 9-16. 2007. DOI:https://doi.org/10.1145/1277548.1277551
Fazzi A, Guglielmi N, Markovsky I. Generalized algorithms for the approximate matrix polynomial GCD of reducing data uncertainties with application to MIMO system and control. Journal of Computational and Applied Mathematics. 2021; 393: 113499. https://doi.org/10.1016/j.cam.2021.113499
Brown WS, Traub JF. On Euclid's Algorithm and the Theory of Subresultants. J ACM. 1971; 18: 505-514. DOI:https://doi.org/10.1145/321662.321665
http://www2.math.uu.se/ svante/papers/sjN5.pdf