\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{\$SPAD/src/algebra lodop.spad}
\author{Stephen M. Watt, Jean Della Dora}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{category MLO MonogenicLinearOperator}
<<category MLO MonogenicLinearOperator>>=
)abbrev category MLO MonogenicLinearOperator
++ Author: Stephen M. Watt
++ Date Created: 1986
++ Date Last Updated: May 30, 1991
++ Basic Operations:
++ Related Domains:  NonCommutativeOperatorDivision
++ Also See:
++ AMS Classifications:
++ Keywords:
++ Examples:
++ References:
++ Description:
++   This is the category of linear operator rings with one generator.
++   The generator is not named by the category but can always be
++   constructed as \spad{monomial(1,1)}.
++
++   For convenience, call the generator \spad{G}.
++   Then each value is equal to
++       \spad{sum(a(i)*G**i, i = 0..n)}
++   for some unique \spad{n} and \spad{a(i)} in \spad{R}.
++
++   Note that multiplication is not necessarily commutative.
++   In fact,  if \spad{a} is in \spad{R}, it is quite normal
++   to have \spad{a*G \~= G*a}.

MonogenicLinearOperator(R): Category == Defn where
    E ==> NonNegativeInteger
    R: Ring
    Defn == Join(Ring, BiModule(R,R)) with
        if R has CommutativeRing then Algebra(R)
        degree: $ -> E
            ++ degree(l) is \spad{n} if
            ++   \spad{l = sum(monomial(a(i),i), i = 0..n)}.
        minimumDegree: $ -> E
            ++ minimumDegree(l) is the smallest \spad{k} such that
            ++ \spad{a(k) \~= 0} if
            ++   \spad{l = sum(monomial(a(i),i), i = 0..n)}.
        leadingCoefficient: $ -> R
            ++ leadingCoefficient(l) is \spad{a(n)} if
            ++   \spad{l = sum(monomial(a(i),i), i = 0..n)}.
        reductum: $ -> $
            ++ reductum(l) is \spad{l - monomial(a(n),n)} if
            ++   \spad{l = sum(monomial(a(i),i), i = 0..n)}.
        coefficient: ($, E) -> R
            ++ coefficient(l,k) is \spad{a(k)} if
            ++   \spad{l = sum(monomial(a(i),i), i = 0..n)}.
        monomial: (R, E) -> $
            ++ monomial(c,k) produces c times the k-th power of
            ++ the generating operator, \spad{monomial(1,1)}.

@
\section{domain OMLO OppositeMonogenicLinearOperator}
<<domain OMLO OppositeMonogenicLinearOperator>>=
)abbrev domain OMLO OppositeMonogenicLinearOperator
++ Author: Stephen M. Watt
++ Date Created: 1986
++ Date Last Updated: May 30, 1991
++ Basic Operations:
++ Related Domains: MonogenicLinearOperator
++ Also See:
++ AMS Classifications:
++ Keywords: opposite ring
++ Examples:
++ References:
++ Description:
++   This constructor creates the \spadtype{MonogenicLinearOperator} domain
++   which is ``opposite'' in the ring sense to P.
++   That is, as sets \spad{P = $} but \spad{a * b} in \spad{$} is equal to
++   \spad{b * a} in P.

OppositeMonogenicLinearOperator(P, R): OPRcat == OPRdef where
   P: MonogenicLinearOperator(R)
   R: Ring

   OPRcat == MonogenicLinearOperator(R) with
        if P has DifferentialRing then DifferentialRing
        op: P -> $  ++ op(p) creates a value in $ equal to p in P.
        po: $ -> P  ++ po(q) creates a value in P equal to q in $.

   OPRdef  == P add
        Rep == P
        op a == per a
        po x == rep x
        (x: %) * (y: %) == per(rep(y) * rep(x))
        coerce(x): OutputForm == prefix(op::OutputForm, [coerce rep x])

