Révision 77
| pobysoPythonSage/src/sageSLZ/sagePolynomialOperations.sage (revision 77) | ||
|---|---|---|
| 1 | 1 |
load "/home/storres/recherche/arithmetique/pobysoPythonSage/src/sageSLZ/sageMatrixOperations.sage" |
| 2 | 2 |
|
| 3 |
def spo_polynomial_to_matrix(p, pRing, alpha, N, columnWidth=0): |
|
| 3 |
def spo_polynomial_to_matrix(p, pRing, alpha, N, columnsWidth=0):
|
|
| 4 | 4 |
""" |
| 5 | 5 |
From a (bivariate) polynomial and some other parameters build a matrix |
| 6 | 6 |
to be reduced by fpLLL. |
| ... | ... | |
| 11 | 11 |
N: |
| 12 | 12 |
|
| 13 | 13 |
""" |
| 14 |
knownMonomials = [] |
|
| 15 |
protoMatrixRows = [] |
|
| 14 | 16 |
pVariables = p.variables() |
| 15 | 17 |
iVariable = pVariables[0] |
| 16 | 18 |
tVariable = pVariables[1] |
| ... | ... | |
| 26 | 28 |
# in, those in t necessary to be able to introduce |
| 27 | 29 |
# p. We arbitrary choose to introduce the highest degree monomial in i |
| 28 | 30 |
# with p. We also introduce all the mixed i^k * t^l monomials with |
| 29 |
# k < p.degree(i) and l <= p.degree(t) |
|
| 31 |
# k < p.degree(i) and l <= p.degree(t). |
|
| 32 |
# Mixed terms introduction is necessary before we start "i shifts" in |
|
| 33 |
# the next iteration. |
|
| 30 | 34 |
if pPower == 0: |
| 31 | 35 |
# iter1: power of i |
| 32 | 36 |
# Notice how i^pIdegree is excluded. |
| 33 | 37 |
for iPower in xrange(0, pIdegree): |
| 34 | 38 |
# iter5: power of t. |
| 35 | 39 |
for tPower in xrange(0, pTdegree + 1): |
| 36 |
if columnWidth != 0: |
|
| 40 |
if columnsWidth != 0:
|
|
| 37 | 41 |
print "->", spo_expression_as_string(iPower, |
| 38 | 42 |
tPower, |
| 39 | 43 |
pPower, |
| ... | ... | |
| 46 | 50 |
polynomialAtPower |
| 47 | 51 |
pMonomials = currentPolynomial.monomials() |
| 48 | 52 |
pCoefficients = currentPolynomial.coefficients() |
| 49 |
spo_add_polynomial_coeffs_to_matrix(pMonomials, pCoefficients, knownMonomials, protoMatrixRows, monomialLengthChars) |
|
| 53 |
spo_add_polynomial_coeffs_to_matrix(pMonomials, |
|
| 54 |
pCoefficients, |
|
| 55 |
knownMonomials, |
|
| 56 |
protoMatrixRows, |
|
| 57 |
columnsWidth) |
|
| 50 | 58 |
# End iter5. |
| 51 | 59 |
# End for iter1. |
| 52 | 60 |
|
| 53 |
else: # Next runs (p^1..p^alpha) |
|
| 54 |
pass |
|
| 55 |
|
|
| 61 |
else: # pPower > 0: (p^1..p^alpha) |
|
| 62 |
# This where we introduce the p^iPower * N^(alpha-iPower) |
|
| 63 |
# polynomial. |
|
| 64 |
# This step could technically be fused as the first iteration |
|
| 65 |
# of the next loop (with iPower starting at 0). |
|
| 66 |
# We set it apart for clarity. |
|
| 67 |
if columnsWidth != 0: |
|
| 68 |
print "->", spo_expression_as_string(0, 0, pPower, alpha) |
|
| 69 |
currentPolynomial = polynomialAtPower * nAtPower |
|
| 70 |
pMonomials = currentPolynomial.monomials() |
|
| 71 |
pCoefficients = currentPolynomial.coefficients() |
|
| 72 |
spo_add_polynomial_coeffs_to_matrix(pMonomials, |
|
| 73 |
pCoefficients, |
|
| 74 |
knownMonomials, |
|
| 75 |
protoMatrixRows, |
|
| 76 |
columnsWidth) |
|
| 77 |
|
|
| 78 |
# The i^iPower * p^pPower polynomials: they add i^k monomials to |
|
| 79 |
# p^pPower up to k < pIdegree * pPower. This only introduces i^k |
|
| 80 |
# monomials since mixed terms (that were introduced at a previous |
|
| 81 |
# stage) are only shifted to already existing |
|
| 82 |
# ones. p^pPower is "shifted" to higher degrees in i as far as |
|
| 83 |
# possible, one step short of the degree in i of p^(pPower+1) . |
|
| 84 |
# These "pure" i^k monomials can only show up with i multiplications. |
|
| 85 |
for iPower in xrange(1, pIdegree): |
|
| 86 |
print "->", spo_expression_as_string(iPower, 0, pPower, alpha) |
|
| 87 |
currentExpression = i^iPower * nAtPower |
|
| 88 |
currentPolynomial = P(currentExpression) * polynomialAtPower |
|
| 89 |
pMonomials = currentPolynomial.monomials() |
|
| 90 |
pCoefficients = currentPolynomial.coefficients() |
|
| 91 |
spo_add_polynomial_coeffs_to_matrix(pMonomials, |
|
| 92 |
pCoefficients, |
|
| 93 |
knownMonomials, |
|
| 94 |
protoMatrixRows, |
|
| 95 |
columnsWidth) |
|
| 96 |
# End for iPower |
|
| 97 |
# We want now to introduce a t * p^pPower polynomial. But before |
|
| 98 |
# that we must introduce some mixed monomials. |
|
| 99 |
# This loop is no triggered before pPower == 2. |
|
| 100 |
# It introduces a first set of mixed monomials. |
|
| 101 |
for iPower in xrange(1, pPower): |
|
| 102 |
tPower = pPower - iPower + 1 |
|
| 103 |
if columnsWidth != 0: |
|
| 104 |
print "->", spo_expression_as_string(iPower * pIdegree, |
|
| 105 |
tPower, |
|
| 106 |
0, |
|
| 107 |
alpha) |
|
| 108 |
currentExpression = i^(iPower * pIdegree) * t^tPower * nAtPower |
|
| 109 |
currentPolynomial = P(currentExpression) |
|
| 110 |
pMonomials = currentPolynomial.monomials() |
|
| 111 |
pCoefficients = currentPolynomial.coefficients() |
|
| 112 |
spo_add_polynomial_coeffs_to_matrix(pMonomials, |
|
| 113 |
pCoefficients, |
|
| 114 |
knownMonomials, |
|
| 115 |
protoMatrixRows, |
|
| 116 |
columnsWidth) |
|
| 117 |
# End for iPower |
|
| 118 |
# This is the main loop. It introduces: |
|
| 119 |
# - the missing mixed monomials needed before the |
|
| 120 |
# t * p^pPower * N^(alpha-pPower) polynomial; |
|
| 121 |
# - the t * p^pPower * N^(alpha-pPower) itself; |
|
| 122 |
# - the missing mixed monomials needed before each of the |
|
| 123 |
# i^k * t^l * p^pPower * N^(alpha-pPower) polynomials; |
|
| 124 |
# - the i^k * t^l * p^pPower * N^(alpha-pPower) themselves. |
|
| 125 |
for iShift in xrange(0, pIdegree): |
|
| 126 |
# When pTdegree == 1, the following loop only introduces |
|
| 127 |
# a single new monomial. |
|
| 128 |
#print "++++++++++" |
|
| 129 |
for outerTpower in xrange(1, pTdegree + 1): |
|
| 130 |
# First one high i degree mixed monomial. |
|
| 131 |
iPower = iShift + pPower * pIdegree |
|
| 132 |
if columnsWidth != 0: |
|
| 133 |
print "->", spo_expression_as_string(iPower, |
|
| 134 |
outerTpower, |
|
| 135 |
0, |
|
| 136 |
alpha) |
|
| 137 |
currentExpression = i^iPower * t^outerTpower * nAtPower |
|
| 138 |
currentPolynomial = P(currentExpression) |
|
| 139 |
pMonomials = currentPolynomial.monomials() |
|
| 140 |
pCoefficients = currentPolynomial.coefficients() |
|
| 141 |
spo_add_polynomial_coeffs_to_matrix(pMonomials, |
|
| 142 |
pCoefficients, |
|
| 143 |
knownMonomials, |
|
| 144 |
protoMatrixRows, |
|
| 145 |
columnsWidth) |
|
| 146 |
#print "+++++" |
|
| 147 |
|
|
| 148 |
# At iShift == 0, the following loop adds duplicate |
|
| 149 |
# monomials, since no extra i^l * t^k is needed before |
|
| 150 |
# introducing the |
|
| 151 |
# i^iShift * t^outerPpower * p^pPower * N^(alpha-pPower) |
|
| 152 |
# polynomial. |
|
| 153 |
# It introduces smaller i degree monomials than the |
|
| 154 |
# one(s) added previously (no pPower multiplication). |
|
| 155 |
# Here the exponent of t decreases as that of i increases. |
|
| 156 |
if iShift > 0: |
|
| 157 |
iPower = pIdegree + iShift |
|
| 158 |
for innerTpower in xrange(pPower, 1, -1): |
|
| 159 |
if columnsWidth != 0: |
|
| 160 |
print "->", spo_expression_as_string(iPower, |
|
| 161 |
innerTpower, |
|
| 162 |
0, |
|
| 163 |
alpha) |
|
| 164 |
currentExpression = \ |
|
| 165 |
i^(iPower) * t^(innerTpower) * nAtPower |
|
| 166 |
currentPolynomial = P(currentExpression) |
|
| 167 |
pMonomials = currentPolynomial.monomials() |
|
| 168 |
pCoefficients = currentPolynomial.coefficients() |
|
| 169 |
spo_add_polynomial_coeffs_to_matrix(pMonomials, |
|
| 170 |
pCoefficients, |
|
| 171 |
knownMonomials, |
|
| 172 |
protoMatrixRows, |
|
| 173 |
columnsWidth) |
|
| 174 |
iPower += pIdegree |
|
| 175 |
# End for innerTpower |
|
| 176 |
# End of if iShift > 0 |
|
| 177 |
# Eventually, the following section introduces the |
|
| 178 |
# i^iShift * t^outerTpower * p^iPower * N^(alpha-iPower) |
|
| 179 |
# polynomials. |
|
| 180 |
if columnsWidth != 0: |
|
| 181 |
print "->", spo_expression_as_string(iShift, |
|
| 182 |
outerTpower, |
|
| 183 |
pPower, |
|
| 184 |
alpha) |
|
| 185 |
currentExpression = i^iShift * t^outerTpower * nAtPower |
|
| 186 |
currentPolynomial = P(currentExpression) * polynomialAtPower |
|
| 187 |
pMonomials = currentPolynomial.monomials() |
|
| 188 |
pCoefficients = currentPolynomial.coefficients() |
|
| 189 |
spo_add_polynomial_coeffs_to_matrix(pMonomials, |
|
| 190 |
pCoefficients, |
|
| 191 |
knownMonomials, |
|
| 192 |
protoMatrixRows, |
|
| 193 |
columnsWidth) |
|
| 194 |
# End for outerTpower |
|
| 195 |
#print "++++++++++" |
|
| 196 |
|
|
| 197 |
|
|
| 198 |
# End for iShift |
|
| 199 |
polynomialAtPower *= p |
|
| 200 |
nAtPower /= N |
|
| 201 |
# End for pPower loop |
|
| 202 |
return protoMatrixRows |
|
| 56 | 203 |
# End spo_polynomial_to_matrix |
| 57 | 204 |
|
| 58 | 205 |
def spo_add_polynomial_coeffs_to_matrix(pMonomials, |
| 59 | 206 |
pCoefficients, |
| 60 | 207 |
knownMonomials, |
| 61 | 208 |
protoMatrixRows, |
| 62 |
columnWidth=0): |
|
| 209 |
columnsWidth=0):
|
|
| 63 | 210 |
""" |
| 64 | 211 |
For a given polynomial (under the form of monomials and coefficents lists), |
| 65 | 212 |
add the coefficients of the protoMatrix (a list of proto rows). |
| ... | ... | |
| 88 | 235 |
for pmIdx in xrange(0, len(pMonomials)): |
| 89 | 236 |
knownMonomials.append(pMonomials[pmIdx]) |
| 90 | 237 |
protoMatrixRowCoefficients.append(pCoefficients[pmIdx]) |
| 91 |
if columnWidth != 0: |
|
| 238 |
if columnsWidth != 0:
|
|
| 92 | 239 |
monomialAsString = str(pCoefficients[pmIdx]) + " " + \ |
| 93 | 240 |
str(pMonomials[pmIdx]) |
| 94 | 241 |
print monomialAsString, " " * \ |
| 95 |
(columnWidth - len(monomialAsString)), |
|
| 242 |
(columnsWidth - len(monomialAsString)),
|
|
| 96 | 243 |
# There are some known monomials. We search for them in pMonomials and |
| 97 | 244 |
# add their coefficients to the proto matrix row. |
| 98 | 245 |
else: |
| ... | ... | |
| 102 | 249 |
try: |
| 103 | 250 |
indexInPmonomials = \ |
| 104 | 251 |
pMonomials.index(knownMonomials[knownMonomialIndex]) |
| 105 |
if columnWidth != 0: |
|
| 252 |
if columnsWidth != 0:
|
|
| 106 | 253 |
monomialAsString = str(pCoefficients[indexInPmonomials]) + \ |
| 107 | 254 |
" " + str(knownMonomials[knownMonomialIndex]) |
| 108 | 255 |
print monomialAsString, " " * \ |
| 109 |
(columnWidth - len(monomialAsString)), |
|
| 256 |
(columnsWidth - len(monomialAsString)),
|
|
| 110 | 257 |
# Add the coefficient to the proto matrix row and delete the \ |
| 111 | 258 |
# known monomial from the current pMonomial list |
| 112 | 259 |
#(and the corresponding coefficient as well). |
| ... | ... | |
| 116 | 263 |
# The knownMonomials element is not in pMonomials |
| 117 | 264 |
except ValueError: |
| 118 | 265 |
protoMatrixRowCoefficients.append(0) |
| 119 |
if columnWidth != 0: |
|
| 266 |
if columnsWidth != 0:
|
|
| 120 | 267 |
monomialAsString = "0" + " "+ \ |
| 121 | 268 |
str(knownMonomials[knownMonomialIndex]) |
| 122 | 269 |
print monomialAsString, " " * \ |
| 123 |
(columnWidth - len(monomialAsString)), |
|
| 270 |
(columnsWidth - len(monomialAsString)),
|
|
| 124 | 271 |
# End for knownMonomialKey loop. |
| 125 | 272 |
# We now append the remaining monomials of pMonomials to knownMonomials |
| 126 | 273 |
# and the corresponding coefficients to proto matrix row. |
| 127 | 274 |
for pmIdx in xrange(0, len(pMonomials)): |
| 128 | 275 |
knownMonomials.append(pMonomials[pmIdx]) |
| 129 | 276 |
protoMatrixRowCoefficients.append(pCoefficients[pmIdx]) |
| 130 |
if columnWidth != 0: |
|
| 277 |
if columnsWidth != 0:
|
|
| 131 | 278 |
monomialAsString = str(pCoefficients[pmIdx]) + " " \ |
| 132 | 279 |
+ str(pMonomials[pmIdx]) |
| 133 | 280 |
print monomialAsString, " " * \ |
| 134 |
(columnWidth - len(monomialAsString)), |
|
| 281 |
(columnsWidth - len(monomialAsString)),
|
|
| 135 | 282 |
# End for pmIdx loop. |
| 136 | 283 |
# Add the new list row elements to the proto matrix. |
| 137 | 284 |
protoMatrixRows.append(protoMatrixRowCoefficients) |
| 138 |
if columnWidth != 0: |
|
| 285 |
if columnsWidth != 0:
|
|
| 139 | 286 |
|
| 140 | 287 |
# End spo_add_polynomial_coeffs_to_matrix |
| 141 | 288 |
|
Formats disponibles : Unified diff