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 100121185
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) 9983511
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 socalled StewartGough 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)
top  contact webmaster@cs.nyu.edu
