Simple and quick way to factor a polynomial

New to Julia
1

Hello I am looking for a simple and quick way I can enter a polynomial like; ax^3 + bx^2 + cx + d and get an output in the format (l + m)(n+ p)(q + r)

I am unable to find any quick way online

2 Likes
2

Factoring a polynomial and finding the roots of the polynomial are very mathematically close. The polynomial in the question is usually referred to as a cubic polynomial and has a special place in the history of mathematics. A reading of:

will answer most of the question and provide formulas to find the factorization which can be translated into code.

3

Here is some Julia code to solve a cubic and factor. It demonstrates:

  • Taking factored symbolic polynomial and expanding it.
  • Extracting the coefficients a,b,c,d.
  • Finding roots using PolynomialRoots package
  • Assembling a factored form from the root.
  • Note there may be issues of numerical accuracy.
julia> using PolynomialRoots

julia> using Symbolics

julia> @variables x
1-element Vector{Num}:
 x

julia> (2-x)*(5-x)*(7-x)
(7 - x)*(5 - x)*(2 - x)

julia> expand((2-x)*(5-x)*(7-x))
70 - 59x + 14(x^2) - (x^3)

julia> a,b,c,d = -1,14,-59,70
(-1, 14, -59, 70)

julia> roots([d,c,b,a])
3-element Vector{ComplexF64}:
 7.0 + 0.0im
 5.0 - 0.0im
 2.0 + 0.0im

julia> prod(x.-roots([d,c,b,a]))
(-2.0 + x)*(-5.0 + x)*(-7.0 + x)

julia> a*prod(x.-roots([d,c,b,a])) .|> real |> expand
70.0 - 59.0x + 14.0(x^2) - (x^3)

ADDENDUM:

Thanks to nsajko, I’ve learned about AMRVW, and with it:

julia> using AMRVW

julia> AMRVW.roots(Float64[d,c,b,a])
3-element Vector{ComplexF64}:
 2.0000000000000004 + 0.0im
  5.000000000000002 + 0.0im
  6.999999999999995 + 0.0im

julia> AMRVW.real_polynomial_roots(Float64[d,c,b,a]).real_roots
3-element Vector{Float64}:
 2.0000000000000004
 5.000000000000002
 6.999999999999995

AMRVW seems to be the better package to go to for finding polynomial roots.

6 Likes
4

“…enter a polynomial like; ax^3 + bx^2 +cx+d”…

  • Are you talking about a cubic polynomial, or
  • Is this just an example of a polynomial, where you in reality ask for finding the form “(l+m)(n+p)(q+r)” [whatever that means – presumably you mean (x-x1)(x-x2)(x-x3)??]" of arbitrary order?
2 Likes
5

For finding polynomial roots numerically, the AMRVW package should be able to give much more accurate results. As of the latest release it also has special support for friendlier handling of real polynomials specifically, in case that helps. The PolynomialRoots package is buggy and not very actively maintained.

2 Likes
6

If the main focus is finding the roots:

import Polynomials as pol

julia> p = pol.Polynomial([1,2,0,3])
Polynomial(1 + 2*x + 3*x^3)

julia> roots(p)
3-element Vector{ComplexF64}:
 -0.40231993806281435 + 0.0im
  0.20115996903140715 - 0.8877289372825564im
  0.20115996903140715 + 0.8877289372825564im

If you want a string expression, you can always do as follows:

import Polynomials as pol

julia> p = pol.Polynomial([1,2,0,3])
Polynomial(1 + 2*x + 3*x^3)

julia> p_root = roots(p)
3-element Vector{ComplexF64}:
 -0.40231993806281435 + 0.0im
  0.20115996903140715 - 0.8877289372825564im
  0.20115996903140715 + 0.8877289372825564im

julia> p_string = ""
""

julia> for x0 in p_root
       p_string = p_string*"(x - ($x0))"
       end

julia> p_string
"(x - (-0.40231993806281435 + 0.0im))(x - (0.20115996903140715 - 0.8877289372825564im))(x - (0.20115996903140715 + 0.8877289372825564im))"
7

If you are using Polynomials.jl, there is also the FactoredPolynomial representation, which might fell more direct:

julia> using Polynomials

julia> x = variable()
Polynomial(x)

julia> p = convert(FactoredPolynomial, x^3 - 6x^2 + 11x - 6)
FactoredPolynomial((x - 1.0000000000000002) * (x - 3.0) * (x - 1.9999999999999996))

You might want to round here, as this polynomial should have integer roots:

julia> map(x -> round(x, digits=1), p)
FactoredPolynomial((x - 2.0) * (x - 3.0) * (x - 1.0))

As for AMRVW or PolynomialRoots or just roots from Polynomials, the faster and more accurate is usually PolynomialRoots until the polynomial gets quite large in degree, but the differences are usually quite modest.

2 Likes
8

Maybe this would be true if the algorithm was implemented correctly (I’m not an expert), but PolynomialRoots seems to suffer from serious bugs, if you take a look at its bug tracker and related threads on this forum.

9

For genuine symbolic multivariate factorization:

julia> using Nemo

julia> R, (x, y, z) = PolynomialRing(ZZ, ["x", "y", "z"]) # declare the list of variables

julia> factor(-3*x^2*y-6*x^2*z-3*x*y^2-5*x*y*z+2*x*z^2+y^2*z+2*y*z^2)
-1 * (x + y) * (y + 2*z) * (3*x - z)
6 Likes
10

It looks like something has changed:

julia> using Nemo

julia> R, (x, y, z) = PolynomialRing(ZZ, ["x", "y", "z"])

ERROR: UndefVarError: `PolynomialRing` not defined
Stacktrace:
 [1] top-level scope
   @ REPL[2]:1

This is Nemo version 0.45.3.

@greatpet it would be great with an updated example.

11

It seems like PolynomialRing has been renamed to polynomial_ring. The following works:

julia> using Nemo
julia> R, (x, y, z) = polynomial_ring(ZZ, ["x", "y", "z"]);
julia> factor(-3*x^2*y-6*x^2*z-3*x*y^2-5*x*y*z+2*x*z^2+y^2*z+2*y*z^2)
-1 * (x + y) * (y + 2*z) * (3*x - z)
5 Likes