Révision 87 pobysoPythonSage/src/sageSLZ/sagePolynomialOperations.sage
| sagePolynomialOperations.sage (revision 87) | ||
|---|---|---|
| 1 | 1 |
load "/home/storres/recherche/arithmetique/pobysoPythonSage/src/sageSLZ/sageMatrixOperations.sage" |
| 2 |
|
|
| 2 |
print "sagePolynomialOperations loading..." |
|
| 3 | 3 |
def spo_add_polynomial_coeffs_to_matrix_row(pMonomials, |
| 4 | 4 |
pCoefficients, |
| 5 | 5 |
knownMonomials, |
| ... | ... | |
| 107 | 107 |
return(expressionAsString) |
| 108 | 108 |
# End spo_expression_as_string. |
| 109 | 109 |
|
| 110 |
def spo_norm(poly, degree):
|
|
| 110 |
def spo_norm(poly, p=2):
|
|
| 111 | 111 |
""" |
| 112 | 112 |
Behaves more or less (no infinity defined) as the norm for the |
| 113 | 113 |
univariate polynomials. |
| ... | ... | |
| 115 | 115 |
Definition: For integer p, the p-norm of a polynomial is the pth root of |
| 116 | 116 |
the sum of the pth powers of the absolute values of the coefficients of |
| 117 | 117 |
the polynomial. |
| 118 |
|
|
| 118 | 119 |
""" |
| 119 |
# TODO: check the arguments. |
|
| 120 |
# TODO: check the arguments (for p see below)..
|
|
| 120 | 121 |
norm = 0 |
| 122 |
# For infinity norm. |
|
| 123 |
if p == Infinity: |
|
| 124 |
for coefficient in poly.coefficients(): |
|
| 125 |
coefficientAbs = coefficient.abs() |
|
| 126 |
if coefficientAbs > norm: |
|
| 127 |
norm = coefficientAbs |
|
| 128 |
return norm |
|
| 129 |
# TODO: check here the value of p |
|
| 130 |
# For 1 norm. |
|
| 131 |
if p == 1: |
|
| 132 |
for coefficient in poly.coefficients(): |
|
| 133 |
norm += coefficient.abs() |
|
| 134 |
return norm |
|
| 135 |
# For other norms |
|
| 121 | 136 |
for coefficient in poly.coefficients(): |
| 122 |
norm += (coefficient^degree).abs()
|
|
| 123 |
return pow(norm, 1/degree)
|
|
| 137 |
norm += (coefficient^p).abs()
|
|
| 138 |
return pow(norm, 1/p)
|
|
| 124 | 139 |
# end spo_norm |
| 125 | 140 |
|
| 126 | 141 |
def spo_polynomial_to_proto_matrix(p, pRing, alpha, N, columnsWidth=0): |
| 127 | 142 |
""" |
| 128 | 143 |
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
|
|
| 144 |
matrix (an array of "rows") to be converted into a "true" matrix and
|
|
| 130 | 145 |
eventually by reduced by fpLLL. |
| 131 | 146 |
The matrix is such as those found in Boneh-Durphee and Stehl?. |
| 132 | 147 |
|
| 133 | 148 |
Parameters |
| 134 | 149 |
---------- |
| 135 |
p: the (bivariate) polynomial |
|
| 136 |
pRing: |
|
| 150 |
p: the (bivariate) polynomial;
|
|
| 151 |
pRing: the ring over which p is defined;
|
|
| 137 | 152 |
alpha: |
| 138 | 153 |
N: |
| 139 | 154 |
columsWidth: if == 0, no information is displayed, otherwise data is |
| ... | ... | |
| 144 | 159 |
pVariables = p.variables() |
| 145 | 160 |
iVariable = pVariables[0] |
| 146 | 161 |
tVariable = pVariables[1] |
| 147 |
polynomialAtPower = P(1)
|
|
| 148 |
currentPolynomial = P(1)
|
|
| 162 |
polynomialAtPower = pRing(1)
|
|
| 163 |
currentPolynomial = pRing(1)
|
|
| 149 | 164 |
pIdegree = p.degree(pVariables[0]) |
| 150 | 165 |
pTdegree = p.degree(pVariables[1]) |
| 151 |
currentIdegree = currentPolynomial.degree(i) |
|
| 166 |
currentIdegree = currentPolynomial.degree(iVariable)
|
|
| 152 | 167 |
nAtPower = N^alpha |
| 153 | 168 |
# We work from p^0 * N^alpha to p^alpha * N^0 |
| 154 | 169 |
for pPower in xrange(0, alpha + 1): |
| ... | ... | |
| 209 | 224 |
# possible, one step short of the degree in i of p^(pPower+1) . |
| 210 | 225 |
# These "pure" i^k monomials can only show up with i multiplications. |
| 211 | 226 |
for iPower in xrange(1, pIdegree): |
| 212 |
print "->", spo_expression_as_string(iPower, 0, pPower, alpha) |
|
| 227 |
if columnsWidth != 0: |
|
| 228 |
print "->", spo_expression_as_string(iPower, \ |
|
| 229 |
0, \ |
|
| 230 |
pPower, \ |
|
| 231 |
alpha) |
|
| 213 | 232 |
currentExpression = i^iPower * nAtPower |
| 214 |
currentPolynomial = P(currentExpression) * polynomialAtPower
|
|
| 233 |
currentPolynomial = pRing(currentExpression) * polynomialAtPower
|
|
| 215 | 234 |
pMonomials = currentPolynomial.monomials() |
| 216 | 235 |
pCoefficients = currentPolynomial.coefficients() |
| 217 |
spo_add_polynomial_coeffs_to_matrix_row(pMonomials, |
|
| 218 |
pCoefficients, |
|
| 219 |
knownMonomials, |
|
| 220 |
protoMatrixRows, |
|
| 236 |
spo_add_polynomial_coeffs_to_matrix_row(pMonomials, \
|
|
| 237 |
pCoefficients, \
|
|
| 238 |
knownMonomials, \
|
|
| 239 |
protoMatrixRows, \
|
|
| 221 | 240 |
columnsWidth) |
| 222 | 241 |
# End for iPower |
| 223 | 242 |
# We want now to introduce a t * p^pPower polynomial. But before |
| ... | ... | |
| 232 | 251 |
0, |
| 233 | 252 |
alpha) |
| 234 | 253 |
currentExpression = i^(iPower * pIdegree) * t^tPower * nAtPower |
| 235 |
currentPolynomial = P(currentExpression)
|
|
| 254 |
currentPolynomial = pRing(currentExpression)
|
|
| 236 | 255 |
pMonomials = currentPolynomial.monomials() |
| 237 | 256 |
pCoefficients = currentPolynomial.coefficients() |
| 238 | 257 |
spo_add_polynomial_coeffs_to_matrix_row(pMonomials, |
| ... | ... | |
| 264 | 283 |
0, |
| 265 | 284 |
alpha) |
| 266 | 285 |
currentExpression = i^iPower * t^outerTpower * nAtPower |
| 267 |
currentPolynomial = P(currentExpression)
|
|
| 286 |
currentPolynomial = pRing(currentExpression)
|
|
| 268 | 287 |
pMonomials = currentPolynomial.monomials() |
| 269 | 288 |
pCoefficients = currentPolynomial.coefficients() |
| 270 | 289 |
spo_add_polynomial_coeffs_to_matrix_row(pMonomials, |
| ... | ... | |
| 295 | 314 |
alpha) |
| 296 | 315 |
currentExpression = \ |
| 297 | 316 |
i^(iPower) * t^(innerTpower) * nAtPower |
| 298 |
currentPolynomial = P(currentExpression)
|
|
| 317 |
currentPolynomial = pRing(currentExpression)
|
|
| 299 | 318 |
pMonomials = currentPolynomial.monomials() |
| 300 | 319 |
pCoefficients = currentPolynomial.coefficients() |
| 301 | 320 |
spo_add_polynomial_coeffs_to_matrix_row(pMonomials, |
| ... | ... | |
| 321 | 340 |
pPower, |
| 322 | 341 |
alpha) |
| 323 | 342 |
currentExpression = i^iShift * t^outerTpower * nAtPower |
| 324 |
currentPolynomial = P(currentExpression) * polynomialAtPower
|
|
| 343 |
currentPolynomial = pRing(currentExpression) * polynomialAtPower
|
|
| 325 | 344 |
pMonomials = currentPolynomial.monomials() |
| 326 | 345 |
pCoefficients = currentPolynomial.coefficients() |
| 327 | 346 |
spo_add_polynomial_coeffs_to_matrix_row(pMonomials, |
| ... | ... | |
| 335 | 354 |
polynomialAtPower *= p |
| 336 | 355 |
nAtPower /= N |
| 337 | 356 |
# End for pPower loop |
| 338 |
return protoMatrixRows
|
|
| 357 |
return ((protoMatrixRows, knownMonomials))
|
|
| 339 | 358 |
# End spo_polynomial_to_proto_matrix |
| 340 | 359 |
|
| 341 |
def spo_proto_to_column_matrix(protoMatrixRows):
|
|
| 360 |
def spo_proto_to_column_matrix(protoMatrixColumns):
|
|
| 342 | 361 |
""" |
| 343 |
Create a row (each column holds the coefficients of one polynomial) matrix.
|
|
| 362 |
Create a column (each row holds the coefficients of one monomial) matrix.
|
|
| 344 | 363 |
protoMatrixRows. |
| 345 | 364 |
|
| 346 | 365 |
Parameters |
| 347 | 366 |
---------- |
| 348 |
protoMatrixRows: a list of coefficient lists.
|
|
| 367 |
protoMatrixColumns: a list of coefficient lists.
|
|
| 349 | 368 |
""" |
| 350 |
numRows = len(protoMatrixRows)
|
|
| 351 |
if numRows == 0:
|
|
| 369 |
numColumns = len(protoMatrixColumns)
|
|
| 370 |
if numColumns == 0:
|
|
| 352 | 371 |
return None |
| 353 |
numColumns = len(protoMatrixRows[numRows-1]) |
|
| 372 |
# The last column holds has the maximum length. |
|
| 373 |
numRows = len(protoMatrixColumns[numColumns-1]) |
|
| 354 | 374 |
if numColumns == 0: |
| 355 | 375 |
return None |
| 356 | 376 |
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] |
|
| 377 |
for colIndex in xrange(0, numColumns): |
|
| 378 |
for rowIndex in xrange(0, len(protoMatrixColumns[colIndex])): |
|
| 379 |
baseMatrix[rowIndex, colIndex] = \ |
|
| 380 |
protoMatrixColumns[colIndex][rowIndex] |
|
| 362 | 381 |
return baseMatrix |
| 363 | 382 |
# End spo_proto_to_column_matrix. |
| 364 | 383 |
# |
| 365 | 384 |
def spo_proto_to_row_matrix(protoMatrixRows): |
| 366 | 385 |
""" |
| 367 |
Create a row (each row holds the coefficients of one polynomial) matrix.
|
|
| 386 |
Create a row (each column holds the coefficients of one monomial) matrix.
|
|
| 368 | 387 |
protoMatrixRows. |
| 369 | 388 |
|
| 370 | 389 |
Parameters |
| ... | ... | |
| 379 | 398 |
return None |
| 380 | 399 |
baseMatrix = matrix(ZZ, numRows, numColumns) |
| 381 | 400 |
for rowIndex in xrange(0, numRows): |
| 382 |
if monomialLengthChars != 0: |
|
| 383 |
print protoMatrixRows[rowIndex] |
|
| 384 | 401 |
for colIndex in xrange(0, len(protoMatrixRows[rowIndex])): |
| 385 | 402 |
baseMatrix[rowIndex, colIndex] = protoMatrixRows[rowIndex][colIndex] |
| 386 | 403 |
return baseMatrix |
| 387 | 404 |
# End spo_proto_to_row_matrix. |
| 388 | 405 |
# |
| 389 |
print "sagePolynomialOperations loaded..." |
|
| 406 |
print "\t...sagePolynomialOperations loaded" |
|
Formats disponibles : Unified diff