Approximate polynomial GCD over integers

• Published in: Journal of symbolic computation 2011-12, Vol.46 (12), p.1306-1317
• Main Author: Nagasaka, Kosaku
• Format: Article
• Language: English
• Subjects: Approximate polynomial GCD; Numerical polynomial GCD
• ISSN: 0747-7171; 1095-855X
• DOI: 10.1016/j.jsc.2011.08.011

Symbolic numeric algorithms for polynomials are very important, especially for practical computations since we have to operate with empirical polynomials having numerical errors on their coefficients. Recently, for those polynomials, a number of algorithms have been introduced, such as approximate univariate GCD and approximate multivariate factorization for example. However, for polynomials over integers having coefficients rounded from empirical data, changing their coefficients over reals does not remain them in the polynomial ring over integers; hence we need several approximate operations over integers. In this paper, we discuss computing a polynomial GCD of univariate or multivariate polynomials over integers approximately. Here, “approximately” means that we compute a polynomial GCD over integers by changing their coefficients slightly over integers so that the input polynomials still remain over integers. ► We compute a GCD of multivariate polynomials over integers approximately. ► “Approximately” means that we change their coefficients slightly over integers. ► We use the well-known subresultant mapping and lattice basis reduction. ► The algorithm works for not only very tiny but also small tolerances.