A polyalgorithm for polynomial GCD computation involving matrices

• Main Author: Parrilla, Nonna J.
• Format: text
• Language: English
• Published: Animo Repository 2014
• Subjects: Algorithms
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/4615
• Institution: De La Salle University

As GCD computation surfaces as a subproblem in a variety of applications, the need for some way to discriminate between algorithms according to performance becomes apparent. In this study, a polyalgorithm for polynomial GCD computation was developed. Algorithms involving Sylvester, Bezout, and Hankel matrices were analyzed, implemented and compared under the sparse and dense models, using polynomials of varying degrees and coefficient lengths. In the process of studying the algorithms which all require rank determination, for which the LSP factorization was used, improvements on the LSP were introduced. Both theoretical and empirical analyses were done for all the three algorithms (and the LSP algorithm) and were used to develop the polyalgorithm which chooses the best algorithm given the degree and coefficient lengths of polynomial inputs.