×

The computation of the degree of the greatest common divisor of three Bernstein basis polynomials. (English) Zbl 1442.13090

Summary: This paper considers the application of the Sylvester resultant matrix to the computation of the degree of the greatest common divisor (GCD) of three Bernstein basis polynomials \(f (y), g (y)\) and \(h (y)\). It is shown that the governing equations can be written in two forms, which lead to different Sylvester matrices. The first form requires that the polynomials be considered in pairs, but different pairs of polynomials may yield different computational answers, for example, the solution of the computations \(\text{GCD} (f, g)\) and \(\text{GCD} (g, h)\) may differ from the solution of the computations \(\text{GCD} (f, g)\) and \(\text{GCD} (f, h)\), depending on \(f (y), g (y)\) and \(h (y)\). This problem does not arise when the second form is considered, which requires that the three polynomials be considered simultaneously. Complications arise in both forms because of the combinatorial terms in the Bernstein basis functions, which cause the entries of the matrices to span several orders of magnitude, even if the coefficients of the polynomials are of the same order of magnitude. It is shown that the adverse effects of this wide range of magnitudes can be mitigated by postmultiplying both forms of the Sylvester matrix by a diagonal matrix of combinatorial terms and preprocessing \(f (y), g (y)\) and \(h (y)\) by three operations. Results of \(\operatorname{GCD}\) computations from the two forms of the Sylvester matrix when \(f (y), g (y)\) and \(h (y)\) are perturbed by noise, and with the omission and inclusion of the preprocessing operations, are shown.

MSC:

13P15 Solving polynomial systems; resultants
33C45 Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.)
65F99 Numerical linear algebra
65H14 Numerical algebraic geometry

Software:

