Safe Haskell	None
Language	Haskell2010

Algebra.Algorithms.ZeroDim

Contents

Root finding for zero-dimensional ideal
Radical computation
Converting monomial ordering to Lex using FGLM algorithm
- Internal helper function

Description

Algorithms for zero-dimensional ideals.

Since 0.4.0.0

Synopsis

solveM :: forall m r ord n. (Normed r, Ord r, MonadRandom m, Field r, CoeffRing r, KnownNat n, IsMonomialOrder n ord, Convertible r Double, 0 < n) => Ideal (OrderedPolynomial r ord n) -> m [Sized n (Complex Double)]
solve' :: forall r n ord. (Field r, CoeffRing r, KnownNat n, 0 < n, IsMonomialOrder n ord, Convertible r Double) => Double -> Ideal (OrderedPolynomial r ord n) -> [Sized n (Complex Double)]
solveViaCompanion :: forall r ord n. (Show r, Ord r, Field r, CoeffRing r, KnownNat n, IsMonomialOrder n ord, Convertible r Double) => Double -> Ideal (OrderedPolynomial r ord n) -> [Sized n (Complex Double)]
solveLinear :: (Ord r, Fractional r) => Matrix r -> Vector r -> Maybe (Vector r)
radical :: forall r ord n. (Ord r, CoeffRing r, KnownNat n, Field r, IsMonomialOrder n ord) => Ideal (OrderedPolynomial r ord n) -> Ideal (OrderedPolynomial r ord n)
isRadical :: forall r ord n. (Ord r, CoeffRing r, KnownNat n, 0 < n, Field r, IsMonomialOrder n ord) => Ideal (OrderedPolynomial r ord n) -> Bool
fglm :: (Ord r, KnownNat n, Field r, IsMonomialOrder n ord, 0 < n) => Ideal (OrderedPolynomial r ord n) -> ([OrderedPolynomial r Lex n], [OrderedPolynomial r Lex n])
fglmMap :: forall k ord n. (Ord k, Field k, 0 < n, IsMonomialOrder n ord, CoeffRing k, KnownNat n) => (OrderedPolynomial k ord n -> Vector k) -> ([OrderedPolynomial k Lex n], [OrderedPolynomial k Lex n])
solveWith :: forall r n ord. (DecidableZero r, Normed r, Ord r, Field r, CoeffRing r, 0 < n, IsMonomialOrder n ord, KnownNat n, Convertible r Double) => OrderedPolynomial r ord n -> Ideal (OrderedPolynomial r ord n) -> Maybe [Sized n (Complex Double)]
univPoly :: forall r ord n. (Ord r, Field r, CoeffRing r, KnownNat n, IsMonomialOrder n ord) => Ordinal n -> Ideal (OrderedPolynomial r ord n) -> OrderedPolynomial r ord n
reduction :: (CoeffRing r, KnownNat n, IsMonomialOrder n ord, Field r) => Ordinal n -> OrderedPolynomial r ord n -> OrderedPolynomial r ord n
matrixRep :: (DecidableZero t, Eq t, Field t, KnownNat n, IsMonomialOrder n order, Reifies ideal (QIdeal (OrderedPolynomial t order n))) => Quotient (OrderedPolynomial t order n) ideal -> [[t]]
subspMatrix :: forall r n ord. (Show r, Ord r, Field r, CoeffRing r, KnownNat n, IsMonomialOrder n ord) => Ordinal n -> Ideal (OrderedPolynomial r ord n) -> Matrix r
vectorRep :: forall k poly (ideal :: k). (IsOrderedPolynomial poly, Reifies ideal (QIdeal poly)) => Quotient poly ideal -> Vector (Coefficient poly)

Root finding for zero-dimensional ideal

solveM :: forall m r ord n. (Normed r, Ord r, MonadRandom m, Field r, CoeffRing r, KnownNat n, IsMonomialOrder n ord, Convertible r Double, 0 < n) => Ideal (OrderedPolynomial r ord n) -> m [Sized n (Complex Double)] Source #

Finds complex approximate roots of given zero-dimensional ideal, using randomized altorithm.

See also solve' and solveViaCompanion.

solve' :: forall r n ord. (Field r, CoeffRing r, KnownNat n, 0 < n, IsMonomialOrder n ord, Convertible r Double) => Double -> Ideal (OrderedPolynomial r ord n) -> [Sized n (Complex Double)] Source #

