computational-algebra 0.1.3.5 → 0.1.3.6

raw patch · 3 files changed

+40/−9 lines, 3 files

Files

• Algebra/Algorithms/Groebner.hs +27/−8
• computational-algebra.cabal +1/−1
• examples/poly-02.hs +12/−0

@@ -33,6 +33,7 @@ import           Data.Function import qualified Data.Heap               as H import           Data.List+import           Data.Maybe import           Data.Proxy import           Data.STRef import           Numeric.Algebra@@ -80,7 +81,7 @@   in fst $ until (null . snd) (\(ggs, acc) -> let cur = nub $ ggs ++ acc in                                               (cur, calc cur)) (gs, calc gs)   where-    calc acc = [ q | f <- acc, g <- acc, f /= g+    calc acc = [ q | f <- acc, g <- acc                , let q = sPolynomial f g `modPolynomial` acc, q /= zero                ] @@ -228,19 +229,37 @@       tsgr h = deg' h - totalDegree (leadingMonomial h)       sugar = max (tsgr f) (tsgr g) + totalDegree (lcmMonomial (leadingMonomial f) (leadingMonomial g)) --- | Minimize the given groebner basis. minimizeGroebnerBasis :: (Field k, IsPolynomial k n, IsMonomialOrder order)                       => [OrderedPolynomial k order n] -> [OrderedPolynomial k order n]-minimizeGroebnerBasis = foldr step []-  where-    step x xs = monoize x : filter (not . (leadingMonomial x `divs`) . leadingMonomial) xs+minimizeGroebnerBasis bs = runST $ do+  left  <- newSTRef bs+  right <- newSTRef []+  whileM_ (not . null <$> readSTRef left) $ do+    f : xs <- readSTRef left+    writeSTRef left xs+    ys     <- readSTRef right+    if any (\g -> leadingMonomial g `divs` leadingMonomial f) xs ||+       any (\g -> leadingMonomial g `divs` leadingMonomial f) ys+      then writeSTRef right ys+      else writeSTRef right (monoize f : ys)+  readSTRef right  -- | Reduce minimum Groebner basis into reduced Groebner basis. reduceMinimalGroebnerBasis :: (Field k, IsPolynomial k n, IsMonomialOrder order)                            => [OrderedPolynomial k order n] -> [OrderedPolynomial k order n]-reduceMinimalGroebnerBasis bs = filter (/= zero) $ map (monoize . red) bs-  where-    red x = x `modPolynomial` delete x bs+reduceMinimalGroebnerBasis bs = runST $ do+  left  <- newSTRef bs+  right <- newSTRef []+  whileM_ (not . null <$> readSTRef left) $ do+    f : xs <- readSTRef left+    writeSTRef left xs+    ys     <- readSTRef right+    let q = f `modPolynomial` (xs ++ ys)+    if q == zero then writeSTRef right ys else writeSTRef right (q : ys)+  readSTRef right++-- foldr step [] [f, g, h]+--  f `step` (g `step` (h `step` []))  monoize :: (Field k, IsPolynomial k n, IsMonomialOrder order)            => OrderedPolynomial k order n -> OrderedPolynomial k order n

@@ -2,7 +2,7 @@ -- further documentation, see http://haskell.org/cabal/users-guide/  name:                computational-algebra-version:             0.1.3.5+version:             0.1.3.6 synopsis:            Well-kinded computational algebra library, currently supporting Groebner basis. description:         Dependently-typed computational algebra libray for Groebner basis. homepage:            https://github.com/konn/computational-algebra

@@ -0,0 +1,12 @@+{-# LANGUAGE DataKinds, OverloadedStrings, PolyKinds #-}+module Main where+import Algebra.Algorithms.Groebner+import Algebra.Internal+import Algebra.Ring.Noetherian+import Algebra.Ring.Polynomial++x, y :: OrderedPolynomial Rational Lex Two+[x, y] = genVars sTwo++main :: IO ()+main = print $ reduceMinimalGroebnerBasis $ minimizeGroebnerBasis $ simpleBuchberger $ toIdeal [x^2*y-1,x^3-y^2-x]