\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} <>= )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} <>= )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} <>= --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. @ <<*>>= <> <> <> @ \eject \begin{thebibliography}{99} \bibitem{1} nothing \end{thebibliography} \end{document}