A polyalgorithm for polynomial GCD computation involving matrices

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 Hanke...

Full description

Saved in:
Bibliographic Details
Main Author: Parrilla, Nonna J.
Format: text
Language:English
Published: Animo Repository 2014
Subjects:
Online Access:https://animorepository.dlsu.edu.ph/etd_masteral/4615
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: De La Salle University
Language: English
Description
Summary: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.