path: root/src/algebra/dpolcat.spad.pamphlet

\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{\$SPAD/src/algebra dpolcat.spad}
\author{William Sit}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{category DVARCAT DifferentialVariableCategory}
<<category DVARCAT DifferentialVariableCategory>>=
)abbrev category DVARCAT DifferentialVariableCategory
++ Author:  William Sit
++ Date Created: 19 July 1990
++ Date Last Updated: 13 September 1991
++ Basic Operations:
++ Related Constructors:DifferentialPolynomialCategory
++ See Also:OrderedDifferentialVariable,
++          SequentialDifferentialVariable,
++          DifferentialSparseMultivariatePolynomial.
++ AMS Classifications:12H05
++ Keywords: differential indeterminates, ranking, order, weight
++ References:Ritt, J.F. "Differential Algebra" (Dover, 1950).
++ Description:
++   \spadtype{DifferentialVariableCategory} constructs the
++   set of derivatives of a given set of
++   (ordinary) differential indeterminates.
++   If x,...,y is an ordered set of differential indeterminates,
++   and the prime notation is used for differentiation, then
++   the set of derivatives (including
++   zero-th order) of the differential indeterminates is
++   x,\spad{x'},\spad{x''},..., y,\spad{y'},\spad{y''},...
++   (Note: in the interpreter, the n-th derivative of y is displayed as
++   y with a subscript n.)  This set is
++   viewed as a set of algebraic indeterminates, totally ordered in a
++   way compatible with differentiation and the given order on the
++   differential indeterminates.  Such a total order is called a
++   ranking of the differential indeterminates.
++
++   A domain in this category is needed to construct a differential
++   polynomial domain.  Differential polynomials are ordered
++   by a ranking on the derivatives,  and by an order (extending the
++   ranking) on
++   on the set of differential monomials.  One may thus associate
++   a domain in this category with a ranking of the differential
++   indeterminates, just as one associates a domain in the category
++   \spadtype{OrderedAbelianMonoidSup} with an ordering of the set of
++   monomials in a set of algebraic indeterminates.  The ranking
++   is specified through the binary relation \spadfun{<}.
++   For example, one may define
++   one derivative to be less than another by lexicographically comparing
++   first the \spadfun{order}, then the given order of the differential
++   indeterminates appearing in the derivatives.  This is the default
++   implementation.
++
++   The notion of weight generalizes that of degree.  A
++   polynomial domain may be made into a graded ring
++   if a weight function is given on the set of indeterminates,
++   Very often, a grading is the first step in ordering the set of
++   monomials.  For differential polynomial domains, this
++   constructor provides a function \spadfun{weight}, which
++   allows the assignment of a non-negative number to each derivative of a
++   differential indeterminate.  For example, one may define
++   the weight of a derivative to be simply its \spadfun{order}
++   (this is the default assignment).
++   This weight function can then be extended to the set of
++   all differential polynomials, providing a graded ring
++   structure.
DifferentialVariableCategory(S:OrderedSet): Category ==
  Join(OrderedSet, DifferentialSpace, RetractableTo S) with
    -- Examples:
    -- v:=makeVariable('s,5)
    makeVariable  : (S, NonNegativeInteger) -> $
       ++ makeVariable(s, n) returns the n-th derivative of a
       ++ differential indeterminate s as an algebraic indeterminate.
       -- Example: makeVariable('s, 5)
    order         : $ -> NonNegativeInteger
       ++ order(v) returns n if v is the n-th derivative of any
       ++ differential indeterminate.
       -- Example: order(v)
    variable      : $ -> S
       ++ variable(v) returns s if v is any derivative of the differential
       ++ indeterminate s.
       -- Example: variable(v)
          --  default implementation using above primitives --

    weight        : $ -> NonNegativeInteger
       ++ weight(v) returns the weight of the derivative v.
       -- Example: weight(v)
 add
    import NumberFormats
    coerce (s:S):$ == makeVariable(s, 0)
    differentiate v     == differentiate(v, 1)
    differentiate(v, n) == makeVariable(variable v, n + order v)
    retractIfCan v == (zero?(order v) => variable v; "failed")
    v = u      == (variable v = variable u) and (order v = order u)

    coerce(v:$):OutputForm ==
      a := variable(v)::OutputForm
      zero?(nn := order v) => a
      sub(a, outputForm nn)
    retract v ==
      zero?(order v) => variable v
      error "Not retractable"
    v < u ==
      -- the ranking below is orderly, and is the default --
      order v = order u => variable v < variable u
      order v < order u
    weight v == order v
      --  the default weight is just the order

@
\section{domain ODVAR OrderlyDifferentialVariable}
<<domain ODVAR OrderlyDifferentialVariable>>=
)abbrev domain ODVAR OrderlyDifferentialVariable
++ Author:  William Sit
++ Date Created: 19 July 1990
++ Date Last Updated: 13 September 1991
++ Basic Operations:differentiate, order, variable,<
++ Related Domains: OrderedVariableList,
++                  SequentialDifferentialVariable.
++ See Also: DifferentialVariableCategory
++ AMS Classifications:12H05
++ Keywords: differential indeterminates, orderly ranking.
++ References:Kolchin, E.R. "Differential Algebra and Algebraic Groups"
++   (Academic Press, 1973).
++ Description:
++   \spadtype{OrderlyDifferentialVariable} adds a commonly used orderly
++   ranking to the set of derivatives of an ordered list of differential
++   indeterminates.  An orderly ranking is a ranking \spadfun{<} of the
++   derivatives with the property that for two derivatives u and v,
++   u \spadfun{<} v if the \spadfun{order} of u is less than that
++   of v.
++   This domain belongs to \spadtype{DifferentialVariableCategory}.  It
++   defines \spadfun{weight} to be just \spadfun{order}, and it
++   defines an orderly ranking \spadfun{<} on derivatives u via the
++   lexicographic order on the pair
++   (\spadfun{order}(u), \spadfun{variable}(u)).
OrderlyDifferentialVariable(S:OrderedSet):DifferentialVariableCategory(S)
  == add
    Rep := Record(var:S, ord:NonNegativeInteger)
    makeVariable(s,n) == [s, n]
    variable v     == v.var
    order v        == v.ord

@
\section{domain SDVAR SequentialDifferentialVariable}
<<domain SDVAR SequentialDifferentialVariable>>=
)abbrev domain SDVAR SequentialDifferentialVariable
++ Author:  William Sit
++ Date Created: 19 July 1990
++ Date Last Updated: 13 September 1991
++ Basic Operations:differentiate, order, variable, <
++ Related Domains: OrderedVariableList,
++                  OrderlyDifferentialVariable.
++ See Also:DifferentialVariableCategory
++ AMS Classifications:12H05
++ Keywords: differential indeterminates, sequential ranking.
++ References:Kolchin, E.R. "Differential Algebra and Algebraic Groups"
++   (Academic Press, 1973).
++ Description:
++   \spadtype{OrderlyDifferentialVariable} adds a commonly used sequential
++   ranking to the set of derivatives of an ordered list of differential
++   indeterminates.  A sequential ranking is a ranking \spadfun{<} of the
++   derivatives with the property that for any derivative v,
++   there are only a finite number of derivatives u with u \spadfun{<} v.
++   This domain belongs to \spadtype{DifferentialVariableCategory}.  It
++   defines \spadfun{weight} to be just \spadfun{order}, and it
++   defines a sequential ranking \spadfun{<} on derivatives u by the
++   lexicographic order on the pair
++   (\spadfun{variable}(u), \spadfun{order}(u)).

