/usr/share/axiom-20170501/src/algebra/POLUTIL.spad is in axiom-source 20170501-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 | )abbrev package POLUTIL RealPolynomialUtilitiesPackage
++ Author: Renaud Rioboo
++ Date Created: summer 1992
++ Description:
++ \axiomType{RealPolynomialUtilitiesPackage} provides common functions used
++ by interval coding.
RealPolynomialUtilitiesPackage(TheField,ThePols) : SIG == CODE where
TheField : Field
ThePols : UnivariatePolynomialCategory(TheField)
Z ==> Integer
N ==> NonNegativeInteger
P ==> ThePols
SIG ==> with
sylvesterSequence : (ThePols,ThePols) -> List ThePols
++ \axiom{sylvesterSequence(p,q)} is the negated remainder sequence
++ of p and q divided by the last computed term
sturmSequence : ThePols -> List ThePols
++ \axiom{sturmSequence(p) = sylvesterSequence(p,p')}
if TheField has OrderedRing then
boundOfCauchy : ThePols -> TheField
++ \axiom{boundOfCauchy(p)} bounds the roots of p
sturmVariationsOf : List TheField -> N
++ \axiom{sturmVariationsOf(l)} is the number of sign variations
++ in the list of numbers l,
++ note that the first term counts as a sign
lazyVariations : (List(TheField), Z, Z) -> N
++ \axiom{lazyVariations(l,s1,sn)} is the number of sign variations
++ in the list of non null numbers [s1::l]@sn,
CODE ==> add
sturmSequence(p) ==
sylvesterSequence(p,differentiate(p))
sylvesterSequence(p1,p2) ==
res : List(ThePols) := [p1]
while (p2 ^= 0) repeat
res := cons(p2 , res)
(p1 , p2) := (p2 , -(p1 rem p2))
if degree(p1) > 0
then
p1 := unitCanonical(p1)
res := [ term quo p1 for term in res ]
reverse! res
if TheField has OrderedRing
then
boundOfCauchy(p) ==
c :TheField := inv(leadingCoefficient(p))
l := [ c*term for term in rest(coefficients(p))]
null(l) => 1
1 + ("max" / [ abs(t) for t in l ])
sturmVariationsOf(l) ==
null(l) => error "POLUTIL: sturmVariationsOf: empty list !"
l1 := first(l)
-- first 0 counts as a sign
ll : List(TheField) := []
for term in rest(l) repeat
-- zeros don't count
if not(zero?(term)) then ll := cons(term,ll)
-- if l1 is not zero then ll = reverse(l)
null(ll) => error "POLUTIL: sturmVariationsOf: Bad sequence"
ln := first(ll)
ll := reverse(rest(ll))
-- if l1 is not zero then first(l) = first(ll)
-- if l1 is zero then first zero should count as a sign
zero?(l1) => 1 + lazyVariations(rest(ll),sign(first(ll)),sign(ln))
lazyVariations(ll, sign(l1), sign(ln))
lazyVariations(l,sl,sh) ==
zero?(sl) or zero?(sh) => error "POLUTIL: lazyVariations: zero sign!"
null(l) =>
if sl = sh then 0 else 1
null(rest(l)) =>
if zero?(first(l))
then error "POLUTIL: lazyVariations: zero sign!"
else
if sl = sh
then
if (sl = sign(first(l)))
then 0
else 2
-- in this case we save one test
else 1
s := sign(l.2)
lazyVariations([first(l)],sl,s) +
lazyVariations(rest(rest(l)),s,sh)
|