Algebraic Systems Solving

Introduction

AlgebraicSolving allows to solve systems for input generators over finite fields of characteristic smaller $2^{31}$ and over the rationals.

The underlying engine is provided by msolve.

Functionality

AlgebraicSolving.rational_parametrizationMethod
rational_parametrization(I::Ideal{T} where T <: MPolyRingElem, <keyword arguments>)

Given an ideal I with a finite solution set over the complex numbers, return the rational parametrization of the ideal with a given precision (default 32 bits).

Note: At the moment only QQ is supported as ground field. If the dimension of the ideal is greater then zero an empty array is returned.

Arguments

  • I::Ideal{T} where T <: MPolyRingElem: input generators.
  • initial_hts::Int=17: initial hash table size log_2.
  • nr_thrds::Int=1: number of threads for parallel linear algebra.
  • max_nr_pairs::Int=0: maximal number of pairs per matrix, only bounded by minimal degree if 0.
  • la_option::Int=2: linear algebra option: exact sparse-dense (1), exact sparse (2, default), probabilistic sparse-dense (42), probabilistic sparse(44).
  • info_level::Int=0: info level printout: off (0, default), summary (1), detailed (2).
  • precision::Int=32: bit precision for the computed solutions.

Examples

julia> using AlgebraicSolving

julia> R,(x1,x2,x3) = polynomial_ring(QQ, ["x1","x2","x3"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x1, x2, x3])

julia> I = Ideal([x1+2*x2+2*x3-1, x1^2+2*x2^2+2*x3^2-x1, 2*x1*x2+2*x2*x3-x2])
QQMPolyRingElem[x1 + 2*x2 + 2*x3 - 1, x1^2 - x1 + 2*x2^2 + 2*x3^2, 2*x1*x2 + 2*x2*x3 - x2]

julia> rational_parametrization(I)
AlgebraicSolving.RationalParametrization([:x1, :x2, :x3], ZZRingElem[], 84*x^4 - 40*x^3 + x^2 + x, 336*x^3 - 120*x^2 + 2*x + 1, AbstractAlgebra.PolyRingElem[184*x^3 - 80*x^2 + 4*x + 1, 36*x^3 - 18*x^2 + 2*x])
AlgebraicSolving.real_solutionsMethod
real_solutions(I::Ideal{T} where T <: MPolyRingElem, <keyword arguments>)

Given an ideal I with a finite solution set over the complex numbers, return the real roots of the ideal with a given precision (default 32 bits).

Note: At the moment only QQ is supported as ground field. If the dimension of the ideal is greater than zero an empty array is returned.

Arguments

  • I::Ideal{T} where T <: MPolyRingElem: input generators.
  • initial_hts::Int=17: initial hash table size log_2.
  • nr_thrds::Int=1: number of threads for parallel linear algebra.
  • max_nr_pairs::Int=0: maximal number of pairs per matrix, only bounded by minimal degree if 0.
  • la_option::Int=2: linear algebra option: exact sparse-dense (1), exact sparse (2, default), probabilistic sparse-dense (42), probabilistic sparse(44).
  • info_level::Int=0: info level printout: off (0, default), summary (1), detailed (2).
  • precision::Int=32: bit precision for the computed solutions.

Examples

julia> using AlgebraicSolving

julia> R,(x1,x2,x3) = polynomial_ring(QQ, ["x1","x2","x3"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x1, x2, x3])

julia> I = Ideal([x1+2*x2+2*x3-1, x1^2+2*x2^2+2*x3^2-x1, 2*x1*x2+2*x2*x3-x2])
QQMPolyRingElem[x1 + 2*x2 + 2*x3 - 1, x1^2 - x1 + 2*x2^2 + 2*x3^2, 2*x1*x2 + 2*x2*x3 - x2]

julia> real_solutions(I)
4-element Vector{Vector{QQFieldElem}}:
 [5416829397//8589934592, 2708414699//8589934592, -2844258330290649520990905062759917788583//21778071482940061661655974875633165533184]
 [1, 0, 0]
 [1945971683//8589934592, 972985841//8589934592, 744426424910260862653434112767010536665//2722258935367507707706996859454145691648]
 [2863311531//8589934592, 0, 3629678580490010276942662479272194255531//10889035741470030830827987437816582766592]
AlgebraicSolving.rational_solutionsMethod
rational_solutions(I::Ideal{T} where T <: MPolyRingElem, <keyword arguments>)

Given an ideal I with a finite solution set over the complex numbers, return the rational roots of the ideal.

Arguments

  • I::Ideal{T} where T <: MPolyRingElem: input generators.
  • initial_hts::Int=17: initial hash table size log_2.
  • nr_thrds::Int=1: number of threads for parallel linear algebra.
  • max_nr_pairs::Int=0: maximal number of pairs per matrix, only bounded by minimal degree if 0.
  • la_option::Int=2: linear algebra option: exact sparse-dense (1), exact sparse (2, default), probabilistic sparse-dense (42), probabilistic sparse(44).
  • info_level::Int=0: info level printout: off (0, default), summary (1), detailed (2).
  • precision::Int=32: bit precision for the computed solutions.

Examples

julia> using AlgebraicSolving

julia> R,(x1,x2,x3) = polynomial_ring(QQ, ["x1","x2","x3"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x1, x2, x3])

julia> I = Ideal([x1+2*x2+2*x3-1, x1^2+2*x2^2+2*x3^2-x1, 2*x1*x2+2*x2*x3-x2])
QQMPolyRingElem[x1 + 2*x2 + 2*x3 - 1, x1^2 - x1 + 2*x2^2 + 2*x3^2, 2*x1*x2 + 2*x2*x3 - x2]

julia> rat_sols = rational_solutions(I)
2-element Vector{Vector{QQFieldElem}}:
 [1, 0, 0]
 [1//3, 0, 1//3]

julia> map(r->map(p->evaluate(p, r), I.gens), rat_sols)
2-element Vector{Vector{QQFieldElem}}:
 [0, 0, 0]
 [0, 0, 0]