Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
    
Why are you working with floating point numbers? –  Igor Rivin Jun 30 '12 at 23:53
    
In my experience, working with numeric solutions to polynomials is significantly faster than passing to the number field where they have roots, once the degree gets past $4$ or $5$. –  David Speyer Jul 1 '12 at 1:17
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
6  
This doesn't make sense, as the algorithm doesn't need to output the roots in radical form. This does raise the question however, of what form of input and output does the OP expect. –  Felipe Voloch Jun 30 '12 at 13:07
    
I think this answer is valuable; it is unclear what the OP wants and this certainly answers one interpretation. –  David Speyer Jun 30 '12 at 15:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.