\documentclass{article}
\usepackage{axiom}
\begin{document}
\title{\$SPAD/src/algebra lodo.spad}
\author{Manuel Bronstein, Stephen M. Watt}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{category LODOCAT LinearOrdinaryDifferentialOperatorCategory}
<<category LODOCAT LinearOrdinaryDifferentialOperatorCategory>>=
)abbrev category LODOCAT LinearOrdinaryDifferentialOperatorCategory
++ Author: Manuel Bronstein
++ Date Created: 9 December 1993
++ Date Last Updated: 15 April 1994
++ Keywords: differential operator
++ Description:
++   \spad{LinearOrdinaryDifferentialOperatorCategory} is the category
++   of differential operators with coefficients in a ring A with a given
++   derivation.
++   Multiplication of operators corresponds to functional composition:
++       \spad{(L1 * L2).(f) = L1 L2 f}
LinearOrdinaryDifferentialOperatorCategory(A:Ring): Category ==
  Join(UnivariateSkewPolynomialCategory A, Eltable(A, A)) with
        D: () -> %
            ++ D() provides the operator corresponding to a derivation
            ++ in the ring \spad{A}.
        adjoint: % -> %
            ++ adjoint(a) returns the adjoint operator of a.
        if A has Field then
          symmetricProduct: (%, %) -> %
            ++ symmetricProduct(a,b) computes an operator \spad{c} of
            ++ minimal order such that the nullspace of \spad{c} is
            ++ generated by all the products of a solution of \spad{a} by
            ++ a solution of \spad{b}.
          symmetricPower  : (%, NonNegativeInteger) -> %
            ++ symmetricPower(a,n) computes an operator \spad{c} of
            ++ minimal order such that the nullspace of \spad{c} is
            ++ generated by all the products of \spad{n} solutions
            ++ of \spad{a}.
          symmetricSquare : % -> %
            ++ symmetricSquare(a) computes \spad{symmetricProduct(a,a)}
            ++ using a more efficient method.
          directSum: (%, %) -> %
            ++ directSum(a,b) computes an operator \spad{c} of
            ++ minimal order such that the nullspace of \spad{c} is
            ++ generated by all the sums of a solution of \spad{a} by
            ++ a solution of \spad{b}.
   add
        m1monom: NonNegativeInteger -> %

        D() == monomial(1, 1)

        m1monom n ==
          a:A := (odd? n => -1; 1)
          monomial(a, n)

        adjoint a ==
          ans:% := 0
          while a ~= 0 repeat
            ans := ans + m1monom(degree a) * leadingCoefficient(a)::%
            a   := reductum a
          ans

        if A has Field then symmetricSquare l == symmetricPower(l, 2)

