Initial population.

1 files changed, 224 insertions, 0 deletions

diff --git a/src/algebra/modmon.spad.pamphlet b/src/algebra/modmon.spad.pamphlet
new file mode 100644
index 00000000..cc8bebec
--- /dev/null
+++ b/src/algebra/modmon.spad.pamphlet
@@ -0,0 +1,224 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra modmon.spad}
+\author{The Axiom Team}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{domain MODMON ModMonic}
+<<domain MODMON ModMonic>>=
+)abbrev domain MODMON ModMonic
+++ Description:
+++ This package \undocumented
+-- following line prevents caching ModMonic
+)bo PUSH('ModMonic, $mutableDomains)
+ 
+ModMonic(R,Rep): C == T
+ where
+  R: Ring
+  Rep: UnivariatePolynomialCategory(R)
+  C == UnivariatePolynomialCategory(R) with
+  --operations
+    setPoly : Rep -> Rep
+	++ setPoly(x) \undocumented
+    modulus : -> Rep
+	++ modulus() \undocumented
+    reduce: Rep -> %
+	++ reduce(x) \undocumented
+    lift: % -> Rep --reduce lift = identity
+	++ lift(x) \undocumented
+    coerce: Rep -> %
+	++ coerce(x) \undocumented
+    Vectorise: % -> Vector(R)
+	++ Vectorise(x) \undocumented
+    UnVectorise: Vector(R) -> %
+	++ UnVectorise(v) \undocumented
+    An: % -> Vector(R)
+	++ An(x) \undocumented
+    pow : -> PrimitiveArray(%)
+	++ pow() \undocumented
+    computePowers : -> PrimitiveArray(%)
+	++ computePowers() \undocumented
+    if R has FiniteFieldCategory then
+       frobenius: % -> %
+	++ frobenius(x) \undocumented
+    --LinearTransf: (%,Vector(R)) -> SquareMatrix<deg> R
+  --assertions
+    if R has Finite then Finite
+  T == add
+    --constants
+      m:Rep := monomial(1,1)$Rep --| degree(m) > 0 and LeadingCoef(m) = R$1
+      d := degree(m)$Rep
+      d1 := (d-1):NonNegativeInteger
+      twod := 2*d1+1
+      frobenius?:Boolean := R has FiniteFieldCategory
+      --VectorRep:= DirectProduct(d:NonNegativeInteger,R)
+    --declarations
+      x,y: %
+      p: Rep
+      d,n: Integer
+      e,k1,k2: NonNegativeInteger
+      c: R
+      --vect: Vector(R)
+      power:PrimitiveArray(%)
+      frobeniusPower:PrimitiveArray(%)
+      computeFrobeniusPowers : () -> PrimitiveArray(%)
+    --representations
+    --mutable m    --take this out??
+    --define
+      power := new(0,0)
+      frobeniusPower := new(0,0)
+      setPoly (mon : Rep) ==
+        mon =$Rep m => mon
+        oldm := m
+        leadingCoefficient mon ^= 1 => error "polynomial must be monic"
+        -- following copy code needed since FFPOLY can modify mon
+        copymon:Rep:= 0
+        while not zero? mon repeat
+           copymon := monomial(leadingCoefficient mon, degree mon)$Rep + copymon
+           mon := reductum mon
+        m := copymon
+        d := degree(m)$Rep
+        d1 := (d-1)::NonNegativeInteger
+        twod := 2*d1+1
+        power := computePowers()
+        if frobenius? then
+          degree(oldm)>1 and not((oldm exquo$Rep m) case "failed") =>
+              for i in 1..d1 repeat
+                frobeniusPower(i) := reduce lift frobeniusPower(i)
+          frobeniusPower := computeFrobeniusPowers()
+        m
+      modulus == m
+      if R has Finite then
+         size == d * size$R
+         random == UnVectorise([random()$R for i in 0..d1])
+      0 == 0$Rep
+      1 == 1$Rep
+      c * x == c *$Rep x
+      n * x == (n::R) *$Rep x
+      coerce(c:R):% == monomial(c,0)$Rep
+      coerce(x:%):OutputForm == coerce(x)$Rep
+      coefficient(x,e):R == coefficient(x,e)$Rep
+      reductum(x) == reductum(x)$Rep
+      leadingCoefficient x == (leadingCoefficient x)$Rep
+      degree x == (degree x)$Rep
+      lift(x) == x pretend Rep
+      reduce(p) == (monicDivide(p,m)$Rep).remainder
+      coerce(p) == reduce(p)
+      x = y == x =$Rep y
+      x + y == x +$Rep y
+      - x == -$Rep x
+      x * y ==
+        p := x *$Rep y
+        ans:=0$Rep
+        while (n:=degree p)>d1 repeat
+           ans:=ans + leadingCoefficient(p)*power.(n-d)
+           p := reductum p
+        ans+p
+      Vectorise(x) == [coefficient(lift(x),i) for i in 0..d1]
+      UnVectorise(vect) ==
+        reduce(+/[monomial(vect.(i+1),i) for i in 0..d1])
+      computePowers ==
+           mat : PrimitiveArray(%):= new(d,0)
+           mat.0:= reductum(-m)$Rep
+           w: % := monomial$Rep (1,1)
+           for i in 1..d1 repeat
+              mat.i := w *$Rep mat.(i-1)
+              if degree mat.i=d then
+                mat.i:= reductum mat.i + leadingCoefficient mat.i * mat.0
+           mat
+      if frobenius? then
+          computeFrobeniusPowers() ==
+            mat : PrimitiveArray(%):= new(d,1)
+            mat.1:= mult := monomial(1, size$R)$%
+            for i in 2..d1 repeat
+               mat.i := mult * mat.(i-1)
+            mat
+
+          frobenius(a:%):% ==
+            aq:% := 0
+            while a^=0 repeat
+              aq:= aq + leadingCoefficient(a)*frobeniusPower(degree a)
+              a := reductum a
+            aq
+         
+      pow == power
+      monomial(c,e)==
+         if e<d then monomial(c,e)$Rep
+         else
+            if e<=twod then
+               c * power.(e-d)
+            else
+               k1:=e quo twod
+               k2 := (e-k1*twod)::NonNegativeInteger
+               reduce((power.d1 **k1)*monomial(c,k2))
+      if R has Field then
+
+         (x:% exquo y:%):Union(%, "failed") ==
+            uv := extendedEuclidean(y, modulus(), x)$Rep
+            uv case "failed" => "failed"
+            return reduce(uv.coef1)
+
+         recip(y:%):Union(%, "failed") ==  1 exquo y
+         divide(x:%, y:%) ==
+            (q := (x exquo y)) case "failed" => error "not divisible"
+            [q, 0]
+
+--     An(MM) == Vectorise(-(reduce(reductum(m))::MM))
+--     LinearTransf(vect,MM) ==
+--       ans:= 0::SquareMatrix<d>(R)
+--       for i in 1..d do setelt(ans,i,1,vect.i)
+--       for j in 2..d do
+--          setelt(ans,1,j, elt(ans,d,j-1) * An(MM).1)
+--          for i in 2..d do
+--            setelt(ans,i,j, elt(ans,i-1,j-1) + elt(ans,d,j-1) * An(MM).i)
+--       ans
+
+@
+\section{License}
+<<license>>=
+--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
+--All rights reserved.
+--
+--Redistribution and use in source and binary forms, with or without
+--modification, are permitted provided that the following conditions are
+--met:
+--
+--    - Redistributions of source code must retain the above copyright
+--      notice, this list of conditions and the following disclaimer.
+--
+--    - Redistributions in binary form must reproduce the above copyright
+--      notice, this list of conditions and the following disclaimer in
+--      the documentation and/or other materials provided with the
+--      distribution.
+--
+--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
+--      names of its contributors may be used to endorse or promote products
+--      derived from this software without specific prior written permission.
+--
+--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+@
+<<*>>=
+<<license>>
+
+<<domain MODMON ModMonic>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}