Computer Science Colloquium

Approximate Factorization of Complex Multivariate Polynomials

Erich Kaltofen
North Carolina State University

Friday, September 24, 2004 11:30 A.M.
Room 1302 Warren Weaver Hall
251 Mercer Street
New York, NY 10012-1185

Directions: http://cs.nyu.edu/csweb/Location/directions.html
Colloquium Information: http://cs.nyu.edu/csweb/Calendar/colloquium/index.html

Hosts:

Victor Shoup shoup@cs.nyu.edu, (212) 998-3511

Abstract

The input to our algorithms is a ``noisy'' polynomial f(x,y), that is, the complex rational coefficients of f are considered imprecise with unknown errors 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 a numerical variant of algorithms by W. M. Ruppert and S. Gao. Our numerical factorizer makes repeated use of singular value decompositions. We demonstrate on a significant body of experimental data that our algorithm is 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 that arise in the engineering of so-called Stewart-Gough platforms used, for example, in flight simulators. These polynomials can have three and more variables and we present generalizations of our approach to that case.

Joint work with Shuhong Gao (Clemson), John P. May (NCSU and Waterloo), Zhengfeng Yang and Lihong Zhi (AMSS Beijing)