SequentialDifferentialVariable(S:OrderedSet):DifferentialVariableCategory(S)
  == add
    Rep := Record(var:S, ord:NonNegativeInteger)
    makeVariable(s,n) == [s, n]
    variable v     == v.var
    order v        == v.ord
    v < u ==
      variable v = variable u => order v < order u
      variable v < variable u

@
\section{category DPOLCAT DifferentialPolynomialCategory}
<<category DPOLCAT DifferentialPolynomialCategory>>=
)abbrev category DPOLCAT DifferentialPolynomialCategory
++ Author:  William Sit
++ Date Created: 19 July 1990
++ Date Last Updated: 13 September 1991
++ Basic Operations:PolynomialCategory
++ Related Constructors:DifferentialVariableCategory
++ See Also:
++ AMS Classifications:12H05
++ Keywords: differential indeterminates, ranking, differential polynomials,
++           order, weight, leader, separant, initial, isobaric
++ References:Kolchin, E.R. "Differential Algebra and Algebraic Groups"
++   (Academic Press, 1973).
++ Description:
++   \spadtype{DifferentialPolynomialCategory} is a category constructor
++   specifying basic functions in an ordinary differential polynomial
++   ring with a given ordered set of differential indeterminates.
++   In addition, it implements defaults for the basic functions.
++   The functions \spadfun{order} and \spadfun{weight} are extended
++   from the set of derivatives of differential indeterminates
++   to the set of differential polynomials.  Other operations
++   provided on differential polynomials are
++   \spadfun{leader}, \spadfun{initial},
++   \spadfun{separant}, \spadfun{differentialVariables}, and
++   \spadfun{isobaric?}.   Furthermore, if the ground ring is
++   a differential ring, then evaluation (substitution
++   of differential indeterminates by elements of the ground ring
++   or by differential polynomials) is
++   provided by \spadfun{eval}.
++   A convenient way of referencing derivatives is provided by
++   the functions \spadfun{makeVariable}.
++
++   To construct a domain using this constructor, one needs
++   to provide a ground ring R, an ordered set S of differential
++   indeterminates, a ranking V on the set of derivatives
++   of the differential indeterminates, and a set E of
++   exponents in bijection with the set of differential monomials
++   in the given differential indeterminates.
++

