diff options
| author | dos-reis <gdr@axiomatics.org> | 2007-08-14 05:14:52 +0000 |
|---|---|---|
| committer | dos-reis <gdr@axiomatics.org> | 2007-08-14 05:14:52 +0000 |
| commit | ab8cc85adde879fb963c94d15675783f2cf4b183 (patch) | |
| tree | c202482327f474583b750b2c45dedfc4e4312b1d /src/algebra/mring.spad.pamphlet | |
| download | open-axiom-ab8cc85adde879fb963c94d15675783f2cf4b183.tar.gz | |
Initial population.
Diffstat (limited to 'src/algebra/mring.spad.pamphlet')
| -rw-r--r-- | src/algebra/mring.spad.pamphlet | 405 |
1 files changed, 405 insertions, 0 deletions
diff --git a/src/algebra/mring.spad.pamphlet b/src/algebra/mring.spad.pamphlet new file mode 100644 index 00000000..04c50f32 --- /dev/null +++ b/src/algebra/mring.spad.pamphlet @@ -0,0 +1,405 @@ +\documentclass{article} +\usepackage{axiom} +\begin{document} +\title{\$SPAD/src/algebra mring.spad} +\author{Stephen M. Watt, Johannes Grabmeier, Mike Dewar} +\maketitle +\begin{abstract} +\end{abstract} +\eject +\tableofcontents +\eject +\section{domain MRING MonoidRing} +<<domain MRING MonoidRing>>= +)abbrev domain MRING MonoidRing +++ Authors: Stephan M. Watt; revised by Johannes Grabmeier +++ Date Created: January 1986 +++ Date Last Updated: 14 December 1995, Mike Dewar +++ Basic Operations: *, +, monomials, coefficients +++ Related Constructors: Polynomial +++ Also See: +++ AMS Classifications: +++ Keywords: monoid ring, group ring, polynomials in non-commuting +++ indeterminates +++ References: +++ Description: +++ \spadtype{MonoidRing}(R,M), implements the algebra +++ of all maps from the monoid M to the commutative ring R with +++ finite support. +++ Multiplication of two maps f and g is defined +++ to map an element c of M to the (convolution) sum over {\em f(a)g(b)} +++ such that {\em ab = c}. Thus M can be identified with a canonical +++ basis and the maps can also be considered as formal linear combinations +++ of the elements in M. Scalar multiples of a basis element are called +++ monomials. A prominent example is the class of polynomials +++ where the monoid is a direct product of the natural numbers +++ with pointwise addition. When M is +++ \spadtype{FreeMonoid Symbol}, one gets polynomials +++ in infinitely many non-commuting variables. Another application +++ area is representation theory of finite groups G, where modules +++ over \spadtype{MonoidRing}(R,G) are studied. + +MonoidRing(R: Ring, M: Monoid): MRcategory == MRdefinition where + Term ==> Record(coef: R, monom: M) + + MRcategory ==> Join(Ring, RetractableTo M, RetractableTo R) with + monomial : (R, M) -> % + ++ monomial(r,m) creates a scalar multiple of the basis element m. + coefficient : (%, M) -> R + ++ coefficient(f,m) extracts the coefficient of m in f with respect + ++ to the canonical basis M. + coerce: List Term -> % + ++ coerce(lt) converts a list of terms and coefficients to a member of the domain. + terms : % -> List Term + ++ terms(f) gives the list of non-zero coefficients combined + ++ with their corresponding basis element as records. + ++ This is the internal representation. + map : (R -> R, %) -> % + ++ map(fn,u) maps function fn onto the coefficients + ++ of the non-zero monomials of u. + monomial? : % -> Boolean + ++ monomial?(f) tests if f is a single monomial. + coefficients: % -> List R + ++ coefficients(f) lists all non-zero coefficients. + monomials: % -> List % + ++ monomials(f) gives the list of all monomials whose + ++ sum is f. + numberOfMonomials: % -> NonNegativeInteger + ++ numberOfMonomials(f) is the number of non-zero coefficients + ++ with respect to the canonical basis. + if R has CharacteristicZero then CharacteristicZero + if R has CharacteristicNonZero then CharacteristicNonZero + if R has CommutativeRing then Algebra(R) + if (R has Finite and M has Finite) then Finite + if M has OrderedSet then + leadingMonomial : % -> M + ++ leadingMonomial(f) gives the monomial of f whose + ++ corresponding monoid element is the greatest + ++ among all those with non-zero coefficients. + leadingCoefficient: % -> R + ++ leadingCoefficient(f) gives the coefficient of f, whose + ++ corresponding monoid element is the greatest + ++ among all those with non-zero coefficients. + reductum : % -> % + ++ reductum(f) is f minus its leading monomial. + + MRdefinition ==> add + Ex ==> OutputForm + Cf ==> coef + Mn ==> monom + + Rep := List Term + + coerce(x: List Term): % == x :: % + + monomial(r:R, m:M) == + r = 0 => empty() + [[r, m]] + + if (R has Finite and M has Finite) then + size() == size()$R ** size()$M + + index k == + -- use p-adic decomposition of k + -- coefficient of p**j determines coefficient of index(i+p)$M + i:Integer := k rem size() + p:Integer := size()$R + n:Integer := size()$M + ans:% := 0 + for j in 0.. while i > 0 repeat + h := i rem p + -- we use index(p) = 0$R + if h ^= 0 then + c : R := index(h :: PositiveInteger)$R + m : M := index((j+n) :: PositiveInteger)$M + --ans := ans + c *$% m + ans := ans + monomial(c, m)$% + i := i quo p + ans + + lookup(z : %) : PositiveInteger == + -- could be improved, if M has OrderedSet + -- z = index lookup z, n = lookup index n + -- use p-adic decomposition of k + -- coefficient of p**j determines coefficient of index(i+p)$M + zero?(z) => size()$% pretend PositiveInteger + liTe : List Term := terms z -- all non-zero coefficients + p : Integer := size()$R + n : Integer := size()$M + res : Integer := 0 + for te in liTe repeat + -- assume that lookup(p)$R = 0 + l:NonNegativeInteger:=lookup(te.Mn)$M + ex : NonNegativeInteger := (n=l => 0;l) + co : Integer := lookup(te.Cf)$R + res := res + co * p ** ex + res pretend PositiveInteger + + random() == index( (1+(random()$Integer rem size()$%) )_ + pretend PositiveInteger)$% + + 0 == empty() + 1 == [[1, 1]] + terms a == (copy a) pretend List(Term) + monomials a == [[t] for t in a] + coefficients a == [t.Cf for t in a] + coerce(m:M):% == [[1, m]] + coerce(r:R): % == + -- coerce of ring + r = 0 => 0 + [[r, 1]] + coerce(n:Integer): % == + -- coerce of integers + n = 0 => 0 + [[n::R, 1]] + - a == [[ -t.Cf, t.Mn] for t in a] + if R has noZeroDivisors + then + (r:R) * (a:%) == + r = 0 => 0 + [[r*t.Cf, t.Mn] for t in a] + else + (r:R) * (a:%) == + r = 0 => 0 + [[rt, t.Mn] for t in a | (rt:=r*t.Cf) ^= 0] + if R has noZeroDivisors + then + (n:Integer) * (a:%) == + n = 0 => 0 + [[n*t.Cf, t.Mn] for t in a] + else + (n:Integer) * (a:%) == + n = 0 => 0 + [[nt, t.Mn] for t in a | (nt:=n*t.Cf) ^= 0] + map(f, a) == [[ft, t.Mn] for t in a | (ft:=f(t.Cf)) ^= 0] + numberOfMonomials a == #a + + retractIfCan(a:%):Union(M, "failed") == +-- one?(#a) and one?(a.first.Cf) => a.first.Mn + ((#a) = 1) and ((a.first.Cf) = 1) => a.first.Mn + "failed" + + retractIfCan(a:%):Union(R, "failed") == +-- one?(#a) and one?(a.first.Mn) => a.first.Cf + ((#a) = 1) and ((a.first.Mn) = 1) => a.first.Cf + "failed" + + if R has noZeroDivisors then + if M has Group then + recip a == + lt := terms a + #lt ^= 1 => "failed" + (u := recip lt.first.Cf) case "failed" => "failed" + --(u::R) * inv lt.first.Mn + monomial((u::R), inv lt.first.Mn)$% + else + recip a == + #a ^= 1 or a.first.Mn ^= 1 => "failed" + (u := recip a.first.Cf) case "failed" => "failed" + u::R::% + + mkTerm(r:R, m:M):Ex == + r=1 => m::Ex + r=0 or m=1 => r::Ex + r::Ex * m::Ex + + coerce(a:%):Ex == + empty? a => (0$Integer)::Ex + empty? rest a => mkTerm(a.first.Cf, a.first.Mn) + reduce(_+, [mkTerm(t.Cf, t.Mn) for t in a])$List(Ex) + + if M has OrderedSet then -- we mean totally ordered + -- Terms are stored in decending order. + leadingCoefficient a == (empty? a => 0; a.first.Cf) + leadingMonomial a == (empty? a => 1; a.first.Mn) + reductum a == (empty? a => a; rest a) + + a = b == + #a ^= #b => false + for ta in a for tb in b repeat + ta.Cf ^= tb.Cf or ta.Mn ^= tb.Mn => return false + true + + a + b == + c:% := empty() + while not empty? a and not empty? b repeat + ta := first a; tb := first b + ra := rest a; rb := rest b + c := + ta.Mn > tb.Mn => (a := ra; concat_!(c, ta)) + ta.Mn < tb.Mn => (b := rb; concat_!(c, tb)) + a := ra; b := rb + not zero?(r := ta.Cf+tb.Cf) => + concat_!(c, [r, ta.Mn]) + c + concat_!(c, concat(a, b)) + + coefficient(a, m) == + for t in a repeat + if t.Mn = m then return t.Cf + if t.Mn < m then return 0 + 0 + + + if M has OrderedMonoid then + + -- we use that multiplying an ordered list of monoid elements + -- by a single element respects the ordering + + if R has noZeroDivisors then + a:% * b:% == + +/[[[ta.Cf*tb.Cf, ta.Mn*tb.Mn]$Term + for tb in b ] for ta in reverse a] + else + a:% * b:% == + +/[[[r, ta.Mn*tb.Mn]$Term + for tb in b | not zero?(r := ta.Cf*tb.Cf)] + for ta in reverse a] + else -- M hasn't OrderedMonoid + + -- we cannot assume that mutiplying an ordered list of + -- monoid elements by a single element respects the ordering: + -- we have to order and to collect equal terms + ge : (Term,Term) -> Boolean + ge(s,t) == t.Mn <= s.Mn + + sortAndAdd : List Term -> List Term + sortAndAdd(liTe) == -- assume liTe not empty + liTe := sort(ge,liTe) + m : M := (first liTe).Mn + cf : R := (first liTe).Cf + res : List Term := [] + for te in rest liTe repeat + if m = te.Mn then + cf := cf + te.Cf + else + if not zero? cf then res := cons([cf,m]$Term, res) + m := te.Mn + cf := te.Cf + if not zero? cf then res := cons([cf,m]$Term, res) + reverse res + + + if R has noZeroDivisors then + a:% * b:% == + zero? a => a + zero? b => b -- avoid calling sortAndAdd with [] + +/[sortAndAdd [[ta.Cf*tb.Cf, ta.Mn*tb.Mn]$Term + for tb in b ] for ta in reverse a] + else + a:% * b:% == + zero? a => a + zero? b => b -- avoid calling sortAndAdd with [] + +/[sortAndAdd [[r, ta.Mn*tb.Mn]$Term + for tb in b | not zero?(r := ta.Cf*tb.Cf)] + for ta in reverse a] + + + else -- M hasn't OrderedSet + -- Terms are stored in random order. + a = b == + #a ^= #b => false + brace(a pretend List(Term)) =$Set(Term) brace(b pretend List(Term)) + + coefficient(a, m) == + for t in a repeat + t.Mn = m => return t.Cf + 0 + + addterm(Tabl: AssociationList(M,R), r:R, m:M):R == + (u := search(m, Tabl)) case "failed" => Tabl.m := r + zero?(r := r + u::R) => (remove_!(m, Tabl); 0) + Tabl.m := r + + a + b == + Tabl := table()$AssociationList(M,R) + for t in a repeat + Tabl t.Mn := t.Cf + for t in b repeat + addterm(Tabl, t.Cf, t.Mn) + [[Tabl m, m]$Term for m in keys Tabl] + + a:% * b:% == + Tabl := table()$AssociationList(M,R) + for ta in a repeat + for tb in (b pretend List(Term)) repeat + addterm(Tabl, ta.Cf*tb.Cf, ta.Mn*tb.Mn) + [[Tabl.m, m]$Term for m in keys Tabl] + +@ +\section{package MRF2 MonoidRingFunctions2} +<<package MRF2 MonoidRingFunctions2>>= +)abbrev package MRF2 MonoidRingFunctions2 +++ Author: Johannes Grabmeier +++ Date Created: 14 May 1991 +++ Date Last Updated: 14 May 1991 +++ Basic Operations: map +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: monoid ring, group ring, change of coefficient domain +++ References: +++ Description: +++ MonoidRingFunctions2 implements functions between +++ two monoid rings defined with the same monoid over different rings. +MonoidRingFunctions2(R,S,M) : Exports == Implementation where + R : Ring + S : Ring + M : Monoid + Exports ==> with + map: (R -> S, MonoidRing(R,M)) -> MonoidRing(S,M) + ++ map(f,u) maps f onto the coefficients f the element + ++ u of the monoid ring to create an element of a monoid + ++ ring with the same monoid b. + Implementation ==> add + map(fn, u) == + res : MonoidRing(S,M) := 0 + for te in terms u repeat + res := res + monomial(fn(te.coef), te.monom) + res + +@ +\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 MRING MonoidRing>> +<<package MRF2 MonoidRingFunctions2>> +@ +\eject +\begin{thebibliography}{99} +\bibitem{1} nothing +\end{thebibliography} +\end{document} |