open-axiom repository from github
\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{src/algebra algfact.spad}
\author{Patrizia Gianni, Manuel Bronstein}
\maketitle
\begin{abstract}
\end{abstract}
\tableofcontents
\eject
\section{package IALGFACT InnerAlgFactor}
<<package IALGFACT InnerAlgFactor>>=
import Field
import UnivariatePolynomialCategory
import CharacteristicZero
import MonogenicAlgebra
import Factored
)abbrev package IALGFACT InnerAlgFactor
++ Factorisation in a simple algebraic extension
++ Author: Patrizia Gianni
++ Date Created: ???
++ Date Last Updated: 20 Jul 1988
++ 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
InnerAlgFactor(F, UP, AlExt, AlPol): Exports == Implementation where
F : Field
UP : UnivariatePolynomialCategory F
AlPol: UnivariatePolynomialCategory AlExt
AlExt : Join(Field, CharacteristicZero, MonogenicAlgebra(F,UP))
NUP ==> SparseUnivariatePolynomial UP
N ==> NonNegativeInteger
Z ==> Integer
FR ==> Factored UP
UPCF2 ==> UnivariatePolynomialCategoryFunctions2
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;
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, k, fact) ==
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, k, fact) ==
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, fact) ==
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 == resultant(convrt q, newp)
change q == map(coerce, q)$UPCF2(F,UP,AlExt,AlPol)
convrt q ==
swap(map(lift, q)$UPCF2(AlExt, AlPol,
UP, NUP))$CommuteUnivariatePolynomialCategory(F, UP, NUP)
@
\section{package SAEFACT SimpleAlgebraicExtensionAlgFactor}
<<package SAEFACT SimpleAlgebraicExtensionAlgFactor>>=
import UnivariatePolynomialCategory
import CharacteristicZero
import Field
import MonogenicAlgebra
import Fraction
import Integer
import Factored
)abbrev package SAEFACT SimpleAlgebraicExtensionAlgFactor
++ Factorisation in a simple algebraic extension;
++ Author: Patrizia Gianni
++ Date Created: ???
++ Date Last Updated: ???
++ 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
UP : UnivariatePolynomialCategory Fraction Integer
SAE : Join(Field, CharacteristicZero,
MonogenicAlgebra(Fraction Integer, UP))
UPA: UnivariatePolynomialCategory SAE
Exports ==> with
factor: UPA -> Factored UPA
++ factor(p) returns a prime factorisation of p.
Implementation ==> add
factor q ==
factor(q, factor$RationalFactorize(UP)
)$InnerAlgFactor(Fraction Integer, UP, SAE, UPA)
@
\section{package RFFACT RationalFunctionFactor}
<<package RFFACT RationalFunctionFactor>>=
import UnivariatePolynomialCategory
import Factored
import Polynomial
import Integer
)abbrev package RFFACT RationalFunctionFactor
++ Factorisation in UP FRAC POLY INT
++ Author: Patrizia Gianni
++ Date Created: ???
++ Date Last Updated: ???
++ Description:
++ Factorization of univariate polynomials with coefficients which
++ are rational functions with integer coefficients.
RationalFunctionFactor(UP): Exports == Implementation where
UP: UnivariatePolynomialCategory Fraction Polynomial Integer
SE ==> Symbol
P ==> Polynomial Integer
RF ==> Fraction P
UPCF2 ==> UnivariatePolynomialCategoryFunctions2
Exports ==> with
factor: UP -> Factored UP
++ factor(p) returns a prime factorisation of p.
Implementation ==> add
likuniv: (P, SE, P) -> UP
dummy := new()$SE
likuniv(p, x, d) ==
map(#1 / d, univariate(p, x))$UPCF2(P,SparseUnivariatePolynomial P,
RF, UP)
factor p ==
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)
@
\section{package SAERFFC SAERationalFunctionAlgFactor}
<<package SAERFFC SAERationalFunctionAlgFactor>>=
import UnivariatePolynomialCategory
import Field
import CharacteristicZero
import Polynomial
import Fraction
import Integer
)abbrev package SAERFFC SAERationalFunctionAlgFactor
++ Factorisation in UP SAE FRAC POLY INT
++ Author: Patrizia Gianni
++ Date Created: ???
++ Date Last Updated: ???
++ 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
UP : UnivariatePolynomialCategory Fraction Polynomial Integer
SAE : Join(Field, CharacteristicZero,
MonogenicAlgebra(Fraction Polynomial Integer, UP))
UPA: UnivariatePolynomialCategory SAE
Exports ==> with
factor: UPA -> Factored UPA
++ factor(p) returns a prime factorisation of p.
Implementation ==> add
factor q ==
factor(q, factor$RationalFunctionFactor(UP)
)$InnerAlgFactor(Fraction Polynomial Integer, UP, SAE, UPA)
@
\section{package ALGFACT AlgFactor}
<<package ALGFACT AlgFactor>>=
import UnivariatePolynomialCategory
import AlgebraicNumber
import Boolean
)abbrev package ALGFACT AlgFactor
++ Factorization of UP AN;
++ Author: Manuel Bronstein
++ Date Created: ???
++ Date Last Updated: ???
++ Description:
++ Factorization of univariate polynomials with coefficients in
++ \spadtype{AlgebraicNumber}.
AlgFactor(UP): Exports == Implementation where
UP: UnivariatePolynomialCategory AlgebraicNumber
N ==> NonNegativeInteger
Z ==> Integer
Q ==> Fraction Integer
AN ==> AlgebraicNumber
K ==> Kernel AN
UPQ ==> SparseUnivariatePolynomial Q
SUP ==> SparseUnivariatePolynomial AN
FR ==> Factored UP
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}.
Implementation ==> add
import PolynomialCategoryQuotientFunctions(IndexedExponents K,
K, Z, SparseMultivariatePolynomial(Z, K), AN)
UPCF2 ==> UnivariatePolynomialCategoryFunctions2
fact : (UP, List K) -> FR
ifactor : (SUP, List K) -> Factored SUP
extend : (UP, Z) -> FR
allk : List AN -> List K
downpoly: UP -> UPQ
liftpoly: UPQ -> UP
irred? : UP -> Boolean
allk l == removeDuplicates concat [kernels x for x in l]
liftpoly p == map(#1::AN, p)$UPCF2(Q, UPQ, AN, UP)
downpoly p == map(retract(#1)@Q, p)$UPCF2(AN, UP ,Q, UPQ)
ifactor(p,l) == (fact(p pretend UP, l)) pretend Factored(SUP)
factor p == fact(p, allk coefficients p)
factor(p, l) ==
fact(p, allk removeDuplicates concat(l, coefficients p))
split p ==
fp := factor p
unit(fp) *
_*/[extend(fc.factor, fc.exponent) for fc in factors fp]
extend(p, n) ==
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 ==
irred? p and irred?((p exquo
(monomial(1, 1)$UP - zeroOf(p pretend SUP)::UP))::UP)
irred? p ==
fp := factor p
one? numberOfFactors fp and one? nthExponent(fp, 1)
fact(p, l) ==
one? degree p => primeFactor(p, 1)
empty? l =>
dr := factor(downpoly p)$RationalFactorize(UPQ)
(liftpoly unit dr) *
_*/[primeFactor(liftpoly dc.factor,dc.exponent)
for dc in factors dr]
q := 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) *
_*/[primeFactor(map((lift(#1)$sae) newalpha,
fc.factor)$UPCF2(sae, ups, AN, UP),
fc.exponent) for fc in factors fr]
@
\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 IALGFACT InnerAlgFactor>>
<<package SAEFACT SimpleAlgebraicExtensionAlgFactor>>
<<package RFFACT RationalFunctionFactor>>
<<package SAERFFC SAERationalFunctionAlgFactor>>
<<package ALGFACT AlgFactor>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}