Safe Haskell	None
Language	Haskell2010

Algebra.Algorithms.Groebner.Signature

Contents

Algorithms
Classes
References

Description

Signature-based Groebner basis algorithms, such as Faugère's \(F_5\).

You can import Algebra.Algorithms.Groebner.Signature.Rules to replace every occurence of calcGroebnerBasis with f5; but its effect is pervasive, you should not import in the library-site.

Synopsis

f5 :: (IsOrderedPolynomial a, Field (Coefficient a), Foldable t) => t a -> [a]
f5With :: forall ord a pxy t. (IsOrderedPolynomial a, Field (Coefficient a), ModuleOrdering a ord, Foldable t) => pxy ord -> t a -> [a]
calcSignatureGB :: forall poly. (Field (Coefficient poly), IsOrderedPolynomial poly) => Vector poly -> Vector (Signature poly, poly)
calcSignatureGBWith :: forall pxy ord poly. (Field (Coefficient poly), ModuleOrdering poly ord, IsOrderedPolynomial poly) => pxy ord -> Vector poly -> Vector (Signature poly, poly)
withDegreeWeights :: forall ord poly proxy a t. (IsOrderedPolynomial poly, ModuleOrdering poly ord, Foldable t) => proxy ord -> (forall k (gs :: k). Reifies gs (Vector Int) => Proxy (DegreeWeighted gs ord) -> t poly -> a) -> t poly -> a
withTermWeights :: forall ord poly proxy a t. (IsOrderedPolynomial poly, ModuleOrdering poly ord, Foldable t) => proxy ord -> (forall k (gs :: k). Reifies gs (Vector (OrderedMonomial (MOrder poly) (Arity poly))) => Proxy (TermWeighted gs ord) -> t poly -> a) -> t poly -> a
reifyDegreeWeights :: forall ord poly proxy a t. (IsOrderedPolynomial poly, ModuleOrdering poly ord, Foldable t) => proxy ord -> t poly -> (forall k (gs :: k). Reifies gs (Vector Int) => Proxy (DegreeWeighted gs ord) -> t poly -> a) -> a
reifyTermWeights :: forall ord poly proxy a t. (IsOrderedPolynomial poly, ModuleOrdering poly ord, Foldable t) => proxy ord -> t poly -> (forall k (gs :: k). Reifies gs (Vector (OMonom poly)) => Proxy (TermWeighted gs ord) -> t poly -> a) -> a
class IsOrderedPolynomial poly => ModuleOrdering poly ord where
- cmpModule :: proxy ord -> Signature poly -> Signature poly -> Ordering
- syzygyBase :: Field (Coefficient poly) => (Int, poly) -> (Int, poly) -> OrdSig ord poly
data POT = POT
data TOP = TOP
data Signature poly = Signature {
- _sigPos :: !Int
- sigMonom :: !(OrderedMonomial (MOrder poly) (Arity poly))
}
newtype OrdSig ord poly where
- OrdSig (Signature poly)
- pattern MkOrdSig :: Int -> OMonom poly -> OrdSig ord poly
newtype DegreeWeighted (gs :: k) ord = DegreeWeighted ord
newtype TermWeighted (gs :: k) ord = TermWeighted ord
type DegreeWeightedPOT gs = DegreeWeighted gs POT
type DegreeWeightedTOP gs = DegreeWeighted gs TOP
type TermWeightedPOT gs = TermWeighted gs POT
type TermWeightedTOP gs = TermWeighted gs TOP

Algorithms

f5 :: (IsOrderedPolynomial a, Field (Coefficient a), Foldable t) => t a -> [a] Source #

Calculates a Gröbner basis of a given ideal using the signature-based algorithm as described in Gao-Iv-Wang.

This is the fastest implementation in this library so far.

f5With :: forall ord a pxy t. (IsOrderedPolynomial a, Field (Coefficient a), ModuleOrdering a ord, Foldable t) => pxy ord -> t a -> [a] Source #

calcSignatureGB :: forall poly. (Field (Coefficient poly), IsOrderedPolynomial poly) => Vector poly -> Vector (Signature poly, poly) Source #

calcSignatureGBWith :: forall pxy ord poly. (Field (Coefficient poly), ModuleOrdering poly ord, IsOrderedPolynomial poly) => pxy ord -> Vector poly -> Vector (Signature poly, poly) Source #

Calculates a Groebner basis for a given ideal, and a set of leading monomials of Groebner basis of the associated syzygy module, as described in Gao-Iv-Wang.

