×

An algorithm for computing certified approximate GCD of \(n\) univariate polynomials. (English) Zbl 0964.12007

The paper presents two algorithms for the problem of finding approximate gcd of \(n\) univariate polynomials. More precisely: Given a tolerance \(\varepsilon\) and polynomials \(P1,\ldots ,P_n\) of degree \(d_i\), respectively, find perturbations \(\delta P_i\) and a divisor \(D\) of \(P_i+\delta P_i\) satisfying: (i) \(\deg \delta P_i \leq d_i\), (ii) \(||\delta P_1,\ldots ,\delta P_n||< \varepsilon\), (iii) \(D\) has maximum degree.
The author uses generalized Sylvester matrices together with Singular Value Decomposition (allowing a numerical approach) to device both algorithms. Bounds for the degree of the approximate gcd are obtained. Moreover, the first algorithm provides a certification of the degree. New algorithms for the problem with two polynomials are suggested. Finally, numerical examples with timings are presented, illustrating his computer implementation.

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
65F30 Other matrix algorithms (MSC2010)
15A18 Eigenvalues, singular values, and eigenvectors
65Y99 Computer aspects of numerical algorithms
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beauzamy, B.; Bombieri, E.; Enflo, P.; Montgomery, H. L., Products of polynomials in many variables, J. Number Theory, 36, 219-245 (1990) · Zbl 0729.30004
[2] R. Corless, P. Gianni, B. Trager, S. Watt, The singular value decomposition for polynomial systems, in: ACM Internat. Symp. on Symbolic and Algebraic Computation, 1995, pp. 195-207.; R. Corless, P. Gianni, B. Trager, S. Watt, The singular value decomposition for polynomial systems, in: ACM Internat. Symp. on Symbolic and Algebraic Computation, 1995, pp. 195-207. · Zbl 0920.65034
[3] J. Dégot, Un théorème de certification pour le degré du pgcd approché de deux polynomes, Université de Limoges, Département de Mathématiques, 123 av. Albert Thomas, 87060 Limoges, France, 1996.; J. Dégot, Un théorème de certification pour le degré du pgcd approché de deux polynomes, Université de Limoges, Département de Mathématiques, 123 av. Albert Thomas, 87060 Limoges, France, 1996.
[4] I.Z. Emiris, A. Galligo, H. Lombardi, Numerical univariate polynomial gcd, in: Proc. AMS-SIAM Summer Seminar on Math. of Numerical Analysis, Lectures in Applied Math., 1995.; I.Z. Emiris, A. Galligo, H. Lombardi, Numerical univariate polynomial gcd, in: Proc. AMS-SIAM Summer Seminar on Math. of Numerical Analysis, Lectures in Applied Math., 1995. · Zbl 0856.65006
[5] I.Z. Emiris, A. Galligo, H. Lombardi, Certified Approximate univariate gcds, in: Proc. 4th Internat. Effective Methods in Algebraic Geometry (MEGA), 1997, in press.; I.Z. Emiris, A. Galligo, H. Lombardi, Certified Approximate univariate gcds, in: Proc. 4th Internat. Effective Methods in Algebraic Geometry (MEGA), 1997, in press. · Zbl 0891.65015
[6] G.H. Golub, C.F. Van Loan, Matrix Computations, The Johns Hopkins University Press, Baltimore, MD, 1989.; G.H. Golub, C.F. Van Loan, Matrix Computations, The Johns Hopkins University Press, Baltimore, MD, 1989. · Zbl 0733.65016
[7] V. Hribernig, H.J. Stetter, Detection and validation of clusters of zeros of polynomials, J. Symbolic Comput. 1996, Special Issue on Validation and Symbolic Computing.; V. Hribernig, H.J. Stetter, Detection and validation of clusters of zeros of polynomials, J. Symbolic Comput. 1996, Special Issue on Validation and Symbolic Computing. · Zbl 0910.65030
[8] N. Karmarkar, Y.N. Lakshman, Approximate polynomial greatest common divisors and nearest singular polynomials, in: ACM Internat. Symp. on Symbolic and Algebraic Computation, 1995.; N. Karmarkar, Y.N. Lakshman, Approximate polynomial greatest common divisors and nearest singular polynomials, in: ACM Internat. Symp. on Symbolic and Algebraic Computation, 1995. · Zbl 0928.13017
[9] M. Mignotte, Mathématiques pour le Calcul Formel, Presses Universitaires de France, Paris, 1989.; M. Mignotte, Mathématiques pour le Calcul Formel, Presses Universitaires de France, Paris, 1989. · Zbl 0679.12001
[10] V.Y. Pan, Numerical computation of a polynomial gcd and extensions, City Univ. of New York, 1996.; V.Y. Pan, Numerical computation of a polynomial gcd and extensions, City Univ. of New York, 1996.
[11] Schönhage, A., Quasi-gcd Computations, J. Complexity, 1, 118-137 (1985) · Zbl 0586.68031
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.