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

\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{\$SPAD/src/algebra rf.spad}
\author{Manuel Bronstein}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{package POLYCATQ PolynomialCategoryQuotientFunctions}
<<package POLYCATQ PolynomialCategoryQuotientFunctions>>=
)abbrev package POLYCATQ PolynomialCategoryQuotientFunctions
++ Manipulations on polynomial quotients
++ Author: Manuel Bronstein
++ Date Created: March 1988
++ Date Last Updated: 9 July 1990
++ Description:
++   This package transforms multivariate polynomials or fractions into
++   univariate polynomials or fractions, and back.
++ Keywords: polynomial, fraction, transformation
PolynomialCategoryQuotientFunctions(E, V, R, P, F):
 Exports == Implementation where
  E: OrderedAbelianMonoidSup
  V: OrderedSet
  R: Ring
  P: PolynomialCategory(R, E, V)
  F: Field with
    coerce: P -> %
    numer : % -> P
    denom : % -> P

  UP  ==> SparseUnivariatePolynomial F
  RF  ==> Fraction UP

  Exports ==> with
    variables   : F -> List V
      ++ variables(f) returns the list of variables appearing
      ++ in the numerator or the denominator of f.
    mainVariable: F -> Union(V, "failed")
      ++ mainVariable(f) returns the highest variable appearing
      ++ in the numerator or the denominator of f, "failed" if
      ++ f has no variables.
    univariate  : (F, V) -> RF
      ++ univariate(f, v) returns f viewed as a univariate
      ++ rational function in v.
    multivariate: (RF, V) -> F
      ++ multivariate(f, v) applies both the numerator and
      ++ denominator of f to v.
    univariate  : (F, V, UP) -> UP
      ++ univariate(f, x, p) returns f viewed as a univariate
      ++ polynomial in x, using the side-condition \spad{p(x) = 0}.
    isPlus      : F -> Union(List F, "failed")
      ++ isPlus(p) returns [m1,...,mn] if \spad{p = m1 + ... + mn} and 
      ++ \spad{n > 1}, "failed" otherwise.
    isTimes     : F -> Union(List F, "failed")
      ++ isTimes(p) returns \spad{[a1,...,an]} if 
      ++ \spad{p = a1 ... an} and \spad{n > 1},
      ++ "failed" otherwise.
    isExpt      : F -> Union(Record(var:V, exponent:Integer), "failed")
      ++ isExpt(p) returns \spad{[x, n]} if \spad{p = x**n} and \spad{n <> 0},
      ++ "failed" otherwise.
    isPower     : F -> Union(Record(val:F, exponent:Integer), "failed")
      ++ isPower(p) returns \spad{[x, n]} if \spad{p = x**n} and \spad{n <> 0},
      ++ "failed" otherwise.

  Implementation ==> add
    P2UP: (P, V) -> UP

    univariate(f, x) == P2UP(numer f, x) / P2UP(denom f, x)

    univariate(f, x, modulus) ==
      (bc := extendedEuclidean(P2UP(denom f, x), modulus, 1))
             case "failed" => error "univariate: denominator is 0 mod p"
      (P2UP(numer f, x) * bc.coef1) rem modulus

    multivariate(f, x) ==
      v := x::P::F
      ((numer f) v) / ((denom f) v)

    mymerge:(List V,List V) ->List V 
    mymerge(l:List V,m:List V):List V==
         empty? l => m
         empty? m => l
         first l = first m => cons(first l,mymerge(rest l,rest m))
         first l > first m => cons(first l,mymerge(rest l,m))
         cons(first m,mymerge(l,rest m))

    variables f ==
      mymerge(variables numer f, variables denom f)

    isPower f ==
      not one?(den := denom f) =>
        not one? numer f => "failed"
        (ur := isExpt den) case "failed" => [den::F, -1]
        r := ur::Record(var:V, exponent:NonNegativeInteger)
        [r.var::P::F, - (r.exponent::Integer)]
      (ur := isExpt numer f) case "failed" => "failed"
      r := ur::Record(var:V, exponent:NonNegativeInteger)
      [r.var::P::F, r.exponent::Integer]

    isExpt f ==
      (ur := isExpt numer f) case "failed" =>
        one? numer f =>
          (ur := isExpt denom f) case "failed" => "failed"
          r := ur::Record(var:V, exponent:NonNegativeInteger)
          [r.var, - (r.exponent::Integer)]
        "failed"
      r := ur::Record(var:V, exponent:NonNegativeInteger)
      one? denom f => [r.var, r.exponent::Integer]
      "failed"

    isTimes f ==
      t := isTimes(num := numer f)
      l:Union(List F, "failed") :=
        t case "failed" => "failed"
        [x::F for x in t]
      one?(den := denom f) => l
      one? num => "failed"
      d := inv(den::F)
      l case "failed" => [num::F, d]
      concat!(l::List(F), d)

    isPlus f ==
      not one? denom f => "failed"
      (s := isPlus numer f) case "failed" => "failed"
      [x::F for x in s]

    mainVariable f ==
      a := mainVariable numer f
      (b := mainVariable denom f) case "failed" => a
      a case "failed" => b
      max(a::V, b::V)

    P2UP(p, x) ==
      map(#1::F,
          univariate(p, x))$SparseUnivariatePolynomialFunctions2(P, F)