withDegreeWeights :: forall ord poly proxy a t. (IsOrderedPolynomial poly, ModuleOrdering poly ord, Foldable t) => proxy ord -> (forall k (gs :: k). Reifies gs (Vector Int) => Proxy (DegreeWeighted gs ord) -> t poly -> a) -> t poly -> a Source #

withTermWeights :: forall ord poly proxy a t. (IsOrderedPolynomial poly, ModuleOrdering poly ord, Foldable t) => proxy ord -> (forall k (gs :: k). Reifies gs (Vector (OrderedMonomial (MOrder poly) (Arity poly))) => Proxy (TermWeighted gs ord) -> t poly -> a) -> t poly -> a Source #

reifyDegreeWeights :: forall ord poly proxy a t. (IsOrderedPolynomial poly, ModuleOrdering poly ord, Foldable t) => proxy ord -> t poly -> (forall k (gs :: k). Reifies gs (Vector Int) => Proxy (DegreeWeighted gs ord) -> t poly -> a) -> a Source #

reifyTermWeights :: forall ord poly proxy a t. (IsOrderedPolynomial poly, ModuleOrdering poly ord, Foldable t) => proxy ord -> t poly -> (forall k (gs :: k). Reifies gs (Vector (OMonom poly)) => Proxy (TermWeighted gs ord) -> t poly -> a) -> a Source #

Classes

class IsOrderedPolynomial poly => ModuleOrdering poly ord where Source #

Minimal complete definition

cmpModule

Methods

cmpModule :: proxy ord -> Signature poly -> Signature poly -> Ordering Source #

syzygyBase :: Field (Coefficient poly) => (Int, poly) -> (Int, poly) -> OrdSig ord poly Source #

Instances

Instances details

IsOrderedPolynomial poly => ModuleOrdering poly TOP Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods cmpModule :: proxy TOP -> Signature poly -> Signature poly -> Ordering Source # syzygyBase :: (Int, poly) -> (Int, poly) -> OrdSig TOP poly Source #
IsOrderedPolynomial poly => ModuleOrdering poly POT Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods cmpModule :: proxy POT -> Signature poly -> Signature poly -> Ordering Source # syzygyBase :: (Int, poly) -> (Int, poly) -> OrdSig POT poly Source #
(ModuleOrdering poly ord, IsOrderedPolynomial poly, Reifies gs (Vector (OrderedMonomial (MOrder poly) (Arity poly)))) => ModuleOrdering poly (TermWeighted gs ord :: Type) Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods cmpModule :: proxy (TermWeighted gs ord) -> Signature poly -> Signature poly -> Ordering Source # syzygyBase :: (Int, poly) -> (Int, poly) -> OrdSig (TermWeighted gs ord) poly Source #
(ModuleOrdering poly ord, IsOrderedPolynomial poly, Reifies gs (Vector Int)) => ModuleOrdering poly (DegreeWeighted gs ord :: Type) Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods cmpModule :: proxy (DegreeWeighted gs ord) -> Signature poly -> Signature poly -> Ordering Source # syzygyBase :: (Int, poly) -> (Int, poly) -> OrdSig (DegreeWeighted gs ord) poly Source #

data POT Source #

Constructors

POT

Instances

Instances details

Eq POT Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods (==) :: POT -> POT -> Bool # (/=) :: POT -> POT -> Bool #
Ord POT Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods compare :: POT -> POT -> Ordering # (<) :: POT -> POT -> Bool # (<=) :: POT -> POT -> Bool # (>) :: POT -> POT -> Bool # (>=) :: POT -> POT -> Bool # max :: POT -> POT -> POT # min :: POT -> POT -> POT #
Read POT Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods readsPrec :: Int -> ReadS POT # readList :: ReadS [POT] # readPrec :: ReadPrec POT # readListPrec :: ReadPrec [POT] #
Show POT Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods showsPrec :: Int -> POT -> ShowS # show :: POT -> String # showList :: [POT] -> ShowS #
IsOrderedPolynomial poly => ModuleOrdering poly POT Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods cmpModule :: proxy POT -> Signature poly -> Signature poly -> Ordering Source # syzygyBase :: (Int, poly) -> (Int, poly) -> OrdSig POT poly Source #

data TOP Source #

Constructors

TOP

Instances

Instances details

