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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

3 Answers

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.

-

Why are you working with floating point numbers? – Igor Rivin Jun 30 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 at 1:17

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-

5
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 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 at 15:50

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 49, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9368462562561035, "perplexity_flag": "head"}