Révision 83 pobysoPythonSage/src/sageSLZ/sagePolynomialOperations.sage
| sagePolynomialOperations.sage (revision 83) | ||
|---|---|---|
| 1 | 1 |
load "/home/storres/recherche/arithmetique/pobysoPythonSage/src/sageSLZ/sageMatrixOperations.sage" |
| 2 | 2 |
|
| 3 |
def spo_add_polynomial_coeffs_to_matrix(pMonomials, |
|
| 4 |
pCoefficients, |
|
| 5 |
knownMonomials, |
|
| 6 |
protoMatrixRows, |
|
| 7 |
columnsWidth=0): |
|
| 3 |
def spo_add_polynomial_coeffs_to_matrix_row(pMonomials,
|
|
| 4 |
pCoefficients,
|
|
| 5 |
knownMonomials,
|
|
| 6 |
protoMatrixRows,
|
|
| 7 |
columnsWidth=0):
|
|
| 8 | 8 |
""" |
| 9 | 9 |
For a given polynomial (under the form of monomials and coefficents lists), |
| 10 | 10 |
add the coefficients of the protoMatrix (a list of proto matrix rows). |
| 11 | 11 |
Coefficients are added to the protoMatrix row in the order imposed by the |
| 12 | 12 |
monomials discovery list (the knownMonomials list) built as construction |
| 13 | 13 |
goes on. |
| 14 |
As a bonus data can be printed out for a visual check. |
|
| 14 |
As a bonus, data can be printed out for a visual check.
|
|
| 15 | 15 |
pMonomials : the list of the monomials coming form some polynomial; |
| 16 | 16 |
pCoefficients : the list of the corresponding coefficients to add to |
| 17 | 17 |
the protoMatrix in the exact same order as the monomials; |
| ... | ... | |
| 82 | 82 |
protoMatrixRows.append(protoMatrixRowCoefficients) |
| 83 | 83 |
if columnsWidth != 0: |
| 84 | 84 |
|
| 85 |
# End spo_add_polynomial_coeffs_to_matrix |
|
| 85 |
# End spo_add_polynomial_coeffs_to_matrix_row
|
|
| 86 | 86 |
|
| 87 | 87 |
def spo_expression_as_string(powI, powT, powP, alpha): |
| 88 | 88 |
""" |
| ... | ... | |
| 123 | 123 |
return pow(norm, 1/degree) |
| 124 | 124 |
# end spo_norm |
| 125 | 125 |
|
| 126 |
def spo_polynomial_to_matrix(p, pRing, alpha, N, columnsWidth=0): |
|
| 126 |
def spo_polynomial_to_proto_matrix(p, pRing, alpha, N, columnsWidth=0):
|
|
| 127 | 127 |
""" |
| 128 |
From a (bivariate) polynomial and some other parameters build a matrix |
|
| 129 |
to be reduced by fpLLL. |
|
| 128 |
From a (bivariate) polynomial and some other parameters build a proto |
|
| 129 |
matrix (an array of rows) to be converted into a "true" matrix and |
|
| 130 |
eventually by reduced by fpLLL. |
|
| 130 | 131 |
The matrix is such as those found in Boneh-Durphee and Stehl?. |
| 131 | 132 |
|
| 133 |
Parameters |
|
| 134 |
---------- |
|
| 132 | 135 |
p: the (bivariate) polynomial |
| 136 |
pRing: |
|
| 133 | 137 |
alpha: |
| 134 | 138 |
N: |
| 135 |
|
|
| 139 |
columsWidth: if == 0, no information is displayed, otherwise data is |
|
| 140 |
printed in colums of columnsWitdth width. |
|
| 136 | 141 |
""" |
| 137 | 142 |
knownMonomials = [] |
| 138 | 143 |
protoMatrixRows = [] |
| ... | ... | |
| 172 | 177 |
polynomialAtPower |
| 173 | 178 |
pMonomials = currentPolynomial.monomials() |
| 174 | 179 |
pCoefficients = currentPolynomial.coefficients() |
| 175 |
spo_add_polynomial_coeffs_to_matrix(pMonomials, |
|
| 176 |
pCoefficients, |
|
| 177 |
knownMonomials, |
|
| 178 |
protoMatrixRows, |
|
| 179 |
columnsWidth) |
|
| 180 |
spo_add_polynomial_coeffs_to_matrix_row(pMonomials,
|
|
| 181 |
pCoefficients,
|
|
| 182 |
knownMonomials,
|
|
| 183 |
protoMatrixRows,
|
|
| 184 |
columnsWidth)
|
|
| 180 | 185 |
# End tPower. |
| 181 | 186 |
# End for iPower. |
| 182 | 187 |
else: # pPower > 0: (p^1..p^alpha) |
| ... | ... | |
| 190 | 195 |
currentPolynomial = polynomialAtPower * nAtPower |
| 191 | 196 |
pMonomials = currentPolynomial.monomials() |
| 192 | 197 |
pCoefficients = currentPolynomial.coefficients() |
| 193 |
spo_add_polynomial_coeffs_to_matrix(pMonomials, |
|
| 194 |
pCoefficients, |
|
| 195 |
knownMonomials, |
|
| 196 |
protoMatrixRows, |
|
| 197 |
columnsWidth) |
|
| 198 |
spo_add_polynomial_coeffs_to_matrix_row(pMonomials,
|
|
| 199 |
pCoefficients,
|
|
| 200 |
knownMonomials,
|
|
| 201 |
protoMatrixRows,
|
|
| 202 |
columnsWidth)
|
|
| 198 | 203 |
|
| 199 | 204 |
# The i^iPower * p^pPower polynomials: they add i^k monomials to |
| 200 | 205 |
# p^pPower up to k < pIdegree * pPower. This only introduces i^k |
| ... | ... | |
| 209 | 214 |
currentPolynomial = P(currentExpression) * polynomialAtPower |
| 210 | 215 |
pMonomials = currentPolynomial.monomials() |
| 211 | 216 |
pCoefficients = currentPolynomial.coefficients() |
| 212 |
spo_add_polynomial_coeffs_to_matrix(pMonomials, |
|
| 213 |
pCoefficients, |
|
| 214 |
knownMonomials, |
|
| 215 |
protoMatrixRows, |
|
| 216 |
columnsWidth) |
|
| 217 |
spo_add_polynomial_coeffs_to_matrix_row(pMonomials,
|
|
| 218 |
pCoefficients,
|
|
| 219 |
knownMonomials,
|
|
| 220 |
protoMatrixRows,
|
|
| 221 |
columnsWidth)
|
|
| 217 | 222 |
# End for iPower |
| 218 | 223 |
# We want now to introduce a t * p^pPower polynomial. But before |
| 219 | 224 |
# that we must introduce some mixed monomials. |
| ... | ... | |
| 230 | 235 |
currentPolynomial = P(currentExpression) |
| 231 | 236 |
pMonomials = currentPolynomial.monomials() |
| 232 | 237 |
pCoefficients = currentPolynomial.coefficients() |
| 233 |
spo_add_polynomial_coeffs_to_matrix(pMonomials, |
|
| 234 |
pCoefficients, |
|
| 235 |
knownMonomials, |
|
| 236 |
protoMatrixRows, |
|
| 237 |
columnsWidth) |
|
| 238 |
spo_add_polynomial_coeffs_to_matrix_row(pMonomials,
|
|
| 239 |
pCoefficients,
|
|
| 240 |
knownMonomials,
|
|
| 241 |
protoMatrixRows,
|
|
| 242 |
columnsWidth)
|
|
| 238 | 243 |
# End for iPower |
| 239 | 244 |
# |
| 240 | 245 |
# This is the mixed monomials main loop. It introduces: |
| ... | ... | |
| 262 | 267 |
currentPolynomial = P(currentExpression) |
| 263 | 268 |
pMonomials = currentPolynomial.monomials() |
| 264 | 269 |
pCoefficients = currentPolynomial.coefficients() |
| 265 |
spo_add_polynomial_coeffs_to_matrix(pMonomials, |
|
| 266 |
pCoefficients, |
|
| 267 |
knownMonomials, |
|
| 268 |
protoMatrixRows, |
|
| 269 |
columnsWidth) |
|
| 270 |
spo_add_polynomial_coeffs_to_matrix_row(pMonomials,
|
|
| 271 |
pCoefficients,
|
|
| 272 |
knownMonomials,
|
|
| 273 |
protoMatrixRows,
|
|
| 274 |
columnsWidth)
|
|
| 270 | 275 |
#print "+++++" |
| 271 | 276 |
# At iShift == 0, the following innerTpower loop adds |
| 272 | 277 |
# duplicate monomials, since no extra i^l * t^k is needed |
| ... | ... | |
| 293 | 298 |
currentPolynomial = P(currentExpression) |
| 294 | 299 |
pMonomials = currentPolynomial.monomials() |
| 295 | 300 |
pCoefficients = currentPolynomial.coefficients() |
| 296 |
spo_add_polynomial_coeffs_to_matrix(pMonomials, |
|
| 301 |
spo_add_polynomial_coeffs_to_matrix_row(pMonomials,
|
|
| 297 | 302 |
pCoefficients, |
| 298 | 303 |
knownMonomials, |
| 299 | 304 |
protoMatrixRows, |
| ... | ... | |
| 319 | 324 |
currentPolynomial = P(currentExpression) * polynomialAtPower |
| 320 | 325 |
pMonomials = currentPolynomial.monomials() |
| 321 | 326 |
pCoefficients = currentPolynomial.coefficients() |
| 322 |
spo_add_polynomial_coeffs_to_matrix(pMonomials, |
|
| 323 |
pCoefficients, |
|
| 324 |
knownMonomials, |
|
| 325 |
protoMatrixRows, |
|
| 326 |
columnsWidth) |
|
| 327 |
spo_add_polynomial_coeffs_to_matrix_row(pMonomials,
|
|
| 328 |
pCoefficients,
|
|
| 329 |
knownMonomials,
|
|
| 330 |
protoMatrixRows,
|
|
| 331 |
columnsWidth)
|
|
| 327 | 332 |
# End for outerTpower |
| 328 | 333 |
#print "++++++++++" |
| 329 | 334 |
# End for iShift |
| ... | ... | |
| 331 | 336 |
nAtPower /= N |
| 332 | 337 |
# End for pPower loop |
| 333 | 338 |
return protoMatrixRows |
| 334 |
# End spo_polynomial_to_matrix |
|
| 339 |
# End spo_polynomial_to_proto_matrix
|
|
| 335 | 340 |
|
| 341 |
def spo_proto_to_column_matrix(protoMatrixRows): |
|
| 342 |
""" |
|
| 343 |
Create a row (each column holds the coefficients of one polynomial) matrix. |
|
| 344 |
protoMatrixRows. |
|
| 345 |
|
|
| 346 |
Parameters |
|
| 347 |
---------- |
|
| 348 |
protoMatrixRows: a list of coefficient lists. |
|
| 349 |
""" |
|
| 350 |
numRows = len(protoMatrixRows) |
|
| 351 |
if numRows == 0: |
|
| 352 |
return None |
|
| 353 |
numColumns = len(protoMatrixRows[numRows-1]) |
|
| 354 |
if numColumns == 0: |
|
| 355 |
return None |
|
| 356 |
baseMatrix = matrix(ZZ, numRows, numColumns) |
|
| 357 |
for rowIndex in xrange(0, numRows): |
|
| 358 |
if monomialLengthChars != 0: |
|
| 359 |
print protoMatrixRows[rowIndex] |
|
| 360 |
for colIndex in xrange(0, len(protoMatrixRows[rowIndex])): |
|
| 361 |
baseMatrix[colIndex, rowIndex] = protoMatrixRows[rowIndex][colIndex] |
|
| 362 |
return baseMatrix |
|
| 363 |
# End spo_proto_to_column_matrix. |
|
| 364 |
# |
|
| 365 |
def spo_proto_to_row_matrix(protoMatrixRows): |
|
| 366 |
""" |
|
| 367 |
Create a row (each row holds the coefficients of one polynomial) matrix. |
|
| 368 |
protoMatrixRows. |
|
| 369 |
|
|
| 370 |
Parameters |
|
| 371 |
---------- |
|
| 372 |
protoMatrixRows: a list of coefficient lists. |
|
| 373 |
""" |
|
| 374 |
numRows = len(protoMatrixRows) |
|
| 375 |
if numRows == 0: |
|
| 376 |
return None |
|
| 377 |
numColumns = len(protoMatrixRows[numRows-1]) |
|
| 378 |
if numColumns == 0: |
|
| 379 |
return None |
|
| 380 |
baseMatrix = matrix(ZZ, numRows, numColumns) |
|
| 381 |
for rowIndex in xrange(0, numRows): |
|
| 382 |
if monomialLengthChars != 0: |
|
| 383 |
print protoMatrixRows[rowIndex] |
|
| 384 |
for colIndex in xrange(0, len(protoMatrixRows[rowIndex])): |
|
| 385 |
baseMatrix[rowIndex, colIndex] = protoMatrixRows[rowIndex][colIndex] |
|
| 386 |
return baseMatrix |
|
| 387 |
# End spo_proto_to_row_matrix. |
|
| 388 |
# |
|
| 336 | 389 |
print "sagePolynomialOperations loaded..." |
Formats disponibles : Unified diff