@
\section{package NCODIV NonCommutativeOperatorDivision}
<<package NCODIV NonCommutativeOperatorDivision>>=
)abbrev package NCODIV NonCommutativeOperatorDivision
++ Author: Jean Della Dora, Stephen M. Watt
++ Date Created: 1986
++ Date Last Updated: May 30, 1991
++ Basic Operations:
++ Related Domains: LinearOrdinaryDifferentialOperator
++ Also See:
++ AMS Classifications:
++ Keywords: gcd, lcm, division, non-commutative
++ Examples:
++ References:
++ Description:
++   This package provides a division and related operations for
++   \spadtype{MonogenicLinearOperator}s over a \spadtype{Field}.
++   Since the multiplication is in general non-commutative,
++   these operations all have left- and right-hand versions.
++   This package provides the operations based on left-division.
            -- [q,r] = leftDivide(a,b) means a=b*q+r

NonCommutativeOperatorDivision(P, F): PDcat == PDdef  where
    P: MonogenicLinearOperator(F)
    F: Field

    PDcat == with
        leftDivide:   (P, P) -> Record(quotient: P, remainder: P)
            ++ leftDivide(a,b) returns the pair \spad{[q,r]} such that
            ++ \spad{a = b*q + r} and the degree of \spad{r} is
            ++ less than the degree of \spad{b}.
            ++ This process is called ``left division''.
        leftQuotient:  (P, P) -> P
            ++ leftQuotient(a,b) computes the pair \spad{[q,r]} such that
            ++ \spad{a = b*q + r} and the degree of \spad{r} is
            ++ less than the degree of \spad{b}.
            ++ The value \spad{q} is returned.
        leftRemainder:  (P, P) -> P
            ++ leftRemainder(a,b) computes the pair \spad{[q,r]} such that
            ++ \spad{a = b*q + r} and the degree of \spad{r} is
            ++ less than the degree of \spad{b}.
            ++ The value \spad{r} is returned.
        leftExactQuotient:(P, P) -> Union(P, "failed")
            ++ leftExactQuotient(a,b) computes the value \spad{q}, if it exists,
            ++  such that \spad{a = b*q}.

        leftGcd:   (P, P) -> P
            ++ leftGcd(a,b) computes the value \spad{g} of highest degree
            ++ such that
            ++    \spad{a = aa*g}
            ++    \spad{b = bb*g}
            ++ for some values \spad{aa} and \spad{bb}.
            ++ The value \spad{g} is computed using left-division.
        leftLcm:   (P, P) -> P
            ++ leftLcm(a,b) computes the value \spad{m} of lowest degree
            ++ such that \spad{m = a*aa = b*bb} for some values
            ++ \spad{aa} and \spad{bb}.  The value \spad{m} is
            ++ computed using left-division.

    PDdef == add
        leftDivide(a, b) ==
            q: P := 0
            r: P := a
            iv:F := inv leadingCoefficient b
            while degree r >= degree b and r ~= 0 repeat
                h := monomial(iv*leadingCoefficient r,
              	                 (degree r - degree b)::NonNegativeInteger)$P
                r := r - b*h
                q := q + h
            [q,r]

        -- leftQuotient(a,b) is the quotient from left division, etc.
        leftQuotient(a,b)   == leftDivide(a,b).quotient
        leftRemainder(a,b)   == leftDivide(a,b).remainder
        leftExactQuotient(a,b) ==
             qr := leftDivide(a,b)
             if qr.remainder = 0 then qr.quotient else "failed"
        -- l = leftGcd(a,b) means  a = aa*l  b = bb*l.  Uses leftDivide.
        leftGcd(a,b) ==
             a = 0 =>b
             b = 0 =>a
             while positive? degree b repeat (a,b) := (b, leftRemainder(a,b))
             if b=0 then a else b
        -- l = leftLcm(a,b) means  l = a*aa  l = b*bb   Uses leftDivide.
        leftLcm(a,b) ==
            a = 0 =>b
            b = 0 =>a
            b0 := b
            u  := monomial(1,0)$P
            v: P := 0
            while leadingCoefficient b ~= 0 repeat
                qr     := leftDivide(a,b)
                (a, b) := (b, qr.remainder)
                (u, v) := (u*qr.quotient+v, u)
            b0*u

