# 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 than zero an ErrorException is thrown.

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 ErrorException is thrown.

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.
• interval::Bool=false: return real solutions as intervals.

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]

julia> real_solutions(I, interval=true)
4-element Vector{Vector{Vector{QQFieldElem}}}:
[[1354207349//2147483648, 2708414699//4294967296], [1354207349//4294967296, 677103675//2147483648], [-355532291286331190123863132844989723573//2722258935367507707706996859454145691648, -1422129165145324760495452531379958894291//10889035741470030830827987437816582766592]]
[[1, 1], [0, 0], [0, 0]]
[[972985841//4294967296, 486492921//2147483648], [60811615//536870912, 486492921//4294967296], [93053303113782607831679264095876317083//340282366920938463463374607431768211456, 372213212455130431326717056383505268333//1361129467683753853853498429727072845824]]
[[1431655765//4294967296, 715827883//2147483648], [-1//4294967296, 1//4294967296], [1814839290245005138471331239636097127765//5444517870735015415413993718908291383296, 907419645122502569235665619818048563883//2722258935367507707706996859454145691648]]
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]