diff options
Diffstat (limited to 'src/algebra/rf.spad.pamphlet')
| -rw-r--r-- | src/algebra/rf.spad.pamphlet | 263 |
1 files changed, 263 insertions, 0 deletions
diff --git a/src/algebra/rf.spad.pamphlet b/src/algebra/rf.spad.pamphlet new file mode 100644 index 00000000..26220e4c --- /dev/null +++ b/src/algebra/rf.spad.pamphlet @@ -0,0 +1,263 @@ +\documentclass{article} +\usepackage{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 == + (den := denom f) ^= 1 => + numer f ^= 1 => "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 => + (numer f) = 1 => + (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] + (denom f) = 1 => [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 + ((den := denom f) = 1) => l +-- one? num => "failed" + num = 1 => "failed" + d := inv(den::F) + l case "failed" => [num::F, d] + concat_!(l::List(F), d) + + isPlus f == + denom f ^= 1 => "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} |