solve' err is finds numeric approximate root of the given zero-dimensional polynomial system is, with error <err.

See also solveViaCompanion and solveM.

solveViaCompanion :: forall r ord n. (Show r, Ord r, Field r, CoeffRing r, KnownNat n, IsMonomialOrder n ord, Convertible r Double) => Double -> Ideal (OrderedPolynomial r ord n) -> [Sized n (Complex Double)] Source #

solveViaCompanion err is finds numeric approximate root of the given zero-dimensional polynomial system is, with error <err.

Radical computation

radical :: forall r ord n. (Ord r, CoeffRing r, KnownNat n, Field r, IsMonomialOrder n ord) => Ideal (OrderedPolynomial r ord n) -> Ideal (OrderedPolynomial r ord n) Source #

Calculate the radical of the given zero-dimensional ideal.

isRadical :: forall r ord n. (Ord r, CoeffRing r, KnownNat n, 0 < n, Field r, IsMonomialOrder n ord) => Ideal (OrderedPolynomial r ord n) -> Bool Source #

Test if the given zero-dimensional ideal is radical or not.

Converting monomial ordering to Lex using FGLM algorithm

fglm :: (Ord r, KnownNat n, Field r, IsMonomialOrder n ord, 0 < n) => Ideal (OrderedPolynomial r ord n) -> ([OrderedPolynomial r Lex n], [OrderedPolynomial r Lex n]) Source #

Calculate the Groebner basis w.r.t. lex ordering of the zero-dimensional ideal using FGLM algorithm. If the given ideal is not zero-dimensional this function may diverge.

fglmMap Source #

Arguments

:: forall k ord n. (Ord k, Field k, 0 < n, IsMonomialOrder n ord, CoeffRing k, KnownNat n)

=> (OrderedPolynomial k ord n -> Vector k)

Linear map from polynomial ring.

-> ([OrderedPolynomial k Lex n], [OrderedPolynomial k Lex n])

The tuple of:

lex-Groebner basis of the kernel of the given linear map.
The vector basis of the image of the linear map.

Compute the kernel and image of the given linear map using generalized FGLM algorithm.

Internal helper function

solveWith :: forall r n ord. (DecidableZero r, Normed r, Ord r, Field r, CoeffRing r, 0 < n, IsMonomialOrder n ord, KnownNat n, Convertible r Double) => OrderedPolynomial r ord n -> Ideal (OrderedPolynomial r ord n) -> Maybe [Sized n (Complex Double)] Source #

solveWith f is finds complex approximate roots of the given zero-dimensional n-variate polynomial system is, using the given relatively prime polynomial f.

univPoly :: forall r ord n. (Ord r, Field r, CoeffRing r, KnownNat n, IsMonomialOrder n ord) => Ordinal n -> Ideal (OrderedPolynomial r ord n) -> OrderedPolynomial r ord n Source #

Calculate the monic generator of \( k[X_0, ..., X_n] \cap k[X_i]\).

reduction :: (CoeffRing r, KnownNat n, IsMonomialOrder n ord, Field r) => Ordinal n -> OrderedPolynomial r ord n -> OrderedPolynomial r ord n Source #

Calculates n-th reduction of f: f div ∂_{x_n} f.

matrixRep :: (DecidableZero t, Eq t, Field t, KnownNat n, IsMonomialOrder n order, Reifies ideal (QIdeal (OrderedPolynomial t order n))) => Quotient (OrderedPolynomial t order n) ideal -> [[t]] Source #

subspMatrix :: forall r n ord. (Show r, Ord r, Field r, CoeffRing r, KnownNat n, IsMonomialOrder n ord) => Ordinal n -> Ideal (OrderedPolynomial r ord n) -> Matrix r Source #

Given a zero-dimensional ideal \(I\), \('subspMatrix' i I\) computes a multiplication matrix \(m_{x_i} \mathbin{\upharpoonright} V_i \) by \(x_i\) restricted to the subspace \(V_i = \mathop{\mathrm{span}}(\left\{\ x_i^n \ \middle|\ 1 \leq n \right\})\) of \(k[\mathbf{X}]\).

vectorRep :: forall k poly (ideal :: k). (IsOrderedPolynomial poly, Reifies ideal (QIdeal poly)) => Quotient poly ideal -> Vector (Coefficient poly) #