\documentclass{article} \usepackage{open-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} <>= )abbrev domain MODMON ModMonic ++ Description: ++ This package \undocumented ModMonic(R,P): C == T where R: Ring P: UnivariatePolynomialCategory(R) C == Join(UnivariatePolynomialCategory(R),CoercibleFrom P) with --operations setPoly : P -> P ++ setPoly(x) \undocumented modulus : -> P ++ modulus() \undocumented reduce: P -> % ++ reduce(x) \undocumented lift: % -> P --reduce lift = identity ++ lift(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 R --assertions if R has Finite then Finite T == add Rep := P --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: % d,n: Integer e,k1,k2: NonNegativeInteger c: R --vect: Vector(R) power: PrimitiveArray(%) := new(0,0) frobeniusPower: PrimitiveArray(%) := new(0,0) computeFrobeniusPowers : () -> PrimitiveArray(%) --representations --mutable m --take this out?? --define setPoly (mon : P) == mon =$Rep m => mon oldm := m not one? leadingCoefficient mon => 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: 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]@%::Rep) 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 not zero? a repeat aq:= aq + leadingCoefficient(a)*frobeniusPower(degree a) a := reductum a aq pow == power monomial(c,e)== if e "failed" return reduce(uv.coef1::Rep) 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(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} <>= --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. @ <<*>>= <> <> @ \eject \begin{thebibliography}{99} \bibitem{1} nothing \end{thebibliography} \end{document}