--* From postmaster%watson.vnet.ibm.com@yktvmv.watson.ibm.com Tue May 31 13:50:06 1994 --* Received: from yktvmv-ob.watson.ibm.com by asharp.watson.ibm.com (AIX 3.2/UCB 5.64/930311) --* id AA18963; Tue, 31 May 1994 13:50:06 -0400 --* Received: from watson.vnet.ibm.com by yktvmv.watson.ibm.com (IBM VM SMTP V2R3) --* with BSMTP id 2637; Tue, 31 May 94 13:50:00 EDT --* Received: from YKTVMV by watson.vnet.ibm.com with "VAGENT.V1.0" --* id --* for asbugs@watson; Tue, 31 May 94 13:38:04 -0400 --* Received: from YKTVMV by watson.vnet.ibm.com with "VAGENT.V1.0" --* id 3047; Tue, 31 May 1994 13:38:02 EDT --* Received: from daly by yktvmv.watson.ibm.com (IBM VM SMTP V2R3) with TCP; --* Tue, 31 May 94 13:38:01 EDT --* Received: by daly (AIX 3.2/UCB 5.64/4.03) --* id AA18896; Tue, 31 May 1994 12:42:02 -0500 --* Date: Tue, 31 May 1994 12:42:02 -0500 --* From: root@daly.watson.ibm.com --* Message-Id: <9405311742.AA18896@daly> --* To: asbugs@watson.ibm.com --* Subject: [3] dependent types within parameter lists fails [algfact.as][35.3] --@ Fixed by: SSD Fri Jun 3 10:19:14 EDT 1994 --@ Tested by: none --@ Summary: Not a bug. Default declarations only give types. They do not introduce meanings for identifiers. Put the dependent types in the parameter list. --Copyright The Numerical Algorithms Group Limited 1991. #include "axiom.as" --)abb package IALGFACT InnerAlgFactor --)abb package SAEFACT SimpleAlgebraicExtensionAlgFactor --)abb package RFFACT RationalFunctionFactor --)abb package SAERFFC SAERationalFunctionAlgFactor --)abb package ALGFACT AlgFactor +++ Factorisation in a simple algebraic extension; +++ Author: Patrizia Gianni +++ Date Created: ??? +++ Date Last Updated: May 25, 1994 asharp conversion by tim daly +++ Description: +++ Factorization of univariate polynomials with coefficients in an +++ algebraic extension of a field over which we can factor UP's; +++ Keywords: factorization, algebraic extension, univariate polynomial UPCF2 ==> UnivariatePolynomialCategoryFunctions2; InnerAlgFactor(F, UP, AlExt, AlPol): Exports == Implementation where {default F : Field; default UP : UnivariatePolynomialCategory F; default AlExt : Join(Field, CharacteristicZero, MonogenicAlgebra(F,UP)); default AlPol: UnivariatePolynomialCategory AlExt; NUP ==> SparseUnivariatePolynomial UP; import from NUP; N ==> NonNegativeInteger; import from N; Z ==> Integer; import from Z; FR ==> Factored UP; import from FR; Exports ==> with {factor: (AlPol, UP -> FR) -> Factored AlPol; ++ factor(p, f) returns a prime factorisation of p; ++ f is a factorisation map for elements of UP; } -- Exports Implementation ==> add {pnorm : AlPol -> UP; convrt : AlPol -> NUP; change : UP -> AlPol; perturbfactor: (AlPol, Z, UP -> FR) -> List AlPol; irrfactor : (AlPol, Z, UP -> FR) -> List AlPol; perturbfactor(f:AlPol, k:Z, fact:(UP->FR)):List(AlPol) == {pol := monomial(1$AlExt,1)- monomial(reduce monomial(k::F,1)$UP ,0); newf := elt(f, pol); lsols := irrfactor(newf, k, fact); pol := monomial(1, 1) + monomial(reduce monomial(k::F,1)$UP,0); [elt(pp, pol) for pp in lsols]} --- factorize the square-free parts of f --- irrfactor(f:AlPol, k:Z, fact:(UP->FR)):List(AlPol) == {degree(f) =$N 1 => [f]; newf := f; nn := pnorm f; --newval:RN:=1; --pert:=false; --if ^ SqFr? nn then -- {pert:=true; -- newterm:=perturb(f); -- newf:=newterm.ppol; -- newval:=newterm.pval; -- nn:=newterm.nnorm} listfact := factors fact nn; #listfact =$N 1 => {first(listfact).exponent =$Z 1 => [f]; perturbfactor(f, k + 1, fact)} listerm:List(AlPol):= []; for pelt in listfact repeat {g := gcd(change(pelt.factor), newf); newf := (newf exquo g)::AlPol; listerm := {pelt.exponent =$Z 1 => cons(g, listerm); append(perturbfactor(g, k + 1, fact), listerm)}} listerm} factor(f:AlPol, fact:(UP->FR)):Factored(AlPol) == {sqf := squareFree f; unit(sqf) * _*/[_*/[primeFactor(pol, sqterm.exponent) for pol in irrfactor(sqterm.factor, 0, fact)] for sqterm in factors sqf]} p := definingPolynomial()$AlExt; newp := map(#1::UP, p)$UPCF2(F, UP, UP, NUP); pnorm(q:Alpol):UP == {resultant(convrt q, newp)} change(q:UP):AlPol == {map(coerce, q)$UPCF2(F,UP,AlExt,AlPol)} convrt(q:AlPol):NUP == {swap(map(lift, q)$UPCF2(AlExt, AlPol, UP, NUP))$CommuteUnivariatePolynomialCategory(F, UP, NUP)} } -- Implementation } -- InnerAlgFactor +++ Factorisation in a simple algebraic extension; +++ Author: Patrizia Gianni +++ Date Created: ??? +++ Date Last Updated: May 25, 1994 asharp conversion by tim daly +++ Description: +++ Factorization of univariate polynomials with coefficients in an +++ algebraic extension of the rational numbers (\spadtype{Fraction Integer}). +++ Keywords: factorization, algebraic extension, univariate polynomial SimpleAlgebraicExtensionAlgFactor(UP,SAE,UPA):Exports==Implementation where {default UP : UnivariatePolynomialCategory Fraction Integer; default SAE : Join(Field, CharacteristicZero, MonogenicAlgebra(Fraction Integer, UP)); default UPA: UnivariatePolynomialCategory SAE; Exports ==> with {factor: UPA -> Factored UPA; ++ factor(p) returns a prime factorisation of p. } -- Exports Implementation ==> add {factor(q:UPA):Factored(UPA) == {factor(q, factor$RationalFactorize(UP) )$InnerAlgFactor(Fraction Integer, UP, SAE, UPA)} } -- Implementation } -- SimpleAlgebraicExtensionAlgFactor +++ Factorisation in UP FRAC POLY INT +++ Author: Patrizia Gianni +++ Date Created: ??? +++ Date Last Updated: May 25, 1994 asharp conversion by tim daly +++ Description: +++ Factorization of univariate polynomials with coefficients which +++ are rational functions with integer coefficients. RationalFunctionFactor(UP): Exports == Implementation where {default UP: UnivariatePolynomialCategory Fraction Polynomial Integer; SE ==> Symbol; import from SE; P ==> Polynomial Integer; import from P; RF ==> Fraction P; import from RF; Exports ==> with {factor: UP -> Factored UP; ++ factor(p) returns a prime factorisation of p. } -- Exports Implementation ==> add {likuniv: (P, SE, P) -> UP; dummy := new()$SE; likuniv(p:P, x:SE, d:P):UP == {map(#1 / d, univariate(p, x))$UPCF2(P,SparseUnivariatePolynomial P, RF, UP)} factor(p:UP):Factored(UP) == {d := denom(q := elt(p,dummy::P :: RF)); map(likuniv(#1,dummy,d), factor(numer q)$MultivariateFactorize(SE, IndexedExponents SE,Integer,P))$FactoredFunctions2(P, UP)} } -- Implementation } -- RationalFunctionFactor +++ Factorisation in UP SAE FRAC POLY INT +++ Author: Patrizia Gianni +++ Date Created: ??? +++ Date Last Updated: May 25, 1994 asharp conversion by tim daly +++ Description: +++ Factorization of univariate polynomials with coefficients in an +++ algebraic extension of \spadtype{Fraction Polynomial Integer}. +++ Keywords: factorization, algebraic extension, univariate polynomial SAERationalFunctionAlgFactor(UP, SAE, UPA): Exports == Implementation where {default UP : UnivariatePolynomialCategory Fraction Polynomial Integer; default SAE : Join(Field, CharacteristicZero, MonogenicAlgebra(Fraction Polynomial Integer, UP)); default UPA: UnivariatePolynomialCategory SAE; Exports ==> with {factor: UPA -> Factored UPA; ++ factor(p) returns a prime factorisation of p. } -- Exports Implementation ==> add {factor(q:UPA):Factored(UPA) == {factor(q, factor$RationalFunctionFactor(UP) )$InnerAlgFactor(Fraction Polynomial Integer, UP, SAE, UPA)} } -- Implementation } -- SAERationalFunctionAlgFactor +++ Factorization of UP AN; +++ Author: Manuel Bronstein +++ Date Created: ??? +++ Date Last Updated: May 25, 1994 asharp conversion by tim daly< +++ Description: +++ Factorization of univariate polynomials with coefficients in +++ \spadtype{AlgebraicNumber}. AlgFactor(UP): Exports == Implementation where {default UP: UnivariatePolynomialCategory AlgebraicNumber; N ==> NonNegativeInteger; import from N; Z ==> Integer; import from Z; Q ==> Fraction Integer; import from Q; AN ==> AlgebraicNumber; import from AN; K ==> Kernel AN; import from K; UPQ ==> SparseUnivariatePolynomial Q; import from UPQ; SUP ==> SparseUnivariatePolynomial AN; import from SUP; FR ==> Factored UP; import from FR; Exports ==> with {factor: (UP, List AN) -> FR; ++ factor(p, [a1,...,an]) returns a prime factorisation of p ++ over the field generated by its coefficients and a1,...,an. factor: UP -> FR; ++ factor(p) returns a prime factorisation of p ++ over the field generated by its coefficients. split : UP -> FR; ++ split(p) returns a prime factorisation of p ++ over its splitting field. doublyTransitive?: UP -> Boolean; ++ doublyTransitive?(p) is true if p is irreducible over ++ over the field K generated by its coefficients, and ++ if \spad{p(X) / (X - a)} is irreducible over ++ \spad{K(a)} where \spad{p(a) = 0}. } -- Exports Implementation ==> add {import from PolynomialCategoryQuotientFunctions(IndexedExponents K, K, Z, SparseMultivariatePolynomial(Z, K), AN); allk : List AN -> List K; liftpoly: UPQ -> UP; downpoly: UP -> UPQ; ifactor : (SUP, List K) -> Factored SUP; xtend : (UP, Z) -> FR; irred? : UP -> Boolean; fact : (UP, List K) -> FR; allk(l:List(AN)):List(K) == {removeDuplicates concat [kernels x for x in l]} liftpoly(p:UPQ):UP == {map(#1::AN, p)$UPCF2(Q, UPQ, AN, UP)} downpoly(p:UP):UPQ == {map(retract(#1)@Q, p)$UPCF2(AN, UP ,Q, UPQ)} ifactor(p:SUP,l:List(K)):Factored(SUP) == {(fact(p pretend UP, l)) pretend Factored(SUP)} factor(p:UP):FR == {fact(p, allk coefficients p)} factor(p:UP, l:List(AN)):FR == {fact(p, allk removeDuplicates concat(l, coefficients p))} split(p:UP):FR == {fp := factor p; unit(fp) * reduce(*,[xtend(fc.factor, fc.exponent) for fc in factors fp])} xtend(p:UP, n:Z):FR == {one? degree p => primeFactor(p, n); q := monomial(1, 1)$UP - zeroOf(p pretend SUP)::UP; primeFactor(q, n) * split((p exquo q)::UP) ** (n::N)} doublyTransitive?(p:UP):Boolean == {irred? p and irred?((p exquo (monomial(1, 1)$UP - zeroOf(p pretend SUP)::UP))::UP)} irred?(p:UP):Boolean == {fp := factor p; one? numberOfFactors fp and one? nthExponent(fp, 1)} fact(p:UP, l:List(K)):FR == {one? degree p => primeFactor(p, 1); empty? l => {dr := factor(downpoly p)$RationalFactorize(UPQ); (liftpoly unit dr) * reduce(*,[primeFactor(liftpoly dc.factor,dc.exponent) for dc in factors dr])} q:AN == minPoly(alpha := "max"/l)$AN; newl := remove(alpha = #1, l); sae ==> SimpleAlgebraicExtension(AN, SUP, q); ups ==> SparseUnivariatePolynomial sae; fr := factor(map(reduce univariate(#1, alpha, q), p)$UPCF2(AN, UP, sae, ups), ifactor(#1, newl))$InnerAlgFactor(AN, SUP, sae, ups); newalpha := alpha::AN; map((lift(#1)$sae) newalpha, unit fr)$UPCF2(sae, ups, AN, UP) * reduce(*,[primeFactor(map((lift(#1)$sae) newalpha, fc.factor)$UPCF2(sae, ups, AN, UP), fc.exponent) for fc in factors fr])} } -- Implementation } -- AlgFactor