Eq TOP Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods (==) :: TOP -> TOP -> Bool # (/=) :: TOP -> TOP -> Bool #
Ord TOP Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods compare :: TOP -> TOP -> Ordering # (<) :: TOP -> TOP -> Bool # (<=) :: TOP -> TOP -> Bool # (>) :: TOP -> TOP -> Bool # (>=) :: TOP -> TOP -> Bool # max :: TOP -> TOP -> TOP # min :: TOP -> TOP -> TOP #
Read TOP Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods readsPrec :: Int -> ReadS TOP # readList :: ReadS [TOP] # readPrec :: ReadPrec TOP # readListPrec :: ReadPrec [TOP] #
Show TOP Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods showsPrec :: Int -> TOP -> ShowS # show :: TOP -> String # showList :: [TOP] -> ShowS #
IsOrderedPolynomial poly => ModuleOrdering poly TOP Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods cmpModule :: proxy TOP -> Signature poly -> Signature poly -> Ordering Source # syzygyBase :: (Int, poly) -> (Int, poly) -> OrdSig TOP poly Source #

data Signature poly Source #

Constructors

Signature
Fields _sigPos :: !Int sigMonom :: !(OrderedMonomial (MOrder poly) (Arity poly))

Instances

Instances details

Eq (Signature poly) Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods (==) :: Signature poly -> Signature poly -> Bool # (/=) :: Signature poly -> Signature poly -> Bool #
(Show (Coefficient poly), KnownNat (Arity poly)) => Show (Signature poly) Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods showsPrec :: Int -> Signature poly -> ShowS # show :: Signature poly -> String # showList :: [Signature poly] -> ShowS #

newtype OrdSig ord poly Source #

Constructors

OrdSig (Signature poly)

Bundled Patterns

pattern MkOrdSig :: Int -> OMonom poly -> OrdSig ord poly

Instances

Instances details

Eq (OrdSig ord poly) Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods (==) :: OrdSig ord poly -> OrdSig ord poly -> Bool # (/=) :: OrdSig ord poly -> OrdSig ord poly -> Bool #
ModuleOrdering poly ord => Ord (OrdSig ord poly) Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods compare :: OrdSig ord poly -> OrdSig ord poly -> Ordering # (<) :: OrdSig ord poly -> OrdSig ord poly -> Bool # (<=) :: OrdSig ord poly -> OrdSig ord poly -> Bool # (>) :: OrdSig ord poly -> OrdSig ord poly -> Bool # (>=) :: OrdSig ord poly -> OrdSig ord poly -> Bool # max :: OrdSig ord poly -> OrdSig ord poly -> OrdSig ord poly # min :: OrdSig ord poly -> OrdSig ord poly -> OrdSig ord poly #

newtype DegreeWeighted (gs :: k) ord Source #

Constructors

DegreeWeighted ord

Instances

Instances details

(ModuleOrdering poly ord, IsOrderedPolynomial poly, Reifies gs (Vector Int)) => ModuleOrdering poly (DegreeWeighted gs ord :: Type) Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods cmpModule :: proxy (DegreeWeighted gs ord) -> Signature poly -> Signature poly -> Ordering Source # syzygyBase :: (Int, poly) -> (Int, poly) -> OrdSig (DegreeWeighted gs ord) poly Source #

newtype TermWeighted (gs :: k) ord Source #

Constructors

TermWeighted ord

Instances

Instances details

(ModuleOrdering poly ord, IsOrderedPolynomial poly, Reifies gs (Vector (OrderedMonomial (MOrder poly) (Arity poly)))) => ModuleOrdering poly (TermWeighted gs ord :: Type) Source #
Instance details Defined in Algebra.Algorithms.Groebner.Signature Methods cmpModule :: proxy (TermWeighted gs ord) -> Signature poly -> Signature poly -> Ordering Source # syzygyBase :: (Int, poly) -> (Int, poly) -> OrdSig (TermWeighted gs ord) poly Source #

type DegreeWeightedPOT gs = DegreeWeighted gs POT Source #

type DegreeWeightedTOP gs = DegreeWeighted gs TOP Source #

type TermWeightedPOT gs = TermWeighted gs POT Source #

type TermWeightedTOP gs = TermWeighted gs TOP Source #

References

J.-C. Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero ( \(F_5\) ), 2014. DOI: 10.1145/780506.780516.
C. Eder and J.-C. Faugère, A survey on signature-based Gröbner basis computations, 2015. arXiv: https://arxiv.org/abs/1404.1774.
D. Cox, J. Little, and D. O'Shea, Additional Gröbner Basis Algorithms, Chapter 10 in Ideals, Variaeties and Algorithms, 4th ed, Springer, 2015.
S. Gao, F. V. Iv, and M. Wang, A new framework for computing Gröbner bases, 2016. DOI: 10.1090mcom2969.