Are there any neat algorithm to factor a homogenous polynomial, given we know this polynomial factors into linear forms?

Question

Are there any neat algorithm to factor a multivariable (more than 2 variables) homogenous polynomial, given we know this polynomial factors into linear forms?

Answer 1

As Denis Serre points out, this problem subsumes the problem of factoring single variable polynomials, so I'm going to assume that you already have software on hand to do that (probably numerically). In that case, here's what I'd do. For simplicity, presented first in the case of a homogenous polynomial $F(x,y,z)$ in three variables, so a curve in the projective plane.

Pick a line $L$ in the plane and find out where it meets your curve. This amounts to solving a single variable polynomial equation $F(x_0+at, y_0+bt, z_0+ct)=0$ for some constants $(x_0, y_0, z_0$ and $(a,b,c)$. If any of the roots are extremely close to each other, this suggests that $L$ is passing very close to where two of your lines cross; discard this data and try again with another $L$. So now we have $n$ points $z_1$, $z_2$, ..., $z_n$ in $\mathbb{P}^2$, one on each of your lines.

Repeat with a second line $M$ to get points $w_1$, $w_2$, ..., $w_n$. Then, for each $(z_i, w_j)$, see whether your polynomial vanishes on the line through $z_i$ and $w_j$. This is just a matter of plugging $z_i + t w_j$ into $F$. Remember that, when you work with floating point numbers, you should never check whether something equals zero, but rather whether it is very small.

Because we chose the $z_i$ and $w_i$ well away from the intersections of your lines, the restriction of $F$ to $z_i + t w_j$ should not be particularly small if $z_i$ and $w_j$ do not lie on the same line. So you can figure out which $z_i$ lies on a factor of $F$ with which $w_j$, and then recover that factor by linear algebra.

For a polynomial in $d+1$ variables, use $d$ lines to get $n d$ points. Computing the restriction of $F$ to $(d-1) n^2$ lines will then tell you which of your points to group together.

Answer 2

There are a number of ways to factor multivariate polynomials, and the problem is greatly muddled by the fact that a general multivariate polynomial in $n$ variables of degree $d$ has something like $d^n$ terms, so any algorithm designed for general polynomials is likely to be useless in practice, so one needs to keep track of the sparsity of the intermediate results, etc. Most algorithms I am aware of use Hensel lifting in some form, see this paper for example (Inaba, Factorizations of Multivariate polynomials, 2005). Whether this method is "neat" is in the eye of the beholder.

Answer 3

No. Take a one-variable polynomial $P(X)$. Make it homogenous: $P(X)=Q(X,1)$. Pretend that $Q(X,Y)$ is a polynomial in $3$ variables $X,Y,Z$. If the field $k$ is algebraically closed, you know that $Q$ splits. If you have that algorithm, then you find the factors and this gives you the roots of $P$. This contradicts Abel's theorem that the general polynomial of degree $\ge5$ is not solvable.