PoslavskySV Rings Versions Save

This release addresses performance issues of multivariate GCD routines for huge polynomials:

• Implementation of sparse distributed <> sparse recursive conversions of underlying multivariate data structure for faster evaluation of multivariate polynomials with Horner scheme
• Several improvements in Zippel algorithm (both monic and LinZip)
• Better switches thresholds between dense and sparse problems

Other things:

• rings.repl can be now used to execute Rings scripts

Ideals in multivariate rings

This release introduces efficient methods for dealing with polynomial ideals, including Groebner bases computation and algebraic operations with ideals. The following new features are implemented:

• Improved Buchberger algorithm with Gebauer-Moller installation and different (sugar/non-sugar) selection strategies
• Implementation of Faugere's F4 algorithm with fast sparse linear algebra that employs special structures of F4 matrices
• Implementation of Hilbert series and Hilbert-driven methods including changing of order etc
• Modular algorithms for computing Groebner basis in Q[X]
• Sparse "lifting" algorithms for reconstruction of Groebner bases
• Implementation of Ideal class (union, intersection, quotient and other methods)

Modifications into other parts of the library

• Major refactoring of multivariate polynomials abstraction: make DegreeVector non abstract and introduce abstract class for monomials AMonomial
• Moved algebraic (module) operations with monomials from polynomial implementation to IMonomialAlgebra interface

Minor things

• Farey bounds for rational reconstruction & error tolerant methods for Farey reconstruction
• Several API enhancements for Ring interface
• Row-reduced forms in LinearSolver
• Important bug fixes in multivariate GCD

• Fast multivariate multiplication via Kronecker substitution #18
• Use EEZ-GCD for very dense GCD problems #19
• Bugfix in sparse Hensel lifting for fields of very small cardinality #21
• Diophantine solver for univariate polynomials (rings.poly.univar.DiophantineEquations)
• API enhancements #24:
  • FactorDecomposition made generic and moved to rings package
  • added gcd, extendedGCD, factor and factorSquareFree methods to Ring interface
  • rename PolynomialRing in Scala DSL to IPolynomialRing (make it consistent with Java API)
• minor enhancements and fixes

Changes:

• significantly improved multivariate factorization with the use of sparse Hensel lifting #13
• support for polynomial GCD and factorization in nested polynomial rings #12
• significantly improved multivariate GCD #9, #10
• improved univariate factorization in finite fields #8
• some minor enhancements and bugfixes

Changes:

• improved rings.repl script
• Homebrew formula: brew install PoslavskySV/rings/rings.repl

The first public release:

• All artifacts are pushed to Maven Cetral