DifferentialPolynomialCategory(R:Ring,S:OrderedSet,
  V:DifferentialVariableCategory S, E:OrderedAbelianMonoidSup):
              Category ==
  Join(PolynomialCategory(R,E,V),
       DifferentialExtension R, RetractableTo S) with
    -- Examples:
    -- s:=makeVariable('s)
    -- p:= 3*(s 1)**2 + s*(s 2)**3
    --  all functions below have default implementations
    --  using primitives from V

    makeVariable: S -> (NonNegativeInteger -> $)
       ++ makeVariable(s) views s as a differential
       ++ indeterminate,  in such a way that the n-th
       ++ derivative of s may be simply referenced as z.n
       ++ where z :=makeVariable(s).
       ++ Note: In the interpreter, z is
       ++ given as an internal map, which may be ignored.
       -- Example: makeVariable('s); %.5

    differentialVariables: $ ->  List S
      ++ differentialVariables(p) returns a list of differential
      ++ indeterminates occurring in a differential polynomial p.
    order : ($, S) -> NonNegativeInteger
      ++ order(p,s) returns the order of the differential
      ++ polynomial p in differential indeterminate s.
    order : $   -> NonNegativeInteger
      ++ order(p) returns the order of the differential polynomial p,
      ++ which is the maximum number of differentiations of a
      ++ differential indeterminate, among all those appearing in p.
    degree: ($, S) -> NonNegativeInteger
      ++ degree(p, s) returns the maximum degree of
      ++ the differential polynomial p viewed as a differential polynomial
      ++ in the differential indeterminate s alone.
    weights: $ -> List NonNegativeInteger
      ++ weights(p) returns a list of weights of differential monomials
      ++ appearing in differential polynomial p.
    weight: $   -> NonNegativeInteger
      ++ weight(p) returns the maximum weight of all differential monomials
      ++ appearing in the differential polynomial p.
    weights: ($, S) -> List NonNegativeInteger
      ++ weights(p, s) returns a list of
      ++ weights of differential monomials
      ++ appearing in the differential polynomial p when p is viewed
      ++ as a differential polynomial in the differential indeterminate s
      ++ alone.
    weight: ($, S) -> NonNegativeInteger
      ++ weight(p, s) returns the maximum weight of all differential
      ++ monomials appearing in the differential polynomial p
      ++ when p is viewed as a differential polynomial in
      ++ the differential indeterminate s alone.
    isobaric?: $ -> Boolean
      ++ isobaric?(p) returns true if every differential monomial appearing
      ++ in the differential polynomial p has same weight,
      ++ and returns false otherwise.
    leader: $   -> V
      ++ leader(p) returns the derivative of the highest rank
      ++ appearing in the differential polynomial p
      ++ Note: an error occurs if p is in the ground ring.
    initial:$   -> $
      ++ initial(p) returns the
      ++ leading coefficient when the differential polynomial p
      ++ is written as a univariate polynomial in its leader.
    separant:$  -> $
      ++ separant(p) returns the
      ++ partial derivative of the differential polynomial p
      ++ with respect to its leader.
    if R has DifferentialRing then
      InnerEvalable(S, R)
      InnerEvalable(S, $)
      Evalable $
      makeVariable: $ -> (NonNegativeInteger -> $)
       ++ makeVariable(p) views p as an element of a differential
       ++ ring,  in such a way that the n-th
       ++ derivative of p may be simply referenced as z.n
       ++ where z := makeVariable(p).
       ++ Note: In the interpreter, z is
       ++ given as an internal map, which may be ignored.
       -- Example: makeVariable(p); %.5; makeVariable(%**2); %.2

 add
    p:$
    s:S
    makeVariable s == makeVariable(s,#1)::$

    if R has IntegralDomain then
      differentiate(p:$, d:R -> R) ==
        ans:$ := 0
        l := variables p
        u : Union(R, "failed")
        while (u:=retractIfCan(p)@Union(R, "failed")) case "failed" repeat
          t := leadingMonomial p
          lc := leadingCoefficient t
          ans := ans + d(lc)::$ * (t exquo lc)::$
              + +/[differentiate(t, v) * (differentiate v)::$ for v in l]
          p := reductum p
        ans + d(u::R)::$

    order (p:$):NonNegativeInteger ==
      ground? p => 0
      "max"/[order v for v in variables p]
    order (p:$,s:S):NonNegativeInteger ==
      ground? p => 0
      empty? (vv:= [order v for v in variables p | (variable v) = s ]) => 0
      "max"/vv

    degree (p, s) ==
      d:NonNegativeInteger:=0
      for lp in monomials p repeat
        lv:= [v for v in variables lp | (variable v) = s ]
        if not empty? lv then d:= max(d, +/degree(lp, lv))
      d

    weights p ==
      ws:List NonNegativeInteger := nil
      empty? (mp:=monomials p) => ws
      for lp in mp repeat
        lv:= variables lp
        if not empty? lv then
          dv:= degree(lp, lv)
          w:=+/[(weight v) * d for v in lv for d in dv]$(List NonNegativeInteger)
          ws:= concat(ws, w)
      ws
    weight p ==
      empty? (ws:=weights p) => 0
      "max"/ws

    weights (p, s) ==
      ws:List NonNegativeInteger := nil
      empty?(mp:=monomials p) => ws
      for lp in mp repeat
        lv:= [v for v in variables lp | (variable v) = s ]
        if not empty? lv then
          dv:= degree(lp, lv)
          w:=+/[(weight v) * d for v in lv for d in dv]$(List NonNegativeInteger)
          ws:= concat(ws, w)
      ws
    weight (p,s)  ==
      empty? (ws:=weights(p,s)) => 0
      "max"/ws

    isobaric? p == (# removeDuplicates weights p) = 1

    leader p ==             -- depends on the ranking
      vl:= variables p
      -- it's not enough just to look at leadingMonomial p
      -- the term-ordering need not respect the ranking
      empty? vl => error "leader is not defined "
      "max"/vl
    initial p == leadingCoefficient univariate(p,leader p)
    separant p == differentiate(p, leader p)

    coerce(s:S):$   == s::V::$

    retractIfCan(p:$):Union(S, "failed") ==
      (v := retractIfCan(p)@Union(V,"failed")) case "failed" => "failed"
      retractIfCan(v::V)

    differentialVariables p ==
      removeDuplicates [variable v for v in variables p]

    if R has DifferentialRing then

      makeVariable p == differentiate(p, #1)

      eval(p:$, sl:List S, rl:List R) ==
        ordp:= order p
        vl  := concat [[makeVariable(s,j)$V for j in  0..ordp]
                                for s in sl]$List(List V)
        rrl:=nil$List(R)
        for r in rl repeat
          t:= r
          rrl:= concat(rrl,
                concat(r, [t := differentiate t for i in 1..ordp]))
        eval(p, vl, rrl)

      eval(p:$, sl:List S, rl:List $) ==
        ordp:= order p
        vl  := concat [[makeVariable(s,j)$V for j in  0..ordp]
                                for s in sl]$List(List V)
        rrl:=nil$List($)
        for r in rl repeat
          t:=r
          rrl:=concat(rrl,
               concat(r, [t:=differentiate t for i in 1..ordp]))
        eval(p, vl, rrl)
      eval(p:$, l:List Equation $) ==
        eval(p, [retract(lhs e)@S for e in l]$List(S),
              [rhs e for e in l]$List($))

@
\section{domain DSMP DifferentialSparseMultivariatePolynomial}
<<domain DSMP DifferentialSparseMultivariatePolynomial>>=
)abbrev domain DSMP DifferentialSparseMultivariatePolynomial
++ Author:  William Sit
++ Date Created: 19 July 1990
++ Date Last Updated: 13 September 1991
++ Basic Operations:DifferentialPolynomialCategory
++ Related Constructors:
++ See Also:
++ AMS Classifications:12H05
++ Keywords: differential indeterminates, ranking, differential polynomials,
++           order, weight, leader, separant, initial, isobaric
++ References:Kolchin, E.R. "Differential Algebra and Algebraic Groups"
++   (Academic Press, 1973).
++ Description:
++   \spadtype{DifferentialSparseMultivariatePolynomial} implements
++   an ordinary differential polynomial ring by combining a
++   domain belonging to the category \spadtype{DifferentialVariableCategory}
++   with the domain \spadtype{SparseMultivariatePolynomial}.
++

DifferentialSparseMultivariatePolynomial(R, S, V):
     Exports == Implementation where
  R: Ring
  S: OrderedSet
  V: DifferentialVariableCategory S
  E   ==> IndexedExponents(V)
  PC  ==> PolynomialCategory(R,IndexedExponents(V),V)
  PCL ==> PolynomialCategoryLifting
  P   ==> SparseMultivariatePolynomial(R, V)
  SUP ==> SparseUnivariatePolynomial
  SMP ==> SparseMultivariatePolynomial(R, S)

  Exports ==> Join(DifferentialPolynomialCategory(R,S,V,E),
                   RetractableTo SMP)

  Implementation ==> P add
    retractIfCan(p:$):Union(SMP, "failed") ==
      zero? order p =>
        map(retract(#1)@S :: SMP, #1::SMP, p)$PCL(
                                  IndexedExponents V, V, R, $, SMP)
      "failed"

    coerce(p:SMP):$ ==
      map(#1::V::$, #1::$, p)$PCL(IndexedExponents S, S, R, SMP, $)

@
\section{domain ODPOL OrderlyDifferentialPolynomial}
<<domain ODPOL OrderlyDifferentialPolynomial>>=
)abbrev domain ODPOL OrderlyDifferentialPolynomial
++ Author:  William Sit
++ Date Created: 24 September, 1991
++ Date Last Updated: 7 February, 1992
++ Basic Operations:DifferentialPolynomialCategory
++ Related Constructors: DifferentialSparseMultivariatePolynomial
++ See Also:
++ AMS Classifications:12H05
++ Keywords: differential indeterminates, ranking, differential polynomials,
++           order, weight, leader, separant, initial, isobaric
++ References:Kolchin, E.R. "Differential Algebra and Algebraic Groups"
++   (Academic Press, 1973).
++ Description:
++   \spadtype{OrderlyDifferentialPolynomial} implements
++   an ordinary differential polynomial ring in arbitrary number
++   of differential indeterminates, with coefficients in a
++   ring.  The ranking on the differential indeterminate is orderly.
++   This is analogous to the domain \spadtype{Polynomial}.
++

OrderlyDifferentialPolynomial(R):
     Exports == Implementation where
  R: Ring
  S  ==> Symbol
  V  ==> OrderlyDifferentialVariable S
  E   ==> IndexedExponents(V)
  SMP ==> SparseMultivariatePolynomial(R, S)
  Exports ==> Join(DifferentialPolynomialCategory(R,S,V,E),
                   RetractableTo SMP)

  Implementation ==> DifferentialSparseMultivariatePolynomial(R,S,V)

@
\section{domain SDPOL SequentialDifferentialPolynomial}
<<domain SDPOL SequentialDifferentialPolynomial>>=
)abbrev domain SDPOL SequentialDifferentialPolynomial
++ Author:  William Sit
++ Date Created: 24 September, 1991
++ Date Last Updated: 7 February, 1992
++ Basic Operations:DifferentialPolynomialCategory
++ Related Constructors: DifferentialSparseMultivariatePolynomial
++ See Also:
++ AMS Classifications:12H05
++ Keywords: differential indeterminates, ranking, differential polynomials,
++           order, weight, leader, separant, initial, isobaric
++ References:Kolchin, E.R. "Differential Algebra and Algebraic Groups"
++   (Academic Press, 1973).
++ Description:
++   \spadtype{SequentialDifferentialPolynomial} implements
++   an ordinary differential polynomial ring in arbitrary number
++   of differential indeterminates, with coefficients in a
++   ring.  The ranking on the differential indeterminate is sequential.
++

SequentialDifferentialPolynomial(R):
     Exports == Implementation where
  R: Ring
  S  ==> Symbol
  V  ==> SequentialDifferentialVariable S
  E   ==> IndexedExponents(V)
  SMP ==> SparseMultivariatePolynomial(R, S)
  Exports ==> Join(DifferentialPolynomialCategory(R,S,V,E),
                   RetractableTo SMP)

  Implementation ==> DifferentialSparseMultivariatePolynomial(R,S,V)

@
\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 DVARCAT DifferentialVariableCategory>>
<<domain ODVAR OrderlyDifferentialVariable>>
<<domain SDVAR SequentialDifferentialVariable>>
<<category DPOLCAT DifferentialPolynomialCategory>>
<<domain DSMP DifferentialSparseMultivariatePolynomial>>
<<domain ODPOL OrderlyDifferentialPolynomial>>
<<domain SDPOL SequentialDifferentialPolynomial>>

@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}