@
\section{package RF RationalFunction}
<<package RF RationalFunction>>=
)abbrev package RF RationalFunction
++ Top-level manipulations of rational functions
++ Author: Manuel Bronstein
++ Date Created: 1987
++ Date Last Updated: 18 April 1991
++ Description:
++   Utilities that provide the same top-level manipulations on
++   fractions than on polynomials.
++ Keywords: polynomial, fraction
-- Do not make into a domain!
RationalFunction(R:IntegralDomain): Exports == Implementation where
  V  ==> Symbol
  P  ==> Polynomial R
  Q  ==> Fraction P
  QF ==> PolynomialCategoryQuotientFunctions(IndexedExponents Symbol,
                                                        Symbol, R, P, Q)

  Exports ==> with
    variables   : Q -> List V
      ++ variables(f) returns the list of variables appearing
      ++ in the numerator or the denominator of f.
    mainVariable: Q -> Union(V, "failed")
      ++ mainVariable(f) returns the highest variable appearing
      ++ in the numerator or the denominator of f, "failed" if
      ++ f has no variables.
    univariate  : (Q, V) -> Fraction SparseUnivariatePolynomial Q
      ++ univariate(f, v) returns f viewed as a univariate
      ++ rational function in v.
    multivariate: (Fraction SparseUnivariatePolynomial Q, V) -> Q
      ++ multivariate(f, v) applies both the numerator and
      ++ denominator of f to v.
    eval        : (Q, V, Q) -> Q
      ++ eval(f, v, g) returns f with v replaced by g.
    eval        : (Q, List V, List Q) -> Q
      ++ eval(f, [v1,...,vn], [g1,...,gn]) returns f with
      ++ each vi replaced by gi in parallel, i.e. vi's appearing
      ++ inside the gi's are not replaced.
    eval        : (Q, Equation Q) -> Q
      ++ eval(f, v = g) returns f with v replaced by g.
      ++ Error: if v is not a symbol.
    eval        : (Q, List Equation Q) -> Q
      ++ eval(f, [v1 = g1,...,vn = gn]) returns f with
      ++ each vi replaced by gi in parallel, i.e. vi's appearing
      ++ inside the gi's are not replaced.
      ++ Error: if any vi is not a symbol.
    coerce      : R -> Q
      ++ coerce(r) returns r viewed as a rational function over R.

  Implementation ==> add
    foo  : (List V, List Q, V) -> Q
    peval: (P, List V, List Q) -> Q

    coerce(r:R):Q            == r::P::Q
    variables f              == variables(f)$QF
    mainVariable f           == mainVariable(f)$QF
    univariate(f, x)         == univariate(f, x)$QF
    multivariate(f, x)       == multivariate(f, x)$QF
    eval(x:Q, s:V, y:Q)      == eval(x, [s], [y])
    eval(x:Q, eq:Equation Q) == eval(x, [eq])
    foo(ls, lv, x)           == match(ls, lv, x, x::Q)$ListToMap(V, Q)

    eval(x:Q, l:List Equation Q) ==
      eval(x, [retract(lhs eq)@V for eq in l]$List(V),
              [rhs eq for eq in l]$List(Q))

    eval(x:Q, ls:List V, lv:List Q) ==
      peval(numer x, ls, lv) / peval(denom x, ls, lv)

    peval(p, ls, lv) ==
      map(foo(ls, lv, #1), #1::Q,
          p)$PolynomialCategoryLifting(IndexedExponents V,V,R,P,Q)

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

<<package POLYCATQ PolynomialCategoryQuotientFunctions>>
<<package RF RationalFunction>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}