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.
|