@
\section{domain ODR OrdinaryDifferentialRing}
<<domain ODR OrdinaryDifferentialRing>>=
)abbrev domain ODR OrdinaryDifferentialRing
++ Author: Stephen M. Watt
++ Date Created: 1986
++ Date Last Updated: June 3, 1991
++ Basic Operations:
++ Related Domains:
++ Also See:
++ AMS Classifications:
++ Keywords: differential ring
++ Examples:
++ References:
++ Description:
++   This constructor produces an ordinary differential ring from
++   a partial differential ring by specifying a variable.

OrdinaryDifferentialRing(Kernels,R,var): DRcategory == DRcapsule where
    Kernels:SetCategory
    R: PartialDifferentialRing(Kernels)
    var : Kernels
    DRcategory == Join(BiModule(%,%), DifferentialRing, HomotopicTo R) with
        if R has Field then Field
    DRcapsule == R add
        n: Integer
        Rep == R
        coerce(u: R): % == per u
        coerce(p: %): R == rep p
        differentiate p == per differentiate(rep p, var)

        if R has Field then
            p / q     == per(rep(p) / rep(q))
            p ** n    == per(rep(p) ** n)
            inv(p)    == per inv rep p

@
\section{domain DPMO DirectProductModule}
<<domain DPMO DirectProductModule>>=
)abbrev domain DPMO DirectProductModule
++ Author:  Stephen M. Watt
++ Date Created: 1986
++ Date Last Updated: June 4, 1991
++ Basic Operations:
++ Related Domains:
++ Also See:
++ AMS Classifications:
++ Keywords: equation
++ Examples:
++ References:
++ Description:
++   This constructor provides a direct product of R-modules
++   with an R-module view.

DirectProductModule(n, R, S): DPcategory == DPcapsule where
    n: NonNegativeInteger
    R: Ring
    S: LeftModule(R)

    DPcategory == Join(DirectProductCategory(n,S), LeftModule(R))
    --  with if S has Algebra(R) then Algebra(R)
    --  <above line leads to matchMmCond: unknown form of condition>

    DPcapsule == DirectProduct(n,S) add
        Rep := Vector(S)
        r:R * x:$ == [r * x.i for i in 1..n]

@
\section{domain DPMM DirectProductMatrixModule}
<<domain DPMM DirectProductMatrixModule>>=
)abbrev domain DPMM DirectProductMatrixModule
++ Author:  Stephen M. Watt
++ Date Created: 1986
++ Date Last Updated: June 4, 1991
++ Basic Operations:
++ Related Domains:
++ Also See:
++ AMS Classifications:
++ Keywords: equation
++ Examples:
++ References:
++ Description:
++   This constructor provides a direct product type with a
++   left matrix-module view.

DirectProductMatrixModule(n, R, M, S): DPcategory == DPcapsule where
    n: PositiveInteger
    R: Ring
    RowCol ==> DirectProduct(n,R)
    M: SquareMatrixCategory(n,R,RowCol,RowCol)
    S: LeftModule(R)

    DPcategory == Join(DirectProductCategory(n,S), LeftModule(R), LeftModule(M))

    DPcapsule == DirectProduct(n, S) add
        Rep := Vector(S)
        r:R * x:$ == [r*x.i for i in 1..n]
        m:M * x:$ == [ +/[m(i,j)*x.j for j in 1..n] for i in 1..n]

@
\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>>

<<category MLO MonogenicLinearOperator>>
<<domain OMLO OppositeMonogenicLinearOperator>>
<<package NCODIV NonCommutativeOperatorDivision>>
<<domain ODR OrdinaryDifferentialRing>>
<<domain DPMO DirectProductModule>>
<<domain DPMM DirectProductMatrixModule>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}