search_index.js

var documenterSearchIndex = {"docs":
[{"location":"groebner-bases/","page":"Gröbner bases","title":"Gröbner bases","text":"Pages = [\"groebner-bases.md\"]","category":"section"},{"location":"groebner-bases/#Gröbner-bases","page":"Gröbner bases","title":"Gröbner bases","text":"","category":"section"},{"location":"groebner-bases/#Introduction","page":"Gröbner bases","title":"Introduction","text":"AlgebraicSolving allows to compute Gröbner bases for input generators over prime fields of characteristic smaller 2^31 or over the rationals w.r.t. the degree reverse lexicographical monomial order.\n\nAt the moment different variants of Faugère's F4 Algorithm are implemented as well as a signature based algorithm to compute Gröbner bases.","category":"section"},{"location":"groebner-bases/#Functionality","page":"Gröbner bases","title":"Functionality","text":"The engine supports the elimination of one block of variables considering the product monomial ordering of two blocks, both ordered w.r.t. the degree reverse lexicographical order. One can either directly add the number of variables of the first block via the eliminate parameter in the groebner_basis call. By using intersect=false it is possible to only  use block ordering without intersecting. We have also implemented an alias  for this call:\n\nTo compute signature Gröbner bases use","category":"section"},{"location":"groebner-bases/#AlgebraicSolving.groebner_basis-Tuple{Ideal}","page":"Gröbner bases","title":"AlgebraicSolving.groebner_basis","text":"groebner_basis(I::Ideal{T} where T <: MPolyRingElem, <keyword arguments>)\n\nCompute a Groebner basis of the ideal I w.r.t. to the degree reverse lexicographical monomial ordering using Faugère's F4 algorithm. At the moment the underlying algorithm is based on variants of Faugère's F4 Algorithm.\n\nNote: At the moment only ground fields of characteristic p, p prime, p < 2^{31} and the rationals are supported.\n\nArguments\n\nI::Ideal{T} where T <: MPolyRingElem: input generators.\ninitial_hts::Int=17: initial hash table size log_2.\nnr_thrds::Int=1: number of threads for parallel linear algebra.\nmax_nr_pairs::Int=0: maximal number of pairs per matrix, only bounded by minimal degree if 0.\nla_option::Int=2: linear algebra option: exact sparse-dense (1), exact sparse (2, default), probabilistic sparse-dense (42), probabilistic sparse(44).\neliminate::Int=0: size of first block of variables to be eliminated.\nintersect::Bool=true: compute the eliminate-th elimination ideal.\ncomplete_reduction::Bool=true: compute a reduced Gröbner basis for I.\nnormalize::Bool=false: normalize generators of Gröbner basis for I, only applicable when working over the rationals.\ntruncate_lifting::Int=0: truncates the lifting process to given number of elements, only applicable when working over the rationals.\ninfo_level::Int=0: info level printout: off (0, default), summary (1), detailed (2).\n\nExamples\n\njulia> using AlgebraicSolving\n\njulia> R, (x,y,z) = polynomial_ring(GF(101),[\"x\",\"y\",\"z\"], internal_ordering=:degrevlex)\n(Multivariate polynomial ring in 3 variables over GF(101), FqMPolyRingElem[x, y, z])\n\njulia> I = Ideal([x+2*y+2*z-1, x^2+2*y^2+2*z^2-x, 2*x*y+2*y*z-y])\nFqMPolyRingElem[x + 2*y + 2*z + 100, x^2 + 2*y^2 + 2*z^2 + 100*x, 2*x*y + 2*y*z + 100*y]\n\njulia> groebner_basis(I)\n4-element Vector{FqMPolyRingElem}:\n x + 2*y + 2*z + 100\n y*z + 82*z^2 + 10*y + 40*z\n y^2 + 60*z^2 + 20*y + 81*z\n z^3 + 28*z^2 + 64*y + 13*z\n\njulia> groebner_basis(I, eliminate=2)\n1-element Vector{FqMPolyRingElem}:\n z^4 + 38*z^3 + 95*z^2 + 95*z\n\n\n\n\n\n","category":"method"},{"location":"groebner-bases/#AlgebraicSolving.eliminate-Tuple{Ideal, Int64}","page":"Gröbner bases","title":"AlgebraicSolving.eliminate","text":"eliminate(I::Ideal{T} where T <: MPolyRingElem, eliminate::Int,  <keyword arguments>)\n\nCompute a Groebner basis of the ideal I w.r.t. to the product monomial ordering defined by two blocks w.r.t. the degree reverse lexicographical monomial ordering using Faugère's F4 algorithm. Hereby the first block includes the first eliminate variables.\n\nAt the moment the underlying algorithm is based on variants of Faugère's F4 Algorithm.\n\nNote: At the moment only ground fields of characteristic p, p prime, p < 2^{31} and the rationals are supported.\n\nArguments\n\nI::Ideal{T} where T <: MPolyRingElem: input generators.\neliminate::Int=0: size of first block of variables to be eliminated.\nintersect::Bool=true: compute the eliminate-th elimination ideal.\ninitial_hts::Int=17: initial hash table size log_2.\nnr_thrds::Int=1: number of threads for parallel linear algebra.\nmax_nr_pairs::Int=0: maximal number of pairs per matrix, only bounded by minimal degree if 0.\nla_option::Int=2: linear algebra option: exact sparse-dense (1), exact sparse (2, default), probabilistic sparse-dense (42), probabilistic sparse(44).\ncomplete_reduction::Bool=true: compute a reduced Gröbner basis for I.\nnormalize::Bool=false: normalize generators of Gröbner basis for I, only applicable when working over the rationals.\ntruncate_lifting::Int=0: truncates the lifting process to given number of elements, only applicable when working over the rationals.\ninfo_level::Int=0: info level printout: off (0, default), summary (1), detailed (2).\n\nExamples\n\njulia> using AlgebraicSolving\n\njulia> R, (x,y,z) = polynomial_ring(GF(101),[\"x\",\"y\",\"z\"], internal_ordering=:degrevlex)\n(Multivariate polynomial ring in 3 variables over GF(101), FqMPolyRingElem[x, y, z])\n\njulia> I = Ideal([x+2*y+2*z-1, x^2+2*y^2+2*z^2-x, 2*x*y+2*y*z-y])\nFqMPolyRingElem[x + 2*y + 2*z + 100, x^2 + 2*y^2 + 2*z^2 + 100*x, 2*x*y + 2*y*z + 100*y]\n\njulia> eliminate(I, 2)\n1-element Vector{FqMPolyRingElem}:\n z^4 + 38*z^3 + 95*z^2 + 95*z\n\n\n\n\n\n","category":"method"},{"location":"groebner-bases/#AlgebraicSolving.sig_groebner_basis-Union{Tuple{Vector{T}}, Tuple{T}} where T<:MPolyRingElem","page":"Gröbner bases","title":"AlgebraicSolving.sig_groebner_basis","text":"sig_groebner_basis(sys::Vector{T}; info_level::Int=0, degbound::Int=0, mod_ord::Symbol=:POT) where {T <: MPolyRingElem}\n\nCompute a Signature Gröbner basis of the sequence sys w.r.t. to the degree reverse lexicographical monomial ordering and the module order mod_ord underlying the computation. The output is a vector of Tuple{Tuple{Int64, T}, T} where the first element indicates the signature and the second the underlying polynomial.\n\nNote: At the moment only ground fields of characteristic p, p prime, p < 2^{31} are supported. Note: If mod_ord == :DPOT then the input generators must be homogeneous. Note: The algorithms behaviour may depend heavily on how the elements in sys are sorted.\n\nArguments\n\nsys::Vector{T} where T <: MpolyElem: input generators.\ninfo_level::Int=0: info level printout: off (0, default), computational details (1)\ndegbound::Int=0: Compute a full Gröbner basis if 0 otherwise only up to degree degbound.\nmod_ord::Symbol=:DPOT: The module monomial order underlying the computation, either :POT (position-over-term, default) or :DPOT (degree-position-over-term) .\n\nExample\n\njulia> using AlgebraicSolving\n\njulia> R, vars = polynomial_ring(GF(17), [\"x$i\" for i in 1:4])\n(Multivariate polynomial ring in 4 variables over GF(17), FqMPolyRingElem[x1, x2, x3, x4])\n\njulia> F = cyclic(R)\nFqMPolyRingElem[x1 + x2 + x3 + x4, x1*x2 + x1*x4 + x2*x3 + x3*x4, x1*x2*x3 + x1*x2*x4 + x1*x3*x4 + x2*x3*x4, x1*x2*x3*x4 + 16]\n\njulia> Fhom = homogenize(F.gens)\n4-element Vector{FqMPolyRingElem}:\n x1 + x2 + x3 + x4\n x1*x2 + x2*x3 + x1*x4 + x3*x4\n x1*x2*x3 + x1*x2*x4 + x1*x3*x4 + x2*x3*x4\n x1*x2*x3*x4 + 16*x5^4\n\njulia> sig_groebner_basis(Fhom, mod_ord = :DPOT)\n7-element Vector{Tuple{Tuple{Int64, FqMPolyRingElem}, FqMPolyRingElem}}:\n ((1, 1), x1 + x2 + x3 + x4)\n ((2, 1), x2^2 + 2*x2*x4 + x4^2)\n ((3, 1), x2*x3^2 + x3^2*x4 + 16*x2*x4^2 + 16*x4^3)\n ((4, 1), x2*x3*x4^2 + x3^2*x4^2 + 16*x2*x4^3 + x3*x4^3 + 16*x4^4 + 16*x5^4)\n ((4, x3), x3^3*x4^2 + x3^2*x4^3 + 16*x3*x5^4 + 16*x4*x5^4)\n ((4, x2), x2*x4^4 + x4^5 + 16*x2*x5^4 + 16*x4*x5^4)\n ((4, x2*x3), x3^2*x4^4 + x2*x3*x5^4 + 16*x2*x4*x5^4 + x3*x4*x5^4 + 15*x4^2*x5^4)\n\n\n\n\n\n","category":"method"},{"location":"solvers/","page":"Algebraic Systems Solving","title":"Algebraic Systems Solving","text":"Pages = [\"solvers.md\"]","category":"section"},{"location":"solvers/#Algebraic-Systems-Solving","page":"Algebraic Systems Solving","title":"Algebraic Systems Solving","text":"","category":"section"},{"location":"solvers/#Introduction","page":"Algebraic Systems Solving","title":"Introduction","text":"AlgebraicSolving allows to solve systems for input generators over finite fields of characteristic smaller 2^31 and over the rationals.\n\nThe underlying engine is provided by msolve.","category":"section"},{"location":"solvers/#Functionality","page":"Algebraic Systems Solving","title":"Functionality","text":"","category":"section"},{"location":"solvers/#AlgebraicSolving.rational_parametrization-Tuple{Ideal}","page":"Algebraic Systems Solving","title":"AlgebraicSolving.rational_parametrization","text":"rational_parametrization(I::Ideal{T} where T <: MPolyRingElem, <keyword arguments>)\n\nGiven 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).\n\nNote: At the moment only QQ is supported as ground field. If the dimension of the ideal is greater than zero an ErrorException is thrown.\n\nArguments\n\nI::Ideal{T} where T <: MPolyRingElem: input generators.\ninitial_hts::Int=17: initial hash table size log_2.\nnr_thrds::Int=1: number of threads for parallel linear algebra.\nmax_nr_pairs::Int=0: maximal number of pairs per matrix, only bounded by minimal degree if 0.\nla_option::Int=2: linear algebra option: exact sparse-dense (1), exact sparse (2, default), probabilistic sparse-dense (42), probabilistic sparse(44).\ninfo_level::Int=0: info level printout: off (0, default), summary (1), detailed (2).\nprecision::Int=32: bit precision for the computed solutions.\n\nExamples\n\njulia> using AlgebraicSolving\n\njulia> R,(x1,x2,x3) = polynomial_ring(QQ, [\"x1\",\"x2\",\"x3\"])\n(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x1, x2, x3])\n\njulia> I = Ideal([x1+2*x2+2*x3-1, x1^2+2*x2^2+2*x3^2-x1, 2*x1*x2+2*x2*x3-x2])\nQQMPolyRingElem[x1 + 2*x2 + 2*x3 - 1, x1^2 - x1 + 2*x2^2 + 2*x3^2, 2*x1*x2 + 2*x2*x3 - x2]\n\njulia> rational_parametrization(I)\nAlgebraicSolving.RationalParametrization([:x1, :x2, :x3], ZZRingElem[], 84*x^4 - 40*x^3 + x^2 + x, 336*x^3 - 120*x^2 + 2*x + 1, Nemo.QQPolyRingElem[184*x^3 - 80*x^2 + 4*x + 1, 36*x^3 - 18*x^2 + 2*x])\n\n\n\n\n\n","category":"method"},{"location":"solvers/#AlgebraicSolving.real_solutions-Tuple{Ideal}","page":"Algebraic Systems Solving","title":"AlgebraicSolving.real_solutions","text":"real_solutions(I::Ideal{T} where T <: MPolyRingElem, <keyword arguments>)\n\nGiven 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).\n\nNote: At the moment only QQ is supported as ground field. If the dimension of the ideal is greater than zero an ErrorException is thrown.\n\nArguments\n\nI::Ideal{T} where T <: MPolyRingElem: input generators.\ninitial_hts::Int=17: initial hash table size log_2.\nnr_thrds::Int=1: number of threads for parallel linear algebra.\nmax_nr_pairs::Int=0: maximal number of pairs per matrix, only bounded by minimal degree if 0.\nla_option::Int=2: linear algebra option: exact sparse-dense (1), exact sparse (2, default), probabilistic sparse-dense (42), probabilistic sparse(44).\ninfo_level::Int=0: info level printout: off (0, default), summary (1), detailed (2).\nprecision::Int=32: bit precision for the computed solutions.\ninterval::Bool=false: return real solutions as intervals.\n\nExamples\n\njulia> using AlgebraicSolving\n\njulia> R,(x1,x2,x3) = polynomial_ring(QQ, [\"x1\",\"x2\",\"x3\"])\n(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x1, x2, x3])\n\njulia> I = Ideal([x1+2*x2+2*x3-1, x1^2+2*x2^2+2*x3^2-x1, 2*x1*x2+2*x2*x3-x2])\nQQMPolyRingElem[x1 + 2*x2 + 2*x3 - 1, x1^2 - x1 + 2*x2^2 + 2*x3^2, 2*x1*x2 + 2*x2*x3 - x2]\n\njulia> real_solutions(I)\n4-element Vector{Vector{QQFieldElem}}:\n [1454069069139182487//2305843009213693952, 1454069069139182487//4611686018427387904, -154187553040555781639//1180591620717411303424]\n [1, 0, 0]\n [8357884734418025835//36893488147419103232, 4178942367209012917//36893488147419103232, 40355437357166103123//147573952589676412928]\n [6148914691236517205//18446744073709551616, 123527304065019319//85070591730234615865843651857942052864, 196765270119568550571//590295810358705651712]\n\njulia> real_solutions(I, interval=true)\n4-element Vector{Vector{Vector{QQFieldElem}}}:\n [[11632552553113459895//18446744073709551616, 11632552553113459897//18446744073709551616], [5816276276556729947//18446744073709551616, 5816276276556729949//18446744073709551616], [-19273444130069472705//147573952589676412928, -77093776520277890819//590295810358705651712]]\n [[1, 1], [0, 0], [0, 0]]\n [[2089471183604506445//9223372036854775808, 4178942367209012945//18446744073709551616], [1044735591802253225//9223372036854775808, 2089471183604506467//18446744073709551616], [20177718678583051561//73786976294838206464, 10088859339291525781//36893488147419103232]]\n [[6148914691236517197//18446744073709551616, 6148914691236517213//18446744073709551616], [-9388075108941468237//170141183460469231731687303715884105728, 9882184325201545513//170141183460469231731687303715884105728], [98382635059784275285//295147905179352825856, 49191317529892137643//147573952589676412928]]\n\n\n\n\n\n","category":"method"},{"location":"solvers/#AlgebraicSolving.rational_solutions-Tuple{Ideal}","page":"Algebraic Systems Solving","title":"AlgebraicSolving.rational_solutions","text":"rational_solutions(I::Ideal{T} where T <: MPolyRingElem, <keyword arguments>)\n\nGiven an ideal I with a finite solution set over the complex numbers, return the rational roots of the ideal. \n\nArguments\n\nI::Ideal{T} where T <: MPolyRingElem: input generators.\ninitial_hts::Int=17: initial hash table size log_2.\nnr_thrds::Int=1: number of threads for parallel linear algebra.\nmax_nr_pairs::Int=0: maximal number of pairs per matrix, only bounded by minimal degree if 0.\nla_option::Int=2: linear algebra option: exact sparse-dense (1), exact sparse (2, default), probabilistic sparse-dense (42), probabilistic sparse(44).\ninfo_level::Int=0: info level printout: off (0, default), summary (1), detailed (2).\nprecision::Int=32: bit precision for the computed solutions.\n\nExamples\n\njulia> using AlgebraicSolving\n\njulia> R,(x1,x2,x3) = polynomial_ring(QQ, [\"x1\",\"x2\",\"x3\"])\n(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x1, x2, x3])\n\njulia> I = Ideal([x1+2*x2+2*x3-1, x1^2+2*x2^2+2*x3^2-x1, 2*x1*x2+2*x2*x3-x2])\nQQMPolyRingElem[x1 + 2*x2 + 2*x3 - 1, x1^2 - x1 + 2*x2^2 + 2*x3^2, 2*x1*x2 + 2*x2*x3 - x2]\n\njulia> rat_sols = rational_solutions(I)\n2-element Vector{Vector{QQFieldElem}}:\n [1//3, 0, 1//3]\n [1, 0, 0]\n\njulia> map(r->map(p->evaluate(p, r), I.gens), rat_sols)\n2-element Vector{Vector{QQFieldElem}}:\n [0, 0, 0]\n [0, 0, 0]\n\n\n\n\n\n","category":"method"},{"location":"solvers/#AlgebraicSolving.rational_curve_parametrization-Tuple{Ideal{P} where P<:QQMPolyRingElem}","page":"Algebraic Systems Solving","title":"AlgebraicSolving.rational_curve_parametrization","text":"rational_curve_parametrization(I::Ideal{T} where T <: MPolyRingElem, <keyword arguments>)\n\nGiven a radical ideal I with solution set X being of dimension 1 over the complex numbers, return a rational curve parametrization of the one-dimensional irreducible components of X.\n\nIn the output, the variables x,y of the parametrization correspond to the last two entries of the vars attribute, in that order.\n\nNote: At the moment only QQ is supported as ground field. If the dimension of the ideal is not one an ErrorException is thrown.\n\nArguments\n\nI::Ideal{T} where T <: QQMPolyRingElem: input generators.\ninfo_level::Int=0: info level printout: off (0, default), summary (1), detailed (2).\nuse_lfs::Bool=false: add new variables (_Z2, _Z1) + 2 generic linear forms\ncfs_lfs::Vector{Vector{ZZRingElem}} = []: coefficients for the above linear forms\nnr_thrds::Int=1: number of threads for msolve\ncheck_gen::Bool = true: perform some genericity position checks on the last two variables\n\nExamples\n\njulia> using AlgebraicSolving\n\njulia> R, (x1,x2,x3) = polynomial_ring(QQ, [\"x1\",\"x2\",\"x3\"])\n(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x1, x2, x3])\n\njulia> I = Ideal([x1+2*x2+2*x3-1, x1^2+2*x2^2+2*x3^2-x1])\nQQMPolyRingElem[x1 + 2*x2 + 2*x3 - 1, x1^2 - x1 + 2*x2^2 + 2*x3^2]\n\njulia> rational_curve_parametrization(I)\nAlgebraicSolving.RationalCurveParametrization([:x1, :x2, :x3], Vector{ZZRingElem}[], x^2 + 4//3*x*y - 1//3*x + y^2 - 1//3*y, 4//3*x + 2*y - 1//3, QQMPolyRingElem[4//3*x^2 - 4//3*x*y + 2//3*x + 4//3*y - 1//3])\n\njulia> rational_curve_parametrization(I, cfs_lfs=map.(Ref(ZZ),[[-8,2,2,-1,-8], [8,-7,-5,8,-7]]))\nAlgebraicSolving.RationalCurveParametrization([:x1, :x2, :x3, :_Z2, :_Z1], Vector{ZZRingElem}[[-8, 2, 2, -1, -8], [8, -7, -5, 8, -7]], 4963//30508*x^2 - 6134//7627*x*y - 647//7627*x + y^2 + 1640//7627*y + 88//7627, -6134//7627*x + 2*y + 1640//7627, QQMPolyRingElem[8662//22881*x^2 - 21442//22881*x*y - 2014//7627*x + 9458//22881*y + 1016//22881, -2769//30508*x^2 + 4047//15254*x*y - 875//7627*x + 3224//7627*y + 344//7627, -9017//91524*x^2 + 9301//45762*x*y - 1185//7627*x + 8480//22881*y + 920//22881])\n\n\n\n\n\n","category":"method"},{"location":"decomposition/","page":"Equidimensional Decomposition","title":"Equidimensional Decomposition","text":"Pages = [\"decomposition.md\"]","category":"section"},{"location":"decomposition/#Equidimensional-Decomposition","page":"Equidimensional Decomposition","title":"Equidimensional Decomposition","text":"","category":"section"},{"location":"decomposition/#Introduction","page":"Equidimensional Decomposition","title":"Introduction","text":"AlgebraicSolving allows to compute equidimensional decompositions of polynomial ideals. This is to be understood in a geometric sense, i.e. given a polynomial ideal I it computes ideals I_1dotsI_k s.t. V(I)=bigcup_i=1^k V(I_j) and such that each V(I_j) is equidimensional.\n\nThe implemented algorithm is the one given in this paper.","category":"section"},{"location":"decomposition/#Functionality","page":"Equidimensional Decomposition","title":"Functionality","text":"","category":"section"},{"location":"decomposition/#AlgebraicSolving.equidimensional_decomposition-Union{Tuple{Ideal{T}}, Tuple{T}} where T<:MPolyRingElem","page":"Equidimensional Decomposition","title":"AlgebraicSolving.equidimensional_decomposition","text":"equidimensional_decomposition(I::Ideal{T}, info_level::Int=0) where {T <: MPolyRingElem}\n\nGiven a polynomial ideal I, return a list of ideals dec s.t. each ideal in dec is equidimensional (i.e. has minimal primes only of one fixed dimension) and s.t. the radical of I equals the intersection of the radicals of the ideals in dec.\n\nNote: At the moment only ground fields of characteristic p, p prime, p < 2^{31} are supported.\n\nArguments\n\nI::Ideal{T} where T <: MpolyElem: input ideal.\ninfo_level::Int=0: info level printout: off (0, default), computational details (1)\n\nExample\n\njulia> using AlgebraicSolving\n\njulia> R, (x, y, z) = polynomial_ring(GF(65521), [\"x\", \"y\", \"z\"])\n(Multivariate polynomial ring in 3 variables over GF(65521), FqMPolyRingElem[x, y, z])\n\njulia> I = Ideal([x*y - x*z, x*z^2 - x*z, x^2*z - x*z])\nFqMPolyRingElem[x*y + 65520*x*z, x*z^2 + 65520*x*z, x^2*z + 65520*x*z]\n\njulia> equidimensional_decomposition(I)\n3-element Vector{Ideal{FqMPolyRingElem}}:\n FqMPolyRingElem[x]\n FqMPolyRingElem[z, y]\n FqMPolyRingElem[z + 65520, y + 65520, x + 65520]\n\n\n\n\n\n","category":"method"},{"location":"katsura/","page":"Examples","title":"Examples","text":"Pages = [\"katsura.md\"]","category":"section"},{"location":"katsura/#Examples","page":"Examples","title":"Examples","text":"Here we include some well-known example multivariate polynomial systems.","category":"section"},{"location":"katsura/#Katsura-n","page":"Examples","title":"Katsura-n","text":"These systems appeared in a problem of magnetism in physics. For a given n katsura(n) has 2^n solutions and is defined in a polynomial ring with n+1 variables. For a given polynomial ring R with n variables katsura(R) defines the corresponding system with 2^n-1 solutions.","category":"section"},{"location":"katsura/#Functionality","page":"Examples","title":"Functionality","text":"","category":"section"},{"location":"katsura/#AlgebraicSolving.katsura-Tuple{Int64}","page":"Examples","title":"AlgebraicSolving.katsura","text":"katsura(n::Int)\n\nGiven a natural number n returns the Katsura ideal generated by u_m - sum_l=n^n u_l-m u_l, 1 - sum_l = -n^n u_l where u_-i = u_i, and u_i = 0 for i  n and m in -n ldots n. Also note that indices have been shifted to start from 1.\n\nExample\n\njulia> using AlgebraicSolving\n\njulia> katsura(2)\nQQMPolyRingElem[x1 + 2*x2 + 2*x3 - 1, x1^2 + 2*x2^2 + 2*x3^2 - x1, 2*x1*x2 + 2*x2*x3 - x2]\n\n\n\n\n\n","category":"method"},{"location":"katsura/#AlgebraicSolving.katsura-Tuple{MPolyRing}","page":"Examples","title":"AlgebraicSolving.katsura","text":"katsura(R::MPolyRing)\n\nReturns the Katsura ideal in the given polynomial ring R.\n\nExample\n\njulia> using AlgebraicSolving\n\njulia> R, _ = QQ[\"x\", \"y\", \"z\"]\n(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])\n\njulia> katsura(R)\nQQMPolyRingElem[x + 2*y + 2*z - 1, x^2 - x + 2*y^2 + 2*z^2, 2*x*y + 2*y*z - y]\n\n\n\n\n\n","category":"method"},{"location":"normal-forms/","page":"Normal forms","title":"Normal forms","text":"Pages = [\"normal-forms.md\"]","category":"section"},{"location":"normal-forms/#Normal-forms","page":"Normal forms","title":"Normal forms","text":"","category":"section"},{"location":"normal-forms/#Introduction","page":"Normal forms","title":"Introduction","text":"AlgebraicSolving allows to compute normal forms of a polynomial resp. a finite array of polynomials w.r.t. some given ideal over a finite field of characteristic smaller 2^31 w.r.t. the degree reverse lexicographical monomial order.\n\nNote: It therefore might first compute a Gröbner bases for the ideal.","category":"section"},{"location":"normal-forms/#Functionality","page":"Normal forms","title":"Functionality","text":"","category":"section"},{"location":"normal-forms/#AlgebraicSolving.normal_form-Union{Tuple{T}, Tuple{T, Ideal{T}}} where T<:MPolyRingElem","page":"Normal forms","title":"AlgebraicSolving.normal_form","text":"normal_form(\n    f::T,\n    I::Ideal{T};\n    nr_thrds::Int=1,\n    info_level::Int=0\n    ) where T <: MPolyRingElem\n\nCompute the normal forms of the elements of F w.r.t. a degree reverse lexicographical Gröbner basis of I.\n\nNote: If I has not already cached a degree reverse lexicographical Gröbner basis, then this one is first computed.\n\nArguments\n\nF::Vector{T} where T <: MPolyRingElem: elements to be reduced.\nI::Ideal{T} where T <: MPolyRingElem: ideal data to reduce with.\nnr_thrds::Int=1: number of threads for parallel linear algebra.\ninfo_level::Int=0: info level printout: off (0, default), summary (1), detailed (2).\n\nExamples\n\njulia> using AlgebraicSolving\n\njulia> R, (x,y) = polynomial_ring(GF(101),[\"x\",\"y\"])\n(Multivariate polynomial ring in 2 variables over GF(101), FqMPolyRingElem[x, y])\n\njulia> I = Ideal([y*x^3+12-y, x+y])\nFqMPolyRingElem[x^3*y + 100*y + 12, x + y]\n\njulia> f = 2*x^2+7*x*y\n2*x^2 + 7*x*y\n\njulia> normal_form(f, I)\n96*y^2\n\n\n\n\n\n","category":"method"},{"location":"normal-forms/#AlgebraicSolving.normal_form-Union{Tuple{T}, Tuple{Vector{T}, Ideal{T}}} where T<:MPolyRingElem","page":"Normal forms","title":"AlgebraicSolving.normal_form","text":"normal_form(\n    F::Vector{T},\n    I::Ideal{T};\n    nr_thrds::Int=1,\n    info_level::Int=0\n    ) where T <: MPolyRingElem\n\nCompute the normal forms of the elements of F w.r.t. a degree reverse lexicographical Gröbner basis of I.\n\nNote: If I has not already cached a degree reverse lexicographical Gröbner basis, then this one is first computed.\n\nArguments\n\nF::Vector{T} where T <: MPolyRingElem: elements to be reduced.\nI::Ideal{T} where T <: MPolyRingElem: ideal data to reduce with.\nnr_thrds::Int=1: number of threads for parallel linear algebra.\ninfo_level::Int=0: info level printout: off (0, default), summary (1), detailed (2).\n\nExamples\n\njulia> using AlgebraicSolving\n\njulia> R, (x,y) = polynomial_ring(GF(101),[\"x\",\"y\"])\n(Multivariate polynomial ring in 2 variables over GF(101), FqMPolyRingElem[x, y])\n\njulia> I = Ideal([y*x^3+12-y, x+y])\nFqMPolyRingElem[x^3*y + 100*y + 12, x + y]\n\njulia> F = [2*x^2+7*x*y, x+y]\n2-element Vector{FqMPolyRingElem}:\n 2*x^2 + 7*x*y\n x + y\n\njulia> normal_form(F,I)\n2-element Vector{FqMPolyRingElem}:\n 96*y^2\n 0\n\n\n\n\n\n","category":"method"},{"location":"hilbert/","page":"Hilbert series of an ideal","title":"Hilbert series of an ideal","text":"Pages = [\"hilbert.md\"]","category":"section"},{"location":"hilbert/#Hilbert-series-of-an-ideal","page":"Hilbert series of an ideal","title":"Hilbert series of an ideal","text":"","category":"section"},{"location":"hilbert/#Introduction","page":"Hilbert series of an ideal","title":"Introduction","text":"AlgebraicSolving allows to compute the Hilbert series for the ideal spanned by given input generators over finite fields of characteristic smaller 2^31 and over the rationals.\n\nThe underlying engine is provided by msolve.","category":"section"},{"location":"hilbert/#Functionality","page":"Hilbert series of an ideal","title":"Functionality","text":"In addition, from the same input, AlgebraicSolving can also compute the dimension and degree of the ideal, as well as the Hilbert polynomial and index of regularity.","category":"section"},{"location":"hilbert/#AlgebraicSolving.hilbert_series-Union{Tuple{Ideal{T}}, Tuple{T}} where T<:MPolyRingElem","page":"Hilbert series of an ideal","title":"AlgebraicSolving.hilbert_series","text":"hilbert_series(I::Ideal{T}) where T <: MPolyRingElem\n\nCompute the Hilbert series of a given polynomial ideal I.\n\nBased on: Anna M. Bigatti, Computation of Hilbert-Poincaré series, Journal of Pure and Applied Algebra, 1997.\n\nNotes:\n\nThis requires a Gröbner basis of I, which is computed internally if not already known.\nSignificantly faster when internal_ordering is :degrevlex.\n\nExamples\n\njulia> using AlgebraicSolving\n\njulia> R, (x, y, z) = polynomial_ring(QQ, [\"x\", \"y\", \"z\"]);\n\njulia> I = Ideal([x*y,x*z,y*z]);\n\njulia> hilbert_series(I)\n(-2*t - 1)//(t - 1)\n\n\n\n\n\n","category":"method"},{"location":"hilbert/#AlgebraicSolving.hilbert_dimension-Union{Tuple{Ideal{T}}, Tuple{T}} where T<:MPolyRingElem","page":"Hilbert series of an ideal","title":"AlgebraicSolving.hilbert_dimension","text":"hilbert_dimension(I::Ideal{T}) where T <: MPolyRingElem\n\nCompute the Krull dimension of a given polynomial ideal I by first computing its Hilbert series.\n\nNote: This requires a Gröbner basis of I, which is computed internally if not already known.\n\nExamples\n\njulia> using AlgebraicSolving\n\njulia> R, (x, y, z) = polynomial_ring(QQ, [\"x\", \"y\", \"z\"]);\n\njulia> I = Ideal([x*y,x*z,y*z]);\n\njulia> hilbert_dimension(I)\n1\n\n\n\n\n\n","category":"method"},{"location":"hilbert/#AlgebraicSolving.hilbert_degree-Union{Tuple{Ideal{T}}, Tuple{T}} where T<:MPolyRingElem","page":"Hilbert series of an ideal","title":"AlgebraicSolving.hilbert_degree","text":"hilbert_degree(I::Ideal{T}) where T <: MPolyRingElem\n\nCompute the degree of a given polynomial ideal I by first computing its Hilbert series.\n\nNote: This requires a Gröbner basis of I, which is computed internally if not already known.\n\nExamples\n\njulia> using AlgebraicSolving\n\njulia> R, (x, y, z) = polynomial_ring(QQ, [\"x\", \"y\", \"z\"]);\n\njulia> I = Ideal([x*y,x*z,y*z]);\n\njulia> hilbert_degree(I)\n3\n\n\n\n\n\n","category":"method"},{"location":"hilbert/#AlgebraicSolving.hilbert_polynomial-Union{Tuple{Ideal{T}}, Tuple{T}} where T<:MPolyRingElem","page":"Hilbert series of an ideal","title":"AlgebraicSolving.hilbert_polynomial","text":"hilbert_polynomial(I::Ideal{T}) where T <: MPolyRingElem\n\nCompute the Hilbert polynomial and the index of regularity of a given polynomial ideal I by first computing its Hilbert series. The index of regularity is the smallest integer such that the Hilbert function and polynomial match.\n\nNote that the Hilbert polynomial of I has leading term (e/d!)*t^d, where e and d are respectively the degree and Krull dimension of I.\n\nNote: This requires a Gröbner basis of I, which is computed internally if not already known.\n\nExamples\n\njulia> using AlgebraicSolving\n\njulia> R, (x, y, z) = polynomial_ring(QQ, [\"x\", \"y\", \"z\"]);\n\njulia> I = Ideal([x*y,x*z,y*z]);\n\njulia> hilbert_polynomial(I)\n(3*s + 3, 1)\n\n\n\n\n\n","category":"method"},{"location":"dimension/","page":"Krull dimension of an ideal","title":"Krull dimension of an ideal","text":"Pages = [\"dimension.md\"]","category":"section"},{"location":"dimension/#Krull-dimension-of-an-ideal","page":"Krull dimension of an ideal","title":"Krull dimension of an ideal","text":"","category":"section"},{"location":"dimension/#Introduction","page":"Krull dimension of an ideal","title":"Introduction","text":"AlgebraicSolving allows to compute the Krull dimension for the ideal spanned by given input generators over finite fields of characteristic smaller 2^31 and over the rationals.\n\nThe underlying engine is provided by msolve.","category":"section"},{"location":"dimension/#Functionality","page":"Krull dimension of an ideal","title":"Functionality","text":"","category":"section"},{"location":"dimension/#AlgebraicSolving.dimension-Union{Tuple{Ideal{T}}, Tuple{T}} where T<:MPolyRingElem","page":"Krull dimension of an ideal","title":"AlgebraicSolving.dimension","text":"dimension(I::Ideal{T}) where T <: MPolyRingElem\n\nCompute the Krull dimension of a given polynomial ideal I.\n\nNote: This requires a Gröbner basis of I, which is computed internally if not already known.\n\nExamples\n\njulia> using AlgebraicSolving\n\njulia> R, (x, y, z) = polynomial_ring(QQ, [\"x\", \"y\", \"z\"]);\n\njulia> I = Ideal([x*y,x*z,y*z]);\n\njulia> dimension(I)\n1\n\n\n\n\n\n","category":"method"},{"location":"#Getting-Started","page":"Getting Started","title":"Getting Started","text":"AlgebraicSolving is a computer algebra package for the Julia programming  language, maintained by Christian Eder, Mohab Safey El Din, Rafael Mohr, Rémi Prébet.\n\nhttps://github.com/algebraic-solving/AlgebraicSolving.jl (Source code)\n\nThe features of AlgebraicSolving include algorithms for computing Gröbner bases over finite fields and for computing real solutions. The main workhorse of AlgebraicSolving is the msolve library .","category":"section"},{"location":"#Installation","page":"Getting Started","title":"Installation","text":"To use Nemo we require Julia 1.6 or higher. Please see https://julialang.org/downloads/ for instructions on how to obtain julia for your system.\n\nAt the Julia prompt simply type\n\njulia> using Pkg; Pkg.add(\"AlgebraicSolving\")","category":"section"},{"location":"types/","page":"Data Types","title":"Data Types","text":"Pages = [\"types.md\"]","category":"section"},{"location":"types/#Data-Types","page":"Data Types","title":"Data Types","text":"","category":"section"},{"location":"types/#Introduction","page":"Data Types","title":"Introduction","text":"AlgebraicSolving handles ideals in multivariate polynomial rings over a prime  field of characteristic 0 or p where p is a prime number 2^31.","category":"section"},{"location":"types/#Polynomial-Rings","page":"Data Types","title":"Polynomial Rings","text":"We use Nemo's multivariate polynomial  ring structures:\n\nusing AlgebraicSolving\nR, (x,y,z) = polynomial_ring(QQ, [\"x\", \"y\", \"z\"], internal_ordering=:degrevlex)\n\nThe above example defines a multivariate polynomial ring in three variables x,  y, and z over the rationals using the dgree reverse lexicographical ordering  for printing polynomials in the following. One can also define polynomial rings  over finite fields:\n\nusing AlgebraicSolving\nR, (x,y,z) = polynomial_ring(GF(101), [\"x\", \"y\", \"z\"], internal_ordering=:degrevlex)","category":"section"},{"location":"types/#Ideals","page":"Data Types","title":"Ideals","text":"Ideals can be constructed by giving an array of generators. Ideals cache varies  data structures connected to ideals in order to make computational algebra more  effective:\n\nusing AlgebraicSolving\nR, (x,y,z) = polynomial_ring(QQ, [\"x\", \"y\", \"z\"], internal_ordering=:degrevlex)\nI = Ideal([x+y+1, y*z^2-13*y^2])","category":"section"}]
}