From ab8cc85adde879fb963c94d15675783f2cf4b183 Mon Sep 17 00:00:00 2001 From: dos-reis Date: Tue, 14 Aug 2007 05:14:52 +0000 Subject: Initial population. --- src/algebra/funcpkgs.spad.pamphlet | 193 +++++++++++++++++++++++++++++++++++++ 1 file changed, 193 insertions(+) create mode 100644 src/algebra/funcpkgs.spad.pamphlet (limited to 'src/algebra/funcpkgs.spad.pamphlet') diff --git a/src/algebra/funcpkgs.spad.pamphlet b/src/algebra/funcpkgs.spad.pamphlet new file mode 100644 index 00000000..41f979ef --- /dev/null +++ b/src/algebra/funcpkgs.spad.pamphlet @@ -0,0 +1,193 @@ +\documentclass{article} +\usepackage{axiom} +\begin{document} +\title{\$SPAD/src/algebra funcpkgs.spad} +\author{Manuel Bronstein} +\maketitle +\begin{abstract} +\end{abstract} +\eject +\tableofcontents +\eject +\section{package FSUPFACT FunctionSpaceUnivariatePolynomialFactor} +<>= +)abbrev package FSUPFACT FunctionSpaceUnivariatePolynomialFactor +++ Used internally by IR2F +++ Author: Manuel Bronstein +++ Date Created: 12 May 1988 +++ Date Last Updated: 22 September 1993 +++ Keywords: function, space, polynomial, factoring +FunctionSpaceUnivariatePolynomialFactor(R, F, UP): + Exports == Implementation where + R : Join(IntegralDomain, OrderedSet, RetractableTo Integer) + F : FunctionSpace R + UP: UnivariatePolynomialCategory F + + Q ==> Fraction Integer + K ==> Kernel F + AN ==> AlgebraicNumber + PQ ==> SparseMultivariatePolynomial(Q, K) + PR ==> SparseMultivariatePolynomial(R, K) + UPQ ==> SparseUnivariatePolynomial Q + UPA ==> SparseUnivariatePolynomial AN + FR ==> Factored UP + FRQ ==> Factored UPQ + FRA ==> Factored UPA + + Exports ==> with + ffactor: UP -> FR + ++ ffactor(p) tries to factor a univariate polynomial p over F + qfactor: UP -> Union(FRQ, "failed") + ++ qfactor(p) tries to factor p over fractions of integers, + ++ returning "failed" if it cannot + UP2ifCan: UP -> Union(overq: UPQ, overan: UPA, failed: Boolean) + ++ UP2ifCan(x) should be local but conditional. + if F has RetractableTo AN then + anfactor: UP -> Union(FRA, "failed") + ++ anfactor(p) tries to factor p over algebraic numbers, + ++ returning "failed" if it cannot + + Implementation ==> add + import AlgFactor(UPA) + import RationalFactorize(UPQ) + + P2QifCan : PR -> Union(PQ, "failed") + UPQ2UP : (SparseUnivariatePolynomial PQ, F) -> UP + PQ2F : (PQ, F) -> F + ffactor0 : UP -> FR + + dummy := kernel(new()$Symbol)$K + + if F has RetractableTo AN then + UPAN2F: UPA -> UP + UPQ2AN: UPQ -> UPA + + UPAN2F p == + map(#1::F, p)$UnivariatePolynomialCategoryFunctions2(AN,UPA,F,UP) + + UPQ2AN p == + map(#1::AN, p)$UnivariatePolynomialCategoryFunctions2(Q,UPQ,AN,UPA) + + ffactor p == + (pq := anfactor p) case FRA => + map(UPAN2F, pq::FRA)$FactoredFunctions2(UPA, UP) + ffactor0 p + + anfactor p == + (q := UP2ifCan p) case overq => + map(UPQ2AN, factor(q.overq))$FactoredFunctions2(UPQ, UPA) + q case overan => factor(q.overan) + "failed" + + UP2ifCan p == + ansq := 0$UPQ ; ansa := 0$UPA + goforq? := true + while p ^= 0 repeat + if goforq? then + rq := retractIfCan(leadingCoefficient p)@Union(Q, "failed") + if rq case Q then + ansq := ansq + monomial(rq::Q, degree p) + ansa := ansa + monomial(rq::Q::AN, degree p) + else + goforq? := false + ra := retractIfCan(leadingCoefficient p)@Union(AN, "failed") + if ra case AN then ansa := ansa + monomial(ra::AN, degree p) + else return [true] + else + ra := retractIfCan(leadingCoefficient p)@Union(AN, "failed") + if ra case AN then ansa := ansa + monomial(ra::AN, degree p) + else return [true] + p := reductum p + goforq? => [ansq] + [ansa] + + else + UPQ2F: UPQ -> UP + + UPQ2F p == + map(#1::F, p)$UnivariatePolynomialCategoryFunctions2(Q,UPQ,F,UP) + + ffactor p == + (pq := qfactor p) case FRQ => + map(UPQ2F, pq::FRQ)$FactoredFunctions2(UPQ, UP) + ffactor0 p + + UP2ifCan p == + ansq := 0$UPQ + while p ^= 0 repeat + rq := retractIfCan(leadingCoefficient p)@Union(Q, "failed") + if rq case Q then ansq := ansq + monomial(rq::Q, degree p) + else return [true] + p := reductum p + [ansq] + + ffactor0 p == + smp := numer(ep := p(dummy::F)) + (q := P2QifCan smp) case "failed" => p::FR + map(UPQ2UP(univariate(#1, dummy), denom(ep)::F), factor(q::PQ + )$MRationalFactorize(IndexedExponents K, K, Integer, + PQ))$FactoredFunctions2(PQ, UP) + + UPQ2UP(p, d) == + map(PQ2F(#1, d), p)$UnivariatePolynomialCategoryFunctions2(PQ, + SparseUnivariatePolynomial PQ, F, UP) + + PQ2F(p, d) == + map(#1::F, #1::F, p)$PolynomialCategoryLifting(IndexedExponents K, + K, Q, PQ, F) / d + + qfactor p == + (q := UP2ifCan p) case overq => factor(q.overq) + "failed" + + P2QifCan p == + and/[retractIfCan(c::F)@Union(Q, "failed") case Q + for c in coefficients p] => + map(#1::PQ, retract(#1::F)@Q :: PQ, + p)$PolynomialCategoryLifting(IndexedExponents K,K,R,PR,PQ) + "failed" + +@ +\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} -- cgit v1.2.3