General  Information
Important Dates
Conference Poster
Organizing Committee
Program and Schedule
Invited Talks
Contributed Talks
Software Exhibitions
Registered Participants
 Call  For
Research Papers
Software Exhibitions
Jenks Prize Nominations
 Local  Information
Conference Location
Speakers' Information
Gastronomic Guide
Additional Information
Social Events
Previous ISSACs
Other Events



Approximate factorization of multivariate polynomials via differential equations

S. Gao, E. Kaltofen, J. P. May, Z. Yang, L. Zhi


We consider the problem of approximately factoring a polynomial f(x,y) in C[x,y], where the actual coefficients of f are real or complex numbers. We do not assume that f is reducible over C. Irreducibility of f is the case, for instance, if the coefficients of f are imprecise due to perturbations caused by physical measurements or by floating point computation. More generally, we do not assume that f is near a factorizable polynomial. By |f| we denote the Euclidean length of the coefficient vector of f. By fmin we denote a factorizable polynomial over C with deg(fmin) <= deg(f) such that | f - \fmin | is minimized, that is, $fmin$ is a nearest reducible polynomial. We present new algorithms that can find a factorization ftilde = f_1 ... f_2 ... f_r in C[x,y] with deg(ftilde) <= deg(f) such that | ftilde - fmin | is small.

Our algorithms are based on Gao's exact algorithms. All our methods are numerical and we execute our procedures with floating point scalars. We use the singular value decomposition (SVD) to determine the number of factors and approximate nullspace vectors in the arising Ruppert matrices. Furthermore, we have designed a new approximate bivariate polynomial GCD algorithm for the last step in Gao's approach. Our approximate GCD algorithm again makes use of the SVD on bivariate and univariate Sylvester matrices.

  issac2004 @