Analysis and comparison of numerical algorithms for finding the GCD of certain types of polynomials in the Chebyshev basis
DOI:
https://doi.org/10.11113/mjfas.v13n2.603Keywords:
Greatest Common Divisor (GCD), Gauss Elimination, QR Decomposition, Overdetermined systems, NormalizationAbstract
This research investigates on the numerical methods for computing the greatest common divisors (GCD) of two polynomials in the orthogonal basis without having to convert to the power series form. Previous implementations were conducted using the Gauss Elimination with partial pivoting (GEPP) and QR Householder algorithms, respectively. This work proceeds to seek for a better approximate solution by comparing the results of the implementations with the QR with column pivoting (QRCP) algorithm. The results reveal that QRCP is as competent as the GEPP algorithm, up to a certain degree, giving a reasonably good approximate solution. It is also found that normalizing the columns of the associated coefficient matrix slightly reduces the condition number of the matrix but has no significant effect on the GCD solutions when applying the GEPP and QR Householder algorithms. However equilibration of the columns by computing its ∞-norm is capable to improve the solution when QRCP is applied. Comparing the three algorithms on some test problems, QR Householder outperforms the rest and is able to give a good approximate solution in the worst case condition when the smallest element of the matrix is 1, the entries ranging up to 15 digits integers.
References
B. Liang, S. U. Pillai. (1997). Two-dimensional blind deconvolution using a robust GCD approach. Proceedings of the 1997 International Conference on Image Processing. Part 2 (of 3). 26-29 October. Santa Barbara, CA, USA: IEEE, 424-427.
S. U. Pillai, B. Liang. (1999). Blind image deconvolution using a robust GCD Approach. IEEE Transactions on Image Processing 8(2), 295-301.
P.Stoica, T. Söderström, (1997). Common factor detection and estimation. Automatica, 33(5), 985-989.
Z. Zheng. (2005). Computing multiple roots of inexact polynomials. Mathematics of Computation, 74, 869-903.
S. Barnett. (1975). A companion matrix analogue for orthogonal polynomials. Linear Algebra and its Applications 12(3), 197-202.
s. barnett. (1971). greatest common divisor of several polynomials. Mathematical Proceedings of the Cambridge Philosophical Society, (Cambridge University Press, 1971), 70, 263-268.
S. Barnett. (1983). Polynomials and Linear Control Systems Marcel. New York, NY, USA: Dekker, Inc.
N. Aris, A. A. Rahman. (2001). On the computation of the GCD of polynomials relative to an orthogonal basis,” Technical Report LT/M Bil.1/2001, April 2001.
N. Aris, S. N. Ahmad. (2008). Computing the greatest common divisor of polynomials using the comrade matrix. In D. Kapur (Ed.), Computer Mathematic, 87-96. Heidelberg: Springer Berlin Heidelberg.
N. Aris. (2003). On the application of modular approach to the computation of the greatest common divisor of generalized polynomials. Doctoral Thesis. Universiti Teknologi Malaysia.
S. N. A. Isa, N. Aris, S. M. Puzi, in N. Rusli, W. M. K. A. W. Zaimi, K. A. M. Khazali, M. J. Masnan, W. S. W. Daud, N. Abdullah, & N. A. M. Amin (Eds.). (2016). Numerical matrix methods in the computation of the greatest common divisor (GCD) of polynomials. AIP Conference Proceedings, 1775(1), 030064).
B. N. Datta. (2010) Numerical linear algebra and applications. India: Prentice Hall.
G. H. Golub, C. F. Van Loan. (2012). Matrix computations (3rd Edition). USA: Johns Hopkins University Press.
N. J. Higham. (2002). Accuracy and stability of numerical algorithms (2nd Edition). Philadelphia: Society for Industrial and Applied Mathematics (SIAM).
