The input to our algorithms is a ``noisy'' multivariate polynomial f(x,y,...), that is, the complex rational coefficients of f are considered imprecise with an unknown error that causes f to be irreducible over the complex numbers C. Such errors could have resulted from a physical measurement or from the truncation present in floating point numbers. We seek to perturb the coefficients by a small quantity such that the resulting polynomial factors over C. Ideally, one would like to minimize the perturbation in some selected distance measure, but no efficient algorithm for that is known.
We present numerical variants of algorithms by W. M. Ruppert and S. Gao. We demonstrate on a significant body of experimental data that our algorithms are practical and can find factorizable polynomials within a distance that is about the same in relative magnitude as the input error, that even when the relative error in the input is substantial (10^(-3)). We have successfully factored polynomials provided to us by Jan Verschelde that arise in the engineering of so-called Stewart-Gough platforms.
Joint work with Shuhong Gao (Clemson), John P. May (NCSU and Waterloo), Zhengfeng Yang and Lihong Zhi (AMSS Beijing, China)