@
\section{package LODOOPS LinearOrdinaryDifferentialOperatorsOps}
<<package LODOOPS LinearOrdinaryDifferentialOperatorsOps>>=
)abbrev package LODOOPS LinearOrdinaryDifferentialOperatorsOps
++ Author: Manuel Bronstein
++ Date Created: 18 January 1994
++ Date Last Updated: 15 April 1994
++ Description:
++   \spad{LinearOrdinaryDifferentialOperatorsOps} provides symmetric
++   products and sums for linear ordinary differential operators.
-- Putting those operations here rather than defaults in LODOCAT allows
-- LODOCAT to be defined independently of the derivative used.
-- MB 1/94
LinearOrdinaryDifferentialOperatorsOps(A, L): Exports == Implementation where
    A: Field
    L: LinearOrdinaryDifferentialOperatorCategory A

    N  ==> NonNegativeInteger
    V  ==> OrderlyDifferentialVariable Symbol
    P  ==> DifferentialSparseMultivariatePolynomial(A, Symbol, V)

    Exports ==> with
          symmetricProduct: (L, L, A -> A) -> L
            ++ symmetricProduct(a,b,D) computes an operator \spad{c} of
            ++ minimal order such that the nullspace of \spad{c} is
            ++ generated by all the products of a solution of \spad{a} by
            ++ a solution of \spad{b}.
            ++ D is the derivation to use.
          symmetricPower: (L, N, A -> A) -> L
            ++ symmetricPower(a,n,D) computes an operator \spad{c} of
            ++ minimal order such that the nullspace of \spad{c} is
            ++ generated by all the products of \spad{n} solutions
            ++ of \spad{a}.
            ++ D is the derivation to use.
          directSum: (L, L, A -> A) -> L
            ++ directSum(a,b,D) computes an operator \spad{c} of
            ++ minimal order such that the nullspace of \spad{c} is
            ++ generated by all the sums of a solution of \spad{a} by
            ++ a solution of \spad{b}.
            ++ D is the derivation to use.

    Implementation ==> add
          import IntegerCombinatoricFunctions

          var1 := new()$Symbol
          var2 := new()$Symbol

          nonTrivial?: Vector A -> Boolean
          applyLODO  : (L, V) -> P
          killer     : (P, N, List V, List P, A -> A) -> L
          vec2LODO   : Vector A -> L

          nonTrivial? v == any?(#1 ~= 0, v)$Vector(A)
          vec2LODO v    == +/[monomial(v.i, (i-1)::N) for i in 1..#v]

          symmetricPower(l, m, diff) ==
            u := var1::V; n := degree l
            un := differentiate(u, n)
            a  := applyLODO(inv(- leadingCoefficient l) * reductum l, u)
            killer(u::P ** m, binomial(n + m - 1, n - 1)::N, [un], [a], diff)

-- returns an operator L such that L(u) = 0, for a given differential
-- polynomial u, given that the differential variables appearing in u
-- satisfy some linear ode's
-- m is a bound on the order of the operator searched.
-- lvar, lval describe the substitution(s) to perform when differentiating
--     the expression u (they encode the fact the the differential variables
--     satisfy some differential equations, which can be seen as the rewrite
--     rules   lvar --> lval)
-- diff is the derivation to use
          killer(u, m, lvar, lval, diff) ==
            lu:List P := [u]
            for q in 0..m repeat
              mat := reducedSystem(matrix([lu])@Matrix(P))@Matrix(A)
              (sol := find(nonTrivial?, l := nullSpace mat)) case Vector(A) =>
                return vec2LODO(sol::Vector(A))
              u := eval(differentiate(u, diff), lvar, lval)
              lu := concat!(lu, [u])
            error "killer: no linear dependence found"

          symmetricProduct(l1, l2, diff) ==
            u  := var1::V;   v  := var2::V
            n1 := degree l1; n2 := degree l2
            un := differentiate(u, n1); vn := differentiate(v, n2)
            a  := applyLODO(inv(- leadingCoefficient l1) * reductum l1, u)
            b  := applyLODO(inv(- leadingCoefficient l2) * reductum l2, v)
            killer(u::P * v::P, n1 * n2, [un, vn], [a, b], diff)

          directSum(l1, l2, diff) ==
            u  := var1::V;   v  := var2::V
            n1 := degree l1; n2 := degree l2
            un := differentiate(u, n1); vn := differentiate(v, n2)
            a  := applyLODO(inv(- leadingCoefficient l1) * reductum l1, u)
            b  := applyLODO(inv(- leadingCoefficient l2) * reductum l2, v)
            killer(u::P + v::P, n1 + n2, [un, vn], [a, b], diff)

          applyLODO(l, v) ==
            p:P := 0
            while l ~= 0 repeat
              p := p + monomial(leadingCoefficient(l)::P,
                                  differentiate(v, degree l), 1)
              l := reductum l
            p

@
\section{domain LODO LinearOrdinaryDifferentialOperator}
<<domain LODO LinearOrdinaryDifferentialOperator>>=
)abbrev domain LODO LinearOrdinaryDifferentialOperator
++ Author: Manuel Bronstein
++ Date Created: 9 December 1993
++ Date Last Updated: 15 April 1994
++ Keywords: differential operator
++ Description:
++   \spad{LinearOrdinaryDifferentialOperator} defines a ring of
++   differential operators with coefficients in a ring A with a given
++   derivation.
++   Multiplication of operators corresponds to functional composition:
++       \spad{(L1 * L2).(f) = L1 L2 f}
LinearOrdinaryDifferentialOperator(A:Ring, diff: A -> A):
    LinearOrdinaryDifferentialOperatorCategory A
      == SparseUnivariateSkewPolynomial(A, 1, diff) add
        Rep := SparseUnivariateSkewPolynomial(A, 1, diff)

        outputD := "D"@String :: Symbol :: OutputForm

        coerce(l:%):OutputForm == outputForm(l, outputD)
        elt(p:%, a:A):A        == apply(p, 0, a)

        if A has Field then
            import LinearOrdinaryDifferentialOperatorsOps(A, %)

            symmetricProduct(a, b) == symmetricProduct(a, b, diff)
            symmetricPower(a, n)   == symmetricPower(a, n, diff)
            directSum(a, b)        == directSum(a, b, diff)

@
\section{domain LODO1 LinearOrdinaryDifferentialOperator1}
<<domain LODO1 LinearOrdinaryDifferentialOperator1>>=
)abbrev domain LODO1 LinearOrdinaryDifferentialOperator1
++ Author: Manuel Bronstein
++ Date Created: 9 December 1993
++ Date Last Updated: 31 January 1994
++ Keywords: differential operator
++ Description:
++   \spad{LinearOrdinaryDifferentialOperator1} defines a ring of
++   differential operators with coefficients in a differential ring A.
++   Multiplication of operators corresponds to functional composition:
++       \spad{(L1 * L2).(f) = L1 L2 f}
LinearOrdinaryDifferentialOperator1(A:DifferentialRing) ==
  LinearOrdinaryDifferentialOperator(A, differentiate$A)

@
\section{domain LODO2 LinearOrdinaryDifferentialOperator2}
<<domain LODO2 LinearOrdinaryDifferentialOperator2>>=
)abbrev domain LODO2 LinearOrdinaryDifferentialOperator2
++ Author: Stephen M. Watt, Manuel Bronstein
++ Date Created: 1986
++ Date Last Updated: 1 February 1994
++ Keywords: differential operator
++ Description:
++   \spad{LinearOrdinaryDifferentialOperator2} defines a ring of
++   differential operators with coefficients in a differential ring A
++   and acting on an A-module M.
++   Multiplication of operators corresponds to functional composition:
++       \spad{(L1 * L2).(f) = L1 L2 f}
LinearOrdinaryDifferentialOperator2(A, M): Exports == Implementation where
  A: DifferentialRing
  M: LeftModule A with 
	differentiate: $ -> $
		++ differentiate(x) returns the derivative of x

  Exports ==> Join(LinearOrdinaryDifferentialOperatorCategory A, Eltable(M, M))

  Implementation ==> LinearOrdinaryDifferentialOperator(A, differentiate$A) add
      elt(p:%, m:M):M ==
        apply(p, differentiate, m)$ApplyUnivariateSkewPolynomial(A, M, %)

@
\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 LODOCAT LinearOrdinaryDifferentialOperatorCategory>>
<<package LODOOPS LinearOrdinaryDifferentialOperatorsOps>>
<<domain LODO LinearOrdinaryDifferentialOperator>>
<<domain LODO1 LinearOrdinaryDifferentialOperator1>>
<<domain LODO2 LinearOrdinaryDifferentialOperator2>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}