aboutsummaryrefslogtreecommitdiff
path: root/src/algebra/modmon.spad.pamphlet
diff options
context:
space:
mode:
authordos-reis <gdr@axiomatics.org>2007-08-14 05:14:52 +0000
committerdos-reis <gdr@axiomatics.org>2007-08-14 05:14:52 +0000
commitab8cc85adde879fb963c94d15675783f2cf4b183 (patch)
treec202482327f474583b750b2c45dedfc4e4312b1d /src/algebra/modmon.spad.pamphlet
downloadopen-axiom-ab8cc85adde879fb963c94d15675783f2cf4b183.tar.gz
Initial population.
Diffstat (limited to 'src/algebra/modmon.spad.pamphlet')
-rw-r--r--src/algebra/modmon.spad.pamphlet224
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}