diff options
Diffstat (limited to 'src/algebra/modmon.spad.pamphlet')
| -rw-r--r-- | src/algebra/modmon.spad.pamphlet | 224 |
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} |