Computing the greatest common divisor of polynomials using the comrade matrix
The comrade matrix of a polynomial is an analogue of the companion matrix when the matrix is expressed in terms of a general basis such that the basis is a set of orthogonal polynomials satisfying the three-term recurrence relation. We present the algorithms for computing the comrade matrix, and the...
| Main Authors: | , |
|---|---|
| Format: | Book Section |
| Published: |
Springer Verlag
2008
|
| Subjects: |
| _version_ | 1796855091840417792 |
|---|---|
| author | Aris, Nor`Aini Nahar Ahmad, Shamsatun |
| author_facet | Aris, Nor`Aini Nahar Ahmad, Shamsatun |
| author_sort | Aris, Nor`Aini |
| collection | ePrints |
| description | The comrade matrix of a polynomial is an analogue of the companion matrix when the matrix is expressed in terms of a general basis such that the basis is a set of orthogonal polynomials satisfying the three-term recurrence relation. We present the algorithms for computing the comrade matrix, and the coefficient matrix of the corresponding linear systems derived from the recurrence relation. The computing times of these algorithms are analyzed. The computing time bounds, which dominate these times, are obtained as functions of the degree and length of the integers that represent the rational number coefficients of the input polynomials. The ultimate aim is to apply these computing time bounds in the analysis of the performance of the generalized polynomial greatest common divisor algorithms. |
| first_indexed | 2024-03-05T18:23:33Z |
| format | Book Section |
| id | utm.eprints-12519 |
| institution | Universiti Teknologi Malaysia - ePrints |
| last_indexed | 2024-03-05T18:23:33Z |
| publishDate | 2008 |
| publisher | Springer Verlag |
| record_format | dspace |
| spelling | utm.eprints-125192017-10-02T08:27:36Z http://eprints.utm.my/12519/ Computing the greatest common divisor of polynomials using the comrade matrix Aris, Nor`Aini Nahar Ahmad, Shamsatun QA Mathematics The comrade matrix of a polynomial is an analogue of the companion matrix when the matrix is expressed in terms of a general basis such that the basis is a set of orthogonal polynomials satisfying the three-term recurrence relation. We present the algorithms for computing the comrade matrix, and the coefficient matrix of the corresponding linear systems derived from the recurrence relation. The computing times of these algorithms are analyzed. The computing time bounds, which dominate these times, are obtained as functions of the degree and length of the integers that represent the rational number coefficients of the input polynomials. The ultimate aim is to apply these computing time bounds in the analysis of the performance of the generalized polynomial greatest common divisor algorithms. Springer Verlag 2008 Book Section PeerReviewed Aris, Nor`Aini and Nahar Ahmad, Shamsatun (2008) Computing the greatest common divisor of polynomials using the comrade matrix. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag, Germany, 87-96 . ISBN 978-354087826-1 http://dx.doi.org/10.1007/978-3-540-87827-8_7 DOI:10.1007/978-3-540-87827-8_7 |
| spellingShingle | QA Mathematics Aris, Nor`Aini Nahar Ahmad, Shamsatun Computing the greatest common divisor of polynomials using the comrade matrix |
| title | Computing the greatest common divisor of polynomials using the comrade matrix |
| title_full | Computing the greatest common divisor of polynomials using the comrade matrix |
| title_fullStr | Computing the greatest common divisor of polynomials using the comrade matrix |
| title_full_unstemmed | Computing the greatest common divisor of polynomials using the comrade matrix |
| title_short | Computing the greatest common divisor of polynomials using the comrade matrix |
| title_sort | computing the greatest common divisor of polynomials using the comrade matrix |
| topic | QA Mathematics |
| work_keys_str_mv | AT arisnoraini computingthegreatestcommondivisorofpolynomialsusingthecomradematrix AT naharahmadshamsatun computingthegreatestcommondivisorofpolynomialsusingthecomradematrix |