Skip to content

Groebner Base and Orderings in Oscar

Jump to bottom
wbhart edited this page Nov 5, 2021 · 45 revisions

Dates: 4-8 Oct 2021 (10:30 am - 6:30 pm)

Location: TU Kaiserslautern Building 48, Room 419

Participants

  • Anne Frühbis-Krüger
  • Matthias Zach
  • Janko Boehm
  • Hans Schönemann
  • Dan Schultz
  • Rafael Mohr (Remote)
  • Jordi Welp
  • Christian Eder (Remote)
  • Julien Schanz
  • Wolfram Decker
  • Claus Fieker
  • William Hart
  • Coronavirus (*)

Topics

  1. Local and global orderings and module orderings interface (Monday)
  2. Local rings interface
  3. Noncommutative Groebner bases
  4. Documentation
  5. LibSing library interface
  6. Groebner Bases examples database
  7. Short presentations on Groebner basis applications/algorithms by participants (Wednesday)

PolynomialRing/Module orderings : TODO list

  • Add test cases for poly ring orderings that are NOT specified by a symbol
  • add missing monomial orderings
  • add weight vectors
  • add module orderings (combined with monomial orderings via concatenation)
  • add documentation for monomial orderings (incl. block and weighted orderings)
  • Fix _isless functions for weighted orderings (for sorting MPolys with specified ordering)
  • add documentation for module orderings
  • Groebner basis for ideals use new orderings
  • groebner_basis_with_transform/transformation_matrix use new ordering types
  • implement leading_ideal, etc. for orderings that are NOT specified by a symbol
  • make the function weights accept new orderings
  • add Block matrices to AbstractAlgebra
  • add weight matrices for block orderings
  • print module orderings better
  • singular_assure/groebner_assure with orderings
  • version of groebner_assure in ModStdQ that takes ordering
  • allow BiPolyArray constructor to take an ordering
  • Raise exception on functions expect an ordering that get a partial ordering (full rank matrix), cache rank_check
  • Test matrix orderings, e.g. Oscar.Orderings.ordering([x1, x2], matrix(ZZ, [1 2; 3 4]))
  • fix bug that causes tests to currently fail
  • add versions of leading_term, leading_coefficient, leading_monomial that take an ordering object
  • make strings in Singular.jl for orderings same as in Oscar, e.g. :negwdegrevlex instead of :negweightedrevlex

Caching of Groebner bases : TODO list

  • cache Groebner bases
  • Groebner basis type

Modules (Janko + student)

  • add singular_assure for modules
  • add std for modules

(*) We will use the TU Kaiserslautern Intake to register all participants when they arrive/depart, for contact tracing.

Noncommutative Groebner bases: TODO list

  • implement the computation of partial Groebner bases in an updatable way, i.e. if the Groebner basis has been computed up to degree 3 and you need it up to degree 4, the already known elements should be reused.
  • make the Groebner basis computation more efficient
  • implement ideals in free associative algebras
  • implement quotients of free associative algebras by ideals
  • can it be useful to make ideals updatable? i.e. given an ideal where I know part of the Groebner basis and I want to add a new relation to the ideal, can I save computation time by reusing the known Groebner basis?

Localizations and local rings: TODO list

All progress can be found in this branch.

  • Set up a general framework for localizations of (multivariate polynomial) rings;
  • Provide a concrete instance for localizations of polynomial rings at maximal ideals from geometric points, port the functionality from Raul's previous implementation;
  • Provide a concrete instance for localizations at prime ideals, implement the GRAAL algorithms for these.
  • Provide a concrete instance for localizations at powers of a specific element.
  • Implement all of the above for quotient rings/affine algebras.

Progress

  • Matthias has written some documentation on existing code and the implementations that we wish to have in the following branch of a fork of Oscar. This is also thought for documenting our discussions on the topic. Anne will contribute some more things on the implementation of various space germs.

  • Bill and Hans implemented module orderings at the Oscar level, see this pull request.

  • Dan and Julien implemented the Free Associative Algebra and basic arithmetic in Oscar and started documentation thereof.

  • Basic Groebner basis computation in Free Associative Algebras works via a simple Buchberger Algorithm

  • Matthias has sketched the beginning of a framework on localizations of (free polynomial) rings on multiplicatively closed sets in the file mpoly-localizations.jl. Probably, the previous implementations due to Raul can be ported to such a more general framework.

  • Anne has sketched the beginning of a framework for space germs, built on top of the localization at complements of maximal/prime ideals. For the first parts thereof, see Matthias branch.

Open questions that we need to discuss

  • Will there be a construction of fraction fields for rings without gcd? Dan says yes.
  • How do we wish to handle the caching of Groebner basis, in particular in local(ized) rings? Do we want to store any standard basis ever computed for a specific ordering ord in a dictionary with index ord?

How the groebner basis functionality should be designed

The general syntax should be: groebner_basis(I::MPolyIdeal, ord::AbsGenOrdering) -> GroebnerBasisObject where GroebnerBasisObject

  • stores the ordering
  • when printed, does this with the respective ordering.
  • provides an explicit list of polynomials with which one can perform reduction.

Reduction should happen internally, for instance in a function normal_form( f::MPolyElem, gb::GroebnerBasisObject) If the groebner basis was computed using Singular, then this would proceed as follows:

  • convert f to a Singular polynomial;
  • perform the reduction;
  • convert the result back to the Oscar side. If some other algorithm is used, it might not be necessary to have such conversions.

Any ideal I can then store Groebner bases that have been computed for different orderings. This should be done using a dictionary with the orderings as keys.

Remarks:

  • a polynomial itself does not have an ordering! Even though there might be a minimal performance improvement, this is not worth the work necessary for implementation.
  • the old version of groebner_basis(I::Ideal, ord::Symbol) will be preserved. To make it easier for the users.
Clone this wiki locally