A polyalgorithm for polynomial GCD computation involving matrices
Date of Publication
2014
Document Type
Master's Thesis
Degree Name
Master of Science in Computer Science
College
College of Computer Studies
Department/Unit
Computer Science
Thesis Adviser
Nelson Marcos
Defense Panel Chair
Shirley Chu
Defense Panel Member
Allan Borra
Abstract/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.
Abstract Format
html
Language
English
Format
Electronic
Electronic File Format
MS WORD
Accession Number
CDTG005557
Shelf Location
Archives, The Learning Commons, 12F Henry Sy Sr. Hall
Physical Description
leaves ; 4 3/4 in.
Keywords
Algorithms
Upload Full Text
wf_no
Recommended Citation
Parrilla, N. J. (2014). A polyalgorithm for polynomial GCD computation involving matrices. Retrieved from https://animorepository.dlsu.edu.ph/etd_masteral/4615