Approximate Multivariate Factorization
and Its Time Complexity

Kosaku Nagasaka $^{\dagger}$ and Tateaki Sasaki $^{\ddagger}$
$^{\dagger}$ Doctoral Program of Mathematics
$^{\ddagger}$ Institute of Mathematics
Univiversity of Tsukuba
Tsukuba-shi, Ibaraki 305-8571, Japan

{nagasaka,sasaki}@math.tsukuba.ac.jp

Abstract:

Approximate factorization of multivariate polynomial is that, given a polynomial F in ${\mathbf C}[x,y,\ldots,z]$, we determine polynomials G,H and ${\mit \Delta}_F$ in ${\mathbf C}[x,y,\ldots,z]$ satisfying $F=GH+{\mit \Delta}_F$, $\parallel\hspace{-3pt}{\mit \Delta}_F \hspace{-3pt}\parallel/\parallel\hspace{-3pt} F\hspace{-3pt}\parallel = \varepsilon \ll 1$, where $\parallel\hspace{-3pt} P\hspace{-3pt}\parallel$ denotes a suitably defined norm of polynomial P. For approximate factorization, we need a completely different algorithm from those for exact factorization. In 1991, Sasaki et al. presented an algorithm of approximate factorization. The algorithm determines irreducible factors by handling the combinations of roots of the form $c_1 \varphi_1^i + \cdots + c_n \varphi_n^i$, $i=1,2,\ldots$, where $\varphi_1,\ldots, \varphi_n$ are the power-series roots of a given polynomial $F(x,y,\ldots,z)$ and $c_1,\ldots,c_n$ are numbers. The algorithm was analyzed by Sasaki et al. in 1992, but it was incomplete in that the truncation degree of power-series roots was not shown. In this paper, we give a sufficient condition to truncate the power-series, improve the algorithm in several points, and show that the algorithm works in polynomial-time w.r.t. $\textrm{\rm deg}_x(F)$ and $\textrm{\rm tdeg}_{y,\ldots,z}(F)$.