Initial population.

1 files changed, 490 insertions, 0 deletions

diff --git a/src/algebra/taylor.spad.pamphlet b/src/algebra/taylor.spad.pamphlet
new file mode 100644
index 00000000..7fa64c04
--- /dev/null
+++ b/src/algebra/taylor.spad.pamphlet
@@ -0,0 +1,490 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra taylor.spad}
+\author{Clifton J. Williamson}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{domain ITAYLOR InnerTaylorSeries}
+<<domain ITAYLOR InnerTaylorSeries>>=
+)abbrev domain ITAYLOR InnerTaylorSeries
+++ Author: Clifton J. Williamson
+++ Date Created: 21 December 1989
+++ Date Last Updated: 25 February 1989
+++ Basic Operations:
+++ Related Domains: UnivariateTaylorSeries(Coef,var,cen)
+++ Also See:
+++ AMS Classifications:
+++ Keywords: stream, dense Taylor series
+++ Examples:
+++ References:
+++ Description: Internal package for dense Taylor series.
+++ This is an internal Taylor series type in which Taylor series
+++ are represented by a \spadtype{Stream} of \spadtype{Ring} elements.
+++ For univariate series, the \spad{Stream} elements are the Taylor
+++ coefficients. For multivariate series, the \spad{n}th Stream element
+++ is a form of degree n in the power series variables.
+
+InnerTaylorSeries(Coef): Exports == Implementation where
+  Coef  : Ring
+  I   ==> Integer
+  NNI ==> NonNegativeInteger
+  ST  ==> Stream Coef
+  STT ==> StreamTaylorSeriesOperations Coef
+
+  Exports ==> Ring with
+    coefficients: % -> Stream Coef
+      ++\spad{coefficients(x)} returns a stream of ring elements.
+      ++ When x is a univariate series, this is a stream of Taylor
+      ++ coefficients. When x is a multivariate series, the
+      ++ \spad{n}th element of the stream is a form of
+      ++ degree n in the power series variables.
+    series: Stream Coef -> %
+      ++\spad{series(s)} creates a power series from a stream of
+      ++ ring elements.
+      ++ For univariate series types, the stream s should be a stream
+      ++ of Taylor coefficients. For multivariate series types, the
+      ++ stream s should be a stream of forms the \spad{n}th element
+      ++ of which is a
+      ++ form of degree n in the power series variables.
+    pole?: % -> Boolean
+      ++\spad{pole?(x)} tests if the series x has a pole.
+      ++ Note: this is false when x is a Taylor series.
+    order: % -> NNI
+      ++\spad{order(x)} returns the order of a power series x,
+      ++ i.e. the degree of the first non-zero term of the series.
+    order: (%,NNI) -> NNI
+      ++\spad{order(x,n)} returns the minimum of n and the order of x.
+    "*" : (Coef,%)->%
+      ++\spad{c*x} returns the product of c and the series x.
+    "*" : (%,Coef)->%
+      ++\spad{x*c} returns the product of c and the series x.
+    "*" : (%,Integer)->%
+      ++\spad{x*i} returns the product of integer i and the series x.
+    if Coef has IntegralDomain then IntegralDomain
+      --++ An IntegralDomain provides 'exquo'
+
+  Implementation ==> add
+
+    Rep := Stream Coef
+
+--% declarations
+    x,y: %
+
+--% definitions
+
+    -- In what follows, we will be calling operations on Streams
+    -- which are NOT defined in the package Stream.  Thus, it is
+    -- necessary to explicitly pass back and forth between Rep and %.
+    -- This will be done using the functions 'stream' and 'series'.
+
+    stream : % -> Stream Coef
+    stream x  == x pretend Stream(Coef)
+    series st == st pretend %
+
+    0 == coerce(0)$STT
+    1 == coerce(1)$STT
+
+    x = y ==
+      -- tests if two power series are equal
+      -- difference must be a finite stream of zeroes of length <= n + 1,
+      -- where n = $streamCount$Lisp
+      st : ST := stream(x - y)
+      n : I := _$streamCount$Lisp
+      for i in 0..n repeat
+        empty? st => return true
+        frst st ^= 0 => return false
+        st := rst st
+      empty? st
+
+    coefficients x == stream x
+
+    x + y            == stream(x) +$STT stream(y)
+    x - y            == stream(x) -$STT stream(y)
+    (x:%) * (y:%)    == stream(x) *$STT stream(y)
+    - x              == -$STT (stream x)
+    (i:I) * (x:%)    == (i::Coef) *$STT stream x
+    (x:%) * (i:I)    == stream(x) *$STT (i::Coef)
+    (c:Coef) * (x:%) == c *$STT stream x
+    (x:%) * (c:Coef) == stream(x) *$STT c
+
+    recip x ==
+      (rec := recip$STT stream x) case "failed" => "failed"
+      series(rec :: ST)
+
+    if Coef has IntegralDomain then
+
+      x exquo y ==
+        (quot := stream(x) exquo$STT stream(y)) case "failed" => "failed"
+        series(quot :: ST)
+
+    x:% ** n:NNI ==
+      n = 0 => 1
+      expt(x,n :: PositiveInteger)$RepeatedSquaring(%)
+
+    characteristic() == characteristic()$Coef
+    pole? x == false
+
+    iOrder: (ST,NNI,NNI) -> NNI
+    iOrder(st,n,n0) ==
+      (n = n0) or (empty? st) => n0
+      zero? frst st => iOrder(rst st,n + 1,n0)
+      n
+
+    order(x,n) == iOrder(stream x,0,n)
+
+    iOrder2: (ST,NNI) -> NNI
+    iOrder2(st,n) ==
+      empty? st => error "order: series has infinite order"
+      zero? frst st => iOrder2(rst st,n + 1)
+      n
+
+    order x == iOrder2(stream x,0)
+
+@
+\section{domain UTS UnivariateTaylorSeries}
+<<domain UTS UnivariateTaylorSeries>>=
+)abbrev domain UTS UnivariateTaylorSeries
+++ Author: Clifton J. Williamson
+++ Date Created: 21 December 1989
+++ Date Last Updated: 21 September 1993
+++ Basic Operations:
+++ Related Domains: UnivariateLaurentSeries(Coef,var,cen), UnivariatePuiseuxSeries(Coef,var,cen)
+++ Also See:
+++ AMS Classifications:
+++ Keywords: dense, Taylor series
+++ Examples:
+++ References:
+++ Description: Dense Taylor series in one variable
+++ \spadtype{UnivariateTaylorSeries} is a domain representing Taylor
+++ series in
+++ one variable with coefficients in an arbitrary ring.  The parameters
+++ of the type specify the coefficient ring, the power series variable,
+++ and the center of the power series expansion.  For example,
+++ \spadtype{UnivariateTaylorSeries}(Integer,x,3) represents
+++ Taylor series in
+++ \spad{(x - 3)} with \spadtype{Integer} coefficients.
+UnivariateTaylorSeries(Coef,var,cen): Exports == Implementation where
+  Coef :  Ring
+  var  :  Symbol
+  cen  :  Coef
+  I    ==> Integer
+  NNI  ==> NonNegativeInteger
+  P    ==> Polynomial Coef
+  RN   ==> Fraction Integer
+  ST   ==> Stream
+  STT  ==> StreamTaylorSeriesOperations Coef
+  TERM ==> Record(k:NNI,c:Coef)
+  UP   ==> UnivariatePolynomial(var,Coef)
+  Exports ==> UnivariateTaylorSeriesCategory(Coef) with
+    coerce: UP -> %
+      ++\spad{coerce(p)} converts a univariate polynomial p in the variable
+      ++\spad{var} to a univariate Taylor series in \spad{var}.
+    univariatePolynomial: (%,NNI) -> UP
+      ++\spad{univariatePolynomial(f,k)} returns a univariate polynomial
+      ++ consisting of the sum of all terms of f of degree \spad{<= k}.
+    coerce: Variable(var) -> %
+      ++\spad{coerce(var)} converts the series variable \spad{var} into a
+      ++ Taylor series.
+    differentiate: (%,Variable(var)) -> %
+      ++ \spad{differentiate(f(x),x)} computes the derivative of
+      ++ \spad{f(x)} with respect to \spad{x}.
+    lagrange: % -> %
+      ++\spad{lagrange(g(x))} produces the Taylor series for \spad{f(x)}
+      ++ where \spad{f(x)} is implicitly defined as \spad{f(x) = x*g(f(x))}.
+    lambert: % -> %
+      ++\spad{lambert(f(x))} returns \spad{f(x) + f(x^2) + f(x^3) + ...}.
+      ++ This function is used for computing infinite products.
+      ++ \spad{f(x)} should have zero constant coefficient.
+      ++ If \spad{f(x)} is a Taylor series with constant term 1, then
+      ++ \spad{product(n = 1..infinity,f(x^n)) = exp(log(lambert(f(x))))}.
+    oddlambert: % -> %
+      ++\spad{oddlambert(f(x))} returns \spad{f(x) + f(x^3) + f(x^5) + ...}.
+      ++ \spad{f(x)} should have a zero constant coefficient.
+      ++ This function is used for computing infinite products.
+      ++ If \spad{f(x)} is a Taylor series with constant term 1, then
+      ++ \spad{product(n=1..infinity,f(x^(2*n-1)))=exp(log(oddlambert(f(x))))}.
+    evenlambert: % -> %
+      ++\spad{evenlambert(f(x))} returns \spad{f(x^2) + f(x^4) + f(x^6) + ...}.
+      ++ \spad{f(x)} should have a zero constant coefficient.
+      ++ This function is used for computing infinite products.
+      ++ If \spad{f(x)} is a Taylor series with constant term 1, then
+      ++ \spad{product(n=1..infinity,f(x^(2*n))) = exp(log(evenlambert(f(x))))}.
+    generalLambert: (%,I,I) -> %
+      ++\spad{generalLambert(f(x),a,d)} returns \spad{f(x^a) + f(x^(a + d)) +
+      ++ f(x^(a + 2 d)) + ... }. \spad{f(x)} should have zero constant
+      ++ coefficient and \spad{a} and d should be positive.
+    revert: % -> %
+      ++ \spad{revert(f(x))} returns a Taylor series \spad{g(x)} such that
+      ++ \spad{f(g(x)) = g(f(x)) = x}. Series \spad{f(x)} should have constant
+      ++ coefficient 0 and 1st order coefficient 1.
+    multisect: (I,I,%) -> %
+      ++\spad{multisect(a,b,f(x))} selects the coefficients of
+      ++ \spad{x^((a+b)*n+a)}, and changes this monomial to \spad{x^n}.
+    invmultisect: (I,I,%) -> %
+      ++\spad{invmultisect(a,b,f(x))} substitutes \spad{x^((a+b)*n)}
+      ++ for \spad{x^n} and multiples by \spad{x^b}.
+    if Coef has Algebra Fraction Integer then
+      integrate: (%,Variable(var)) -> %
+        ++ \spad{integrate(f(x),x)} returns an anti-derivative of the power
+        ++ series \spad{f(x)} with constant coefficient 0.
+        ++ We may integrate a series when we can divide coefficients
+        ++ by integers.
+
+  Implementation ==> InnerTaylorSeries(Coef) add
+
+    Rep := Stream Coef
+
+--% creation and destruction of series
+
+    stream: % -> Stream Coef
+    stream x  == x pretend Stream(Coef)
+
+    coerce(v:Variable(var)) ==
+      zero? cen => monomial(1,1)
+      monomial(1,1) + monomial(cen,0)
+
+    coerce(n:I)    == n :: Coef :: %
+    coerce(r:Coef) == coerce(r)$STT
+    monomial(c,n)  == monom(c,n)$STT
+
+    getExpon: TERM -> NNI
+    getExpon term == term.k
+    getCoef: TERM -> Coef
+    getCoef term == term.c
+    rec: (NNI,Coef) -> TERM
+    rec(expon,coef) == [expon,coef]
+
+    recs: (ST Coef,NNI) -> ST TERM
+    recs(st,n) == delay$ST(TERM)
+      empty? st => empty()
+      zero? (coef := frst st) => recs(rst st,n + 1)
+      concat(rec(n,coef),recs(rst st,n + 1))
+
+    terms x == recs(stream x,0)
+
+    recsToCoefs: (ST TERM,NNI) -> ST Coef
+    recsToCoefs(st,n) == delay
+      empty? st => empty()
+      term := frst st; expon := getExpon term
+      n = expon => concat(getCoef term,recsToCoefs(rst st,n + 1))
+      concat(0,recsToCoefs(st,n + 1))
+
+    series(st: ST TERM) == recsToCoefs(st,0)
+
+    stToPoly: (ST Coef,P,NNI,NNI) -> P
+    stToPoly(st,term,n,n0) ==
+      (n > n0) or (empty? st) => 0
+      frst(st) * term ** n + stToPoly(rst st,term,n + 1,n0)
+
+    polynomial(x,n) == stToPoly(stream x,(var :: P) - (cen :: P),0,n)
+
+    polynomial(x,n1,n2) ==
+      if n1 > n2 then (n1,n2) := (n2,n1)
+      stToPoly(rest(stream x,n1),(var :: P) - (cen :: P),n1,n2)
+
+    stToUPoly: (ST Coef,UP,NNI,NNI) -> UP
+    stToUPoly(st,term,n,n0) ==
+      (n > n0) or (empty? st) => 0
+      frst(st) * term ** n + stToUPoly(rst st,term,n + 1,n0)
+
+    univariatePolynomial(x,n) ==
+      stToUPoly(stream x,monomial(1,1)$UP - monomial(cen,0)$UP,0,n)
+
+    coerce(p:UP) ==
+      zero? p => 0
+      if not zero? cen then
+        p := p(monomial(1,1)$UP + monomial(cen,0)$UP)
+      st : ST Coef := empty()
+      oldDeg : NNI := degree(p) + 1
+      while not zero? p repeat
+        deg := degree p
+        delta := (oldDeg - deg - 1) :: NNI
+        for i in 1..delta repeat st := concat(0$Coef,st)
+        st := concat(leadingCoefficient p,st)
+        oldDeg := deg; p := reductum p
+      for i in 1..oldDeg repeat st := concat(0$Coef,st)
+      st
+
+    if Coef has coerce: Symbol -> Coef then
+      if Coef has "**": (Coef,NNI) -> Coef then
+
+        stToCoef: (ST Coef,Coef,NNI,NNI) -> Coef
+        stToCoef(st,term,n,n0) ==
+          (n > n0) or (empty? st) => 0
+          frst(st) * term ** n + stToCoef(rst st,term,n + 1,n0)
+
+        approximate(x,n) ==
+          stToCoef(stream x,(var :: Coef) - cen,0,n)
+
+--% values
+
+    variable x == var
+    center   s == cen
+
+    coefficient(x,n) ==
+       -- Cannot use elt!  Should return 0 if stream doesn't have it.
+       u := stream x
+       while not empty? u and n > 0 repeat
+         u := rst u
+         n := (n - 1) :: NNI
+       empty? u or n ^= 0 => 0
+       frst u
+
+    elt(x:%,n:NNI) == coefficient(x,n)
+
+--% functions
+
+    map(f,x) == map(f,x)$Rep
+    eval(x:%,r:Coef) == eval(stream x,r-cen)$STT
+    differentiate x == deriv(stream x)$STT
+    differentiate(x:%,v:Variable(var)) == differentiate x
+    if Coef has PartialDifferentialRing(Symbol) then
+      differentiate(x:%,s:Symbol) ==
+        (s = variable(x)) => differentiate x
+        map(differentiate(#1,s),x) - differentiate(center x,s)*differentiate(x)
+    multiplyCoefficients(f,x) == gderiv(f,stream x)$STT
+    lagrange x == lagrange(stream x)$STT
+    lambert x == lambert(stream x)$STT
+    oddlambert x == oddlambert(stream x)$STT
+    evenlambert x == evenlambert(stream x)$STT
+    generalLambert(x:%,a:I,d:I) == generalLambert(stream x,a,d)$STT
+    extend(x,n) == extend(x,n+1)$Rep
+    complete x == complete(x)$Rep
+    truncate(x,n) == first(stream x,n + 1)$Rep
+    truncate(x,n1,n2) ==
+      if n2 < n1 then (n1,n2) := (n2,n1)
+      m := (n2 - n1) :: NNI
+      st := first(rest(stream x,n1)$Rep,m + 1)$Rep
+      for i in 1..n1 repeat st := concat(0$Coef,st)
+      st
+    elt(x:%,y:%) == compose(stream x,stream y)$STT
+    revert x == revert(stream x)$STT
+    multisect(a,b,x) == multisect(a,b,stream x)$STT
+    invmultisect(a,b,x) == invmultisect(a,b,stream x)$STT
+    multiplyExponents(x,n) == invmultisect(n,0,x)
+    quoByVar x == (empty? x => 0; rst x)
+    if Coef has IntegralDomain then
+      unit? x == unit? coefficient(x,0)
+    if Coef has Field then
+      if Coef is RN then
+        (x:%) ** (s:Coef) == powern(s,stream x)$STT
+      else
+        (x:%) ** (s:Coef) == power(s,stream x)$STT
+
+    if Coef has Algebra Fraction Integer then
+      coerce(r:RN) == r :: Coef :: %
+
+      integrate x == integrate(0,stream x)$STT
+      integrate(x:%,v:Variable(var)) == integrate x
+
+      if Coef has integrate: (Coef,Symbol) -> Coef and _
+         Coef has variables: Coef -> List Symbol then
+        integrate(x:%,s:Symbol) ==
+          (s = variable(x)) => integrate x
+          not entry?(s,variables center x) => map(integrate(#1,s),x)
+          error "integrate: center is a function of variable of integration"
+
+      if Coef has TranscendentalFunctionCategory and _
+	 Coef has PrimitiveFunctionCategory and _
+         Coef has AlgebraicallyClosedFunctionSpace Integer then
+
+        integrateWithOneAnswer: (Coef,Symbol) -> Coef
+        integrateWithOneAnswer(f,s) ==
+          res := integrate(f,s)$FunctionSpaceIntegration(I,Coef)
+          res case Coef => res :: Coef
+          first(res :: List Coef)
+
+        integrate(x:%,s:Symbol) ==
+          (s = variable(x)) => integrate x
+          not entry?(s,variables center x) =>
+            map(integrateWithOneAnswer(#1,s),x)
+          error "integrate: center is a function of variable of integration"
+
+--% OutputForms
+--  We use the default coerce: % -> OutputForm in UTSCAT&
+
+@
+\section{package UTS2 UnivariateTaylorSeriesFunctions2}
+<<package UTS2 UnivariateTaylorSeriesFunctions2>>=
+)abbrev package UTS2 UnivariateTaylorSeriesFunctions2
+++ Author: Clifton J. Williamson
+++ Date Created: 9 February 1990
+++ Date Last Updated: 9 February 1990
+++ Basic Operations:
+++ Related Domains: UnivariateTaylorSeries(Coef1,var,cen)
+++ Also See:
+++ AMS Classifications:
+++ Keywords: Taylor series, map
+++ Examples:
+++ References:
+++ Description: Mapping package for univariate Taylor series.
+++   This package allows one to apply a function to the coefficients of
+++   a univariate Taylor series.
+UnivariateTaylorSeriesFunctions2(Coef1,Coef2,UTS1,UTS2):_
+ Exports == Implementation where
+  Coef1 : Ring
+  Coef2 : Ring
+  UTS1  : UnivariateTaylorSeriesCategory Coef1
+  UTS2  : UnivariateTaylorSeriesCategory Coef2
+  ST2 ==> StreamFunctions2(Coef1,Coef2)
+
+  Exports ==> with
+    map: (Coef1 -> Coef2,UTS1) -> UTS2
+      ++\spad{map(f,g(x))} applies the map f to the coefficients of
+      ++ the Taylor series \spad{g(x)}.
+
+  Implementation ==> add
+
+    map(f,uts) == series map(f,coefficients uts)$ST2
+
+@
+\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 ITAYLOR InnerTaylorSeries>>
+<<domain UTS UnivariateTaylorSeries>>
+<<package UTS2 UnivariateTaylorSeriesFunctions2>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}