AngouriMath

Navigation

Home Quick start Wiki Almanac Research What's new Try Use Angouri.org GitHub Report a bug Donate Contacts

AngouriMath.Functions.Algebra.Groebner

← Back to list of namespaces

Classes within the AngouriMath.Functions.Algebra.Groebner namespace

• Buchberger

  Summary

  Buchberger's algorithm, with the Gebauer–Möller pair criteria.

• Fglm

  Summary

  Converts a degree-reverse-lexicographic Gröbner basis of a zero-dimensional ideal
  into the lexicographic one.
  

  Remarks

  Needed because the two orders are good at opposite things. Degrevlex is what can be
  computed; lexicographic is what can be back-substituted, because its basis is
  triangular and leaves the last variable a univariate polynomial with rational
  coefficients. So the system is solved in one order and answered in the other.
  The conversion is linear algebra rather than more Buchberger. For a zero-dimensional
  ideal the quotient ring is a finite-dimensional vector space spanned by the monomials
  no leading term divides, so every monomial reduces to a point in it. Walking
  monomials in lexicographic order and asking which is the first to be a combination of
  those already seen produces the basis directly: each dependency *is* an element, and
  the coefficients of the combination are its terms.
  The cost is governed by the dimension of that space, which is the number of solutions
  counted with multiplicity — a different quantity from anything that bounds Buchberger.
  A system can have a basis that computes in milliseconds and a conversion that does
  not finish, so MaxQuotientDimension is checked before any
  of the work below is done rather than discovered partway through it.
  

• GroebnerBudget

  Summary

  What a Gröbner computation is allowed to spend before it gives up.
  

  Remarks

  Buchberger is doubly exponential in the worst case, so declining has to be reachable:
  a caller waiting forever is a worse answer than "not this one". Four separate
  ceilings because the ways it runs away are not the same — a system can blow up in the
  number of pairs, in the size of one polynomial, in the width of the rationals while
  everything else stays small, or in none of those while simply taking too long.
  Coefficient width is here because it is the one that actually fires: a system has
  been seen to give up with 53 pairs and 64 terms and coefficients 188 digits wide,
  which no count of pairs or terms would have caught.
  

• GroebnerSystemSolver

  Summary

  Solves a system of polynomial equations over Q by triangularising it, for the
  systems where that can be done and answered exactly.
  

  Remarks

  The solver this sits in front of eliminates one variable at a time by calling
  SolveEquation(AngouriMath.Entity.Variable), which applies the closed-form radical
  formulas. With numeric coefficients those are cheap; with symbolic ones they are not,
  and since each elimination turns the next one's coefficients into nested radicals the
  size compounds. Four coupled variables did not finish in three hundred seconds, while
  four uncoupled ones with 256 solutions took seventeen milliseconds — the cost was
  never the size of the system, it was eliminating in radicals.
  A Gröbner basis eliminates without them: the lexicographic basis is triangular and
  leaves the last variable a univariate polynomial with rational coefficients, which
  the existing polynomial solver already handles. The basis is computed under
  degree-reverse-lexicographic, which is the order that can actually be computed, and
  converted by Fglm.
  It answers only where it can check its own answer. Every candidate goes back
  into the original equations and is kept only if they reduce to exactly zero. That
  covers rational and radical solutions — x^2 - 2, y - x comes back as
  (sqrt(2), sqrt(2)) and (-sqrt(2), -sqrt(2)) — because one structural
  pass is enough to prove a radical identity. Where a root is a decimal the check cannot
  be made at all, and rather than accept a tuple on a tolerance, which is how a root
  that is merely close becomes a reported solution, the whole system goes back to the
  existing solver. So this takes what it can prove and declines the rest without
  changing what those did before.