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

This document is currently not available here.

Share

COinS