/usr/share/axiom-20170501/src/algebra/OREPCTO.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 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 | )abbrev package OREPCTO UnivariateSkewPolynomialCategoryOps
++ Author: Manuel Bronstein
++ Date Created: 1 February 1994
++ Date Last Updated: 1 February 1994
++ References:
++ Bron95 On radical solutions of linear ordinary differential equations
++ Abra01 On Solutions of Linear Functional Systems
++ Muld95 Primitives: Orepoly and Lodo
++ Description:
++ \spad{UnivariateSkewPolynomialCategoryOps} provides products and
++ divisions of univariate skew polynomials.
-- Putting those operations here rather than defaults in OREPCAT allows
-- OREPCAT to be defined independently of sigma and delta.
-- MB 2/94
UnivariateSkewPolynomialCategoryOps(R, C) : SIG == CODE where
R : Ring
C : UnivariateSkewPolynomialCategory R
N ==> NonNegativeInteger
MOR ==> Automorphism R
QUOREM ==> Record(quotient: C, remainder: C)
SIG ==> with
times: (C, C, MOR, R -> R) -> C
++ times(p, q, sigma, delta) returns \spad{p * q}.
++ \spad{\sigma} and \spad{\delta} are the maps to use.
apply: (C, R, R, MOR, R -> R) -> R
++ apply(p, c, m, sigma, delta) returns \spad{p(m)} where the action
++ is given by \spad{x m = c sigma(m) + delta(m)}.
if R has IntegralDomain then
monicLeftDivide: (C, C, MOR) -> QUOREM
++ monicLeftDivide(a, b, sigma) returns the pair \spad{[q,r]}
++ such that \spad{a = b*q + r} and the degree of \spad{r} is
++ less than the degree of \spad{b}.
++ \spad{b} must be monic.
++ This process is called ``left division''.
++ \spad{\sigma} is the morphism to use.
monicRightDivide: (C, C, MOR) -> QUOREM
++ monicRightDivide(a, b, sigma) returns the pair \spad{[q,r]}
++ such that \spad{a = q*b + r} and the degree of \spad{r} is
++ less than the degree of \spad{b}.
++ \spad{b} must be monic.
++ This process is called ``right division''.
++ \spad{\sigma} is the morphism to use.
if R has Field then
leftDivide: (C, C, MOR) -> QUOREM
++ leftDivide(a, b, sigma) returns the pair \spad{[q,r]} such
++ that \spad{a = b*q + r} and the degree of \spad{r} is
++ less than the degree of \spad{b}.
++ This process is called ``left division''.
++ \spad{\sigma} is the morphism to use.
rightDivide: (C, C, MOR) -> QUOREM
++ rightDivide(a, b, sigma) returns the pair \spad{[q,r]} such
++ that \spad{a = q*b + r} and the degree of \spad{r} is
++ less than the degree of \spad{b}.
++ This process is called ``right division''.
++ \spad{\sigma} is the morphism to use.
CODE ==> add
termPoly: (R, N, C, MOR, R -> R) -> C
localLeftDivide : (C, C, MOR, R) -> QUOREM
localRightDivide: (C, C, MOR, R) -> QUOREM
times(x, y, sigma, delta) ==
zero? y => 0
z:C := 0
while x ^= 0 repeat
z := z + termPoly(leadingCoefficient x, degree x, y, sigma, delta)
x := reductum x
z
termPoly(a, n, y, sigma, delta) ==
zero? y => 0
(u := subtractIfCan(n, 1)) case "failed" => a * y
n1 := u::N
z:C := 0
while y ^= 0 repeat
m := degree y
b := leadingCoefficient y
z := z + termPoly(a, n1, monomial(sigma b, m + 1), sigma, delta)
+ termPoly(a, n1, monomial(delta b, m), sigma, delta)
y := reductum y
z
apply(p, c, x, sigma, delta) ==
w:R := 0
xn:R := x
for i in 0..degree p repeat
w := w + coefficient(p, i) * xn
xn := c * sigma xn + delta xn
w
-- localLeftDivide(a, b) returns [q, r] such that a = q b + r
-- b1 is the inverse of the leadingCoefficient of b
localLeftDivide(a, b, sigma, b1) ==
zero? b => error "leftDivide: division by 0"
zero? a or
(n := subtractIfCan(degree(a),(m := degree b))) case "failed" =>
[0,a]
q := monomial((sigma**(-m))(b1 * leadingCoefficient a), n::N)
qr := localLeftDivide(a - b * q, b, sigma, b1)
[q + qr.quotient, qr.remainder]
-- localRightDivide(a, b) returns [q, r] such that a = q b + r
-- b1 is the inverse of the leadingCoefficient of b
localRightDivide(a, b, sigma, b1) ==
zero? b => error "rightDivide: division by 0"
zero? a or
(n := subtractIfCan(degree(a),(m := degree b))) case "failed" =>
[0,a]
q := monomial(leadingCoefficient(a) * (sigma**n) b1, n::N)
qr := localRightDivide(a - q * b, b, sigma, b1)
[q + qr.quotient, qr.remainder]
if R has IntegralDomain then
monicLeftDivide(a, b, sigma) ==
unit?(u := leadingCoefficient b) =>
localLeftDivide(a, b, sigma, recip(u)::R)
error "monicLeftDivide: divisor is not monic"
monicRightDivide(a, b, sigma) ==
unit?(u := leadingCoefficient b) =>
localRightDivide(a, b, sigma, recip(u)::R)
error "monicRightDivide: divisor is not monic"
if R has Field then
leftDivide(a, b, sigma) ==
localLeftDivide(a, b, sigma, inv leadingCoefficient b)
rightDivide(a, b, sigma) ==
localRightDivide(a, b, sigma, inv leadingCoefficient b)
|