\documentclass{article} \usepackage{open-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, 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}