Factoring multivariate polynomials

[serenity4]

Are multivariate polynomials planned to be supported, or does this package focuses specifically on univariate polynomials?

For example, I would be interested in performing the following factorization:

using AbstractAlgebra, PolynomialFactors

R, (a, b, c, d) = ZZ["a", "b", "c", "d"]

p = (a + b) * (c + d)

pf = poly_factor(p)

which currently results in this error:

Thrown error

```julia ERROR: MethodError: no method matching iterate(::AbstractAlgebra.Generic.MPoly{BigInt}) Closest candidates are: iterate(::Union{LinRange, StepRangeLen}) @ Base range.jl:887 iterate(::Union{LinRange, StepRangeLen}, ::Integer) @ Base range.jl:887 iterate(::T) where T<:Union{Base.KeySet{<:Any, <:Dict}, Base.ValueIterator{<:Dict}} @ Base dict.jl:716 ... Stacktrace: [1] iterate @ ./iterators.jl:206 [inlined] [2] iterate @ ./iterators.jl:205 [inlined] [3] _foldl_impl(op::Base.MappingRF{PolynomialFactors.var"#5#6"{AbstractAlgebra.Generic.Poly{BigInt}}, Base.BottomRF{typeof(Base.add_sum)}}, init::Base._InitialValue, itr::Base.Iterators.Enumerate{AbstractAlgebra.Generic.MPoly{BigInt}}) @ Base ./reduce.jl:56 [4] foldl_impl(op::Base.MappingRF{PolynomialFactors.var"#5#6"{AbstractAlgebra.Generic.Poly{BigInt}}, Base.BottomRF{typeof(Base.add_sum)}}, nt::Base._InitialValue, itr::Base.Iterators.Enumerate{AbstractAlgebra.Generic.MPoly{BigInt}}) @ Base ./reduce.jl:48 [5] mapfoldl_impl(f::typeof(identity), op::typeof(Base.add_sum), nt::Base._InitialValue, itr::Base.Generator{Base.Iterators.Enumerate{AbstractAlgebra.Generic.MPoly{BigInt}}, PolynomialFactors.var"#5#6"{AbstractAlgebra.Generic.Poly{BigInt}}}) @ Base ./reduce.jl:44 [6] mapfoldl(f::Function, op::Function, itr::Base.Generator{Base.Iterators.Enumerate{AbstractAlgebra.Generic.MPoly{BigInt}}, PolynomialFactors.var"#5#6"{AbstractAlgebra.Generic.Poly{BigInt}}}; init::Base._InitialValue) @ Base ./reduce.jl:175 [7] mapfoldl(f::Function, op::Function, itr::Base.Generator{Base.Iterators.Enumerate{AbstractAlgebra.Generic.MPoly{BigInt}}, PolynomialFactors.var"#5#6"{AbstractAlgebra.Generic.Poly{BigInt}}}) @ Base ./reduce.jl:175 [8] mapreduce(f::Function, op::Function, itr::Base.Generator{Base.Iterators.Enumerate{AbstractAlgebra.Generic.MPoly{BigInt}}, PolynomialFactors.var"#5#6"{AbstractAlgebra.Generic.Poly{BigInt}}}; kw::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}}) @ Base ./reduce.jl:307 [9] mapreduce(f::Function, op::Function, itr::Base.Generator{Base.Iterators.Enumerate{AbstractAlgebra.Generic.MPoly{BigInt}}, PolynomialFactors.var"#5#6"{AbstractAlgebra.Generic.Poly{BigInt}}}) @ Base ./reduce.jl:307 [10] sum(f::Function, a::Base.Generator{Base.Iterators.Enumerate{AbstractAlgebra.Generic.MPoly{BigInt}}, PolynomialFactors.var"#5#6"{AbstractAlgebra.Generic.Poly{BigInt}}}; kw::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}}) @ Base ./reduce.jl:535 [11] sum(f::Function, a::Base.Generator{Base.Iterators.Enumerate{AbstractAlgebra.Generic.MPoly{BigInt}}, PolynomialFactors.var"#5#6"{AbstractAlgebra.Generic.Poly{BigInt}}}) @ Base ./reduce.jl:535 [12] sum(a::Base.Generator{Base.Iterators.Enumerate{AbstractAlgebra.Generic.MPoly{BigInt}}, PolynomialFactors.var"#5#6"{AbstractAlgebra.Generic.Poly{BigInt}}}; kw::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}}) @ Base ./reduce.jl:564 [13] sum(a::Base.Generator{Base.Iterators.Enumerate{AbstractAlgebra.Generic.MPoly{BigInt}}, PolynomialFactors.var"#5#6"{AbstractAlgebra.Generic.Poly{BigInt}}}) @ Base ./reduce.jl:564 [14] as_poly(as::AbstractAlgebra.Generic.MPoly{BigInt}, x::AbstractAlgebra.Generic.Poly{BigInt}) @ PolynomialFactors ~/.julia/packages/PolynomialFactors/lsPmn/src/polyutils.jl:53 [15] as_poly(as::AbstractAlgebra.Generic.MPoly{BigInt}, x0::String) @ PolynomialFactors ~/.julia/packages/PolynomialFactors/lsPmn/src/polyutils.jl:64 [16] as_poly(as::AbstractAlgebra.Generic.MPoly{BigInt}) @ PolynomialFactors ~/.julia/packages/PolynomialFactors/lsPmn/src/polyutils.jl:63 [17] poly_factor(as::AbstractAlgebra.Generic.MPoly{BigInt}) @ PolynomialFactors ~/.julia/packages/PolynomialFactors/lsPmn/src/factor_zx.jl:430 [18] top-level scope @ ~/.julia/dev/SymbolicGA/experiments.jl:8 ```

I noticed that only univariate polynomials are covered in the test suite, which suggests that multivariate polynomials were not really considered. If so, would it take a lot of work to support them?

[jverzani]

I'd like to say yes, but realistically not anytime before the summer, and even then just maybe. So for now, just univariate and still not as performant as I'm sure this could be made.

[serenity4]

I see, thanks. I did some digging and it sounds like implementing it is quite some work, but fortunately most (all?) approaches seem to rely on reducing that case to that of univariate polynomial factorization (and then getting back to the multivariate form in some appropriate way).

Anyways, I figured out that I might not need this functionality in the end, but we can keep the issue open in case others might need it (and that would be nice functionality to have since AFAIK no package provides it in Julia).