MultRoot
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Barnett, S., Polynomials and Linear Control Systems (1983), Marcel Dekker: Marcel Dekker New York, USA · Zbl 0528.93003
[2] D.A. Bini, P. Boito, Structured matrix-based methods for polynomial \(\epsilon \)-GCD: Analysis and comparisons, in: Proc. Int. Symp. Symbolic and Algebraic Computation, Waterloo, Canada, 2007, pp. 9-16. · Zbl 1190.65060
[3] Bini, D. A.; Boito, P., A fast algorithm for approximate polynomial GCD based on structured matrix computations, (Bini, D. A.; Mehrmann, V.; Olshevsky, V.; Tyrtshnikov, E.; Barel, M. Van, Numerical Methods for Structured Matrices and Applications: The Georg Heinig Memorial Volume (2010), Birkhäuser), 155-173 · Zbl 1203.65078
[4] Bourne, M.; Winkler, J. R.; Su, Y., The computation of the degree of an approximate greatest common divisor of two Bernstein polynomials, Appl. Numer. Math., 111, 17-35 (2017) · Zbl 1353.65014
[5] Bourne, M.; Winkler, J. R.; Su, Y., A non-linear structure-preserving matrix method for the computation of the coefficients of an approximate greatest common divisor of two Bernstein polynomials, J. Comput. Appl. Math., 320, 221-241 (2017) · Zbl 1372.65048
[6] Z. Li, Z. Yang, L. Zhi, Blind image deconvolution via fast approximate GCD, in: Proc. Int. Symp. Symbolic and Algebraic Computation, 2010, pp. 155-162. Code: http://fengl.org/publications/. · Zbl 1321.68442
[7] Pan, V. Y., Computation of approximate polynomial GCDs and an extension, Inform. and Comput., 167, 71-85 (2001) · Zbl 1005.12004
[8] Winkler, J. R., Structured matrix methods for the computation of multiple roots of a polynomial, J. Comput. Appl. Math., 272, 449-467 (2014) · Zbl 1294.65053
[9] Winkler, J. R., Polynomial computations for blind image deconvolution, Linear Algebra Appl., 502, 77-103 (2016) · Zbl 1357.68285
[10] Winkler, J. R.; Allan, J. D., Structured low rank approximations of the Sylvester resultant matrix for approximate GCDs of Bernstein polynomials, Electron. Trans. Numer. Anal., 31, 141-155 (2008) · Zbl 1171.65039
[11] Winkler, J. R.; Allan, J. D., Structured total least norm and approximate GCDs of inexact polynomials, J. Comput. Appl. Math., 215, 1-13 (2008) · Zbl 1136.65049
[12] Winkler, J. R.; Hasan, M., An improved non-linear method for the computation of a structured low rank approximation of the Sylvester resultant matrix, J. Comput. Appl. Math., 237, 1, 253-268 (2013) · Zbl 1253.65065
[13] Winkler, J. R.; Hasan, M.; Lao, X. Y., Two methods for the calculation of the degree of an approximate greatest common divisor of two inexact polynomials, Calcolo, 49, 241-267 (2012) · Zbl 1261.12001
[14] Winkler, J. R.; Lao, X. Y.; Hasan, M., The computation of multiple roots of a polynomial, J. Comput. Appl. Math., 236, 3478-3497 (2012) · Zbl 1243.65050
[15] Winkler, J. R.; Yang, N., Resultant matrices and the computation of the degree of an approximate greatest common divisor of two inexact Bernstein basis polynomials, Comput. Aided Geom. Design, 30, 4, 410-429 (2013) · Zbl 1296.65031
[16] Zeng, Z., Computing multiple roots of inexact polynomials, Math. Comp., 74, 869-903 (2005) · Zbl 1079.12007
[17] Barnett, S., Greatest common divisor of several polynomials, Proc. Cambridge Philos. Soc., 70, 263-268 (1971) · Zbl 0224.15018
[18] Barnett, S., Greatest common divisors from generalized Sylvester resultant matrices, Linear Multilinear Algebra, 8, 271-279 (1980) · Zbl 0438.12012
[19] Christou, D.; Karcanias, N.; Mitrouli, M., The ERES method for computing the approximate GCD of several polynomials, Appl. Numer. Math., 227, 126-135 (2009)
[20] Christou, D.; Mitrouli, M.; Triantafyllou, D., Structured matrix methods computing the greatest common divisor of polynomials, Special Matrices, 5, 202-224 (2017) · Zbl 1394.65035
[21] Diaz-Toca, G.; Gonzalez-Vega, L., Barnett’s theorems about the greatest common divisor of several polynomials through Bézout-like matrices, J. Symbolic Comput., 34, 59-81 (2002) · Zbl 1026.13010
[22] Gonzalez-Vega, L., An elementary proof of Barnett’s theorem about the greatest common divisor of several univariate polynomials, Linear Algebra Appl., 247, 185-202 (1996) · Zbl 0866.12002
[23] Corless, R. M.; Gianni, P. M.; Trager, B. M.; Watt, S. M., The singular value decomposition for polynomial systems, (Proc. Int. Symp. Symbolic and Algebraic Computation (1995), ACM Press: ACM Press New York), 195-207 · Zbl 0920.65034
[24] Corless, R. M.; Giesbrecht, M. W.; van Hoeij, M.; Kotsireas, I. S.; Watt, S. M., Towards factoring bivariate approximate polynomials, (Proc. Int. Symp. Symbolic and Algebraic Computation (2001), ACM Press: ACM Press New York), 85-92 · Zbl 1356.13030
[25] Gao, S.; Kaltofen, E.; May, J.; Yang, Z.; Zhi, L., Approximate factorisation of multivariate polynomials via differential equations, (Proc. Int. Symp. Symbolic and Algebraic Computation (2004), ACM Press: ACM Press New York), 167-174 · Zbl 1134.65346
[26] Kaltofen, E.; May, J.; Yang, Z.; Zhi, L., Approximate factorization of multivariate polynomials using singular value decomposition, J. Symbolic Comput., 43, 359-376 (2008) · Zbl 1135.12003
[27] Zhi, L.; Yang, Z., Computing approximate GCD of multivariate polynomials by structured total least norm (2004), Institute of Systems Science, AMSS, Academia Sinica: Institute of Systems Science, AMSS, Academia Sinica Beijing, China
[28] Farouki, R. T.; Rajan, V. T., On the numerical condition of polynomials in Bernstein form, Comput. Aided Geom. Design, 4, 191-216 (1987) · Zbl 0636.65012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.