| 103 |
103 |
# End spo_get_coefficient_for_monomial.
|
| 104 |
104 |
|
| 105 |
105 |
|
| 106 |
|
def spo_expression_as_string(powI, powT, powP, powN):
|
|
106 |
def spo_expression_as_string(powI, boundI, powT, boundT, powP, powN):
|
| 107 |
107 |
"""
|
| 108 |
108 |
Computes a string version of the i^k + t^l + p^m + N^n expression for
|
| 109 |
109 |
output.
|
| 110 |
110 |
"""
|
| 111 |
111 |
expressionAsString =""
|
| 112 |
112 |
if powI != 0:
|
| 113 |
|
expressionAsString += "i^" + str(powI)
|
|
113 |
expressionAsString += str(iBound^powI) + " i^" + str(powI)
|
| 114 |
114 |
if powT != 0:
|
| 115 |
115 |
if len(expressionAsString) != 0:
|
| 116 |
116 |
expressionAsString += " * "
|
| 117 |
|
expressionAsString += "t^" + str(powT)
|
|
117 |
expressionAsString += str(tBound^powT) + " t^" + str(powT)
|
| 118 |
118 |
if powP != 0:
|
| 119 |
119 |
if len(expressionAsString) != 0:
|
| 120 |
120 |
expressionAsString += " * "
|
| ... | ... | |
| 396 |
396 |
return ((protoMatrixRows, knownMonomials, polynomialsList))
|
| 397 |
397 |
# End spo_polynomial_to_proto_matrix
|
| 398 |
398 |
|
| 399 |
|
def spo_polynomial_to_polynomials_list_2(p, alpha, N, columnsWidth=0):
|
|
399 |
def spo_polynomial_to_polynomials_list_2(p, alpha, N, iBound, tBound,
|
|
400 |
columnsWidth=0):
|
| 400 |
401 |
"""
|
| 401 |
402 |
From p, alpha, N build a list of polynomials...
|
| 402 |
403 |
TODO: clean up the comments below!
|
| ... | ... | |
| 448 |
449 |
# No t power is taken into account as we limit our selves to
|
| 449 |
450 |
# degree 1 in t and make no "t-shifts".
|
| 450 |
451 |
if columnsWidth != 0:
|
| 451 |
|
polExpStr = spo_expression_as_string(iPower,
|
|
452 |
polExpStr = spo_expression_as_string(iPower,
|
|
453 |
iBound,
|
| 452 |
454 |
0,
|
|
455 |
tBound,
|
| 453 |
456 |
0,
|
| 454 |
457 |
alpha)
|
| 455 |
458 |
print "->", polExpStr
|
| 456 |
|
currentExpression = iVariable^iPower * nAtAlpha
|
|
459 |
currentExpression = iVariable^iPower * nAtAlpha * iBound^iPower
|
| 457 |
460 |
# polynomialAtPower == 1 here. Next line should be commented
|
| 458 |
461 |
# out but it does not work! Some conversion problem?
|
| 459 |
462 |
currentPolynomial = pRing(currentExpression)
|
| ... | ... | |
| 464 |
467 |
# polynomial. This is also where the t^pPower monomials shows up for
|
| 465 |
468 |
# the first time.
|
| 466 |
469 |
if columnsWidth != 0:
|
| 467 |
|
polExpStr = spo_expression_as_string(0, 0, pPower, alpha-pPower)
|
|
470 |
polExpStr = spo_expression_as_string(0, iBound, 0, tBound, \
|
|
471 |
pPower, alpha-pPower)
|
| 468 |
472 |
print "->", polExpStr
|
| 469 |
473 |
currentPolynomial = polynomialAtPower * nAtPower
|
| 470 |
474 |
polynomialsList.append(currentPolynomial)
|
| ... | ... | |
| 485 |
489 |
internalIpower = iPower
|
| 486 |
490 |
for tPower in xrange(pPower,0,-1):
|
| 487 |
491 |
if columnsWidth != 0:
|
| 488 |
|
polExpStr = spo_expression_as_string(internalIpower, \
|
| 489 |
|
tPower, \
|
| 490 |
|
0, \
|
|
492 |
polExpStr = spo_expression_as_string(internalIpower,
|
|
493 |
iBound,
|
|
494 |
tPower,
|
|
495 |
tBound,
|
|
496 |
0,
|
| 491 |
497 |
alpha)
|
| 492 |
498 |
print "->", polExpStr
|
| 493 |
|
currentExpression = i^internalIpower * t^tPower * nAtAlpha
|
|
499 |
currentExpression = i^internalIpower * t^tPower * \
|
|
500 |
nAtAlpha * iBound^internalIpower * \
|
|
501 |
tBound^tPower
|
|
502 |
|
| 494 |
503 |
currentPolynomial = pRing(currentExpression)
|
| 495 |
504 |
polynomialsList.append(currentPolynomial)
|
| 496 |
505 |
internalIpower += pIdegree
|
| 497 |
506 |
# End for tPower
|
| 498 |
507 |
# The i^iPower * p^pPower * N^(alpha-pPower) i-shift.
|
| 499 |
508 |
if columnsWidth != 0:
|
| 500 |
|
polExpStr = spo_expression_as_string(iPower, \
|
| 501 |
|
0, \
|
| 502 |
|
pPower, \
|
|
509 |
polExpStr = spo_expression_as_string(iPower,
|
|
510 |
iBound,
|
|
511 |
0,
|
|
512 |
tBound,
|
|
513 |
pPower,
|
| 503 |
514 |
alpha-pPower)
|
| 504 |
515 |
print "->", polExpStr
|
| 505 |
|
currentExpression = i^iPower * nAtPower
|
|
516 |
currentExpression = i^iPower * nAtPower * iBound^iPower
|
| 506 |
517 |
currentPolynomial = pRing(currentExpression) * polynomialAtPower
|
| 507 |
518 |
polynomialsList.append(currentPolynomial)
|
| 508 |
519 |
# End for iPower
|
| ... | ... | |
| 512 |
523 |
return polynomialsList
|
| 513 |
524 |
# End spo_polynomial_to_proto_matrix_2
|
| 514 |
525 |
|
| 515 |
|
def spo_polynomial_to_polynomials_list_3(p, alpha, N, iBound, tBound, \
|
|
526 |
def spo_polynomial_to_polynomials_list_3(p, alpha, N, iBound, tBound,
|
| 516 |
527 |
columnsWidth=0):
|
| 517 |
528 |
"""
|
| 518 |
529 |
From p, alpha, N build a list of polynomials...
|
| ... | ... | |
| 532 |
543 |
printed in colums of columnsWitdth width.
|
| 533 |
544 |
"""
|
| 534 |
545 |
pRing = p.parent()
|
| 535 |
|
knownMonomials = []
|
| 536 |
546 |
polynomialsList = []
|
| 537 |
547 |
pVariables = p.variables()
|
| 538 |
548 |
iVariable = pVariables[0]
|
| ... | ... | |
| 556 |
566 |
# degree 1 in t and make no "t-shifts".
|
| 557 |
567 |
if columnsWidth != 0:
|
| 558 |
568 |
polExpStr = spo_expression_as_string(iPower,
|
|
569 |
iBound,
|
| 559 |
570 |
0,
|
|
571 |
tBound,
|
| 560 |
572 |
0,
|
| 561 |
573 |
alpha)
|
| 562 |
574 |
print "->", polExpStr
|
| 563 |
|
currentExpression = iVariable^iPower * nAtAlpha
|
|
575 |
currentExpression = iVariable^iPower * nAtAlpha * iBound^iPower
|
| 564 |
576 |
# polynomialAtPower == 1 here. Next line should be commented
|
| 565 |
577 |
# out but it does not work! Some conversion problem?
|
| 566 |
578 |
currentPolynomial = pRing(currentExpression)
|
| ... | ... | |
| 571 |
583 |
# polynomial. This is also where the t^pPower monomials shows up for
|
| 572 |
584 |
# the first time. It app
|
| 573 |
585 |
if columnsWidth != 0:
|
| 574 |
|
polExpStr = spo_expression_as_string(0, 0, pPower, alpha-pPower)
|
|
586 |
polExpStr = spo_expression_as_string(0, iBound,
|
|
587 |
0, tBound,
|
|
588 |
pPower, alpha-pPower)
|
| 575 |
589 |
print "->", polExpStr
|
| 576 |
590 |
currentPolynomial = polynomialAtPower * nAtPower
|
| 577 |
591 |
polynomialsList.append(currentPolynomial)
|
| 578 |
592 |
# Exit when pPower == alpha
|
| 579 |
593 |
if pPower == alpha:
|
| 580 |
|
return((knownMonomials, polynomialsList))
|
|
594 |
return polynomialsList
|
| 581 |
595 |
# This is where the "i-shifts" take place. Mixed terms, i^k * t^l
|
| 582 |
596 |
# (that were introduced at a previous
|
| 583 |
597 |
# stage or are introduced now) are only shifted to already existing
|
| ... | ... | |
| 592 |
606 |
internalIpower = iPower
|
| 593 |
607 |
for tPower in xrange(pPower,0,-1):
|
| 594 |
608 |
if columnsWidth != 0:
|
| 595 |
|
polExpStr = spo_expression_as_string(internalIpower, \
|
| 596 |
|
tPower, \
|
| 597 |
|
0, \
|
|
609 |
polExpStr = spo_expression_as_string(internalIpower,
|
|
610 |
iBound,
|
|
611 |
tPower,
|
|
612 |
tBound,
|
|
613 |
0,
|
| 598 |
614 |
alpha)
|
| 599 |
615 |
print "->", polExpStr
|
| 600 |
|
currentExpression = i^internalIpower * t^tPower * nAtAlpha
|
|
616 |
currentExpression = i^internalIpower * t^tPower * nAtAlpha * \
|
|
617 |
iBound^internalIpower * tBound^tPower
|
| 601 |
618 |
currentPolynomial = pRing(currentExpression)
|
| 602 |
619 |
polynomialsList.append(currentPolynomial)
|
| 603 |
620 |
internalIpower += pIdegree
|
| 604 |
621 |
# End for tPower
|
| 605 |
622 |
# Here we have to choose between a
|
| 606 |
623 |
# i^iPower * p^pPower * N^(alpha-pPower) i-shift and
|
| 607 |
|
# i^iPower * i^(d_i(p) * pPower) * N^alpha, depend on which
|
|
624 |
# i^iPower * i^(d_i(p) * pPower) * N^alpha, depending on which
|
| 608 |
625 |
# coefficient is smallest.
|
| 609 |
626 |
IcurrentExponent = iPower + \
|
| 610 |
|
(pPower * polynomialAtPower.degree(i))
|
| 611 |
|
currentMonomial = pRing(i^(IcurrentExponent))
|
| 612 |
|
currentPolynomial = pRing(i^iPower * nAtPower) * \
|
| 613 |
|
polynomialAtPower
|
|
627 |
(pPower * polynomialAtPower.degree(iVariable))
|
|
628 |
currentMonomial = pRing(iVariable^IcurrentExponent)
|
|
629 |
currentPolynomial = pRing(iVariable^iPower * nAtPower * \
|
|
630 |
iBound^iPower) * \
|
|
631 |
polynomialAtPower
|
| 614 |
632 |
currMonomials = currentPolynomial.monomials()
|
| 615 |
633 |
currCoefficients = currentPolynomial.coefficients()
|
| 616 |
634 |
currentCoefficient = spo_get_coefficient_for_monomial( \
|
| 617 |
635 |
currMonomials,
|
| 618 |
636 |
currCoefficients,
|
| 619 |
637 |
currentMonomial)
|
| 620 |
|
if currentCoefficient > nAtAlpha:
|
|
638 |
print "Current coefficient:", currentCoefficient
|
|
639 |
alterCoefficient = iBound^IcurrentExponent * nAtAlpha
|
|
640 |
print "N^alpha * ibound^", IcurrentExponent, ":", \
|
|
641 |
alterCoefficient
|
|
642 |
if currentCoefficient > alterCoefficient :
|
| 621 |
643 |
if columnsWidth != 0:
|
| 622 |
|
polExpStr = spo_expression_as_string(IcurrentCoefficient, \
|
| 623 |
|
0, \
|
| 624 |
|
0, \
|
|
644 |
polExpStr = spo_expression_as_string(IcurrentExponent,
|
|
645 |
iBound,
|
|
646 |
0,
|
|
647 |
tBound,
|
|
648 |
0,
|
| 625 |
649 |
alpha)
|
| 626 |
|
print "->", polExpStr
|
| 627 |
|
polynomialsList.append(currentMonomial * nAtAlpha)
|
|
650 |
print "->", polExpStr
|
|
651 |
polynomialsList.append(currentMonomial * \
|
|
652 |
alterCoefficient)
|
| 628 |
653 |
else:
|
| 629 |
654 |
if columnsWidth != 0:
|
| 630 |
|
polExpStr = spo_expression_as_string(iPower, \
|
| 631 |
|
0, \
|
| 632 |
|
pPower, \
|
|
655 |
polExpStr = spo_expression_as_string(iPower, iBound,
|
|
656 |
0, tBound,
|
|
657 |
pPower,
|
| 633 |
658 |
alpha-pPower)
|
| 634 |
|
print "->", polExpStr
|
|
659 |
print "->", polExpStr
|
| 635 |
660 |
polynomialsList.append(currentPolynomial)
|
| 636 |
661 |
# End for iPower
|
| 637 |
662 |
polynomialAtPower *= p
|
| ... | ... | |
| 640 |
665 |
return polynomialsList
|
| 641 |
666 |
# End spo_polynomial_to_proto_matrix_3
|
| 642 |
667 |
|
| 643 |
|
def spo_proto_to_column_matrix(protoMatrixColumns, \
|
| 644 |
|
knownMonomialsList, \
|
| 645 |
|
boundVar1, \
|
| 646 |
|
boundVar2):
|
|
668 |
def spo_polynomial_to_polynomials_list_4(p, alpha, N, iBound, tBound,
|
|
669 |
columnsWidth=0):
|
| 647 |
670 |
"""
|
| 648 |
|
Create a column (each row holds the coefficients of one monomial) matrix.
|
|
671 |
From p, alpha, N build a list of polynomials...
|
|
672 |
TODO: more in depth rationale...
|
| 649 |
673 |
|
|
674 |
Our goal is to introduce each monomial with the smallest coefficient.
|
|
675 |
|
|
676 |
|
|
677 |
|
| 650 |
678 |
Parameters
|
| 651 |
679 |
----------
|
|
680 |
p: the (bivariate) polynomial;
|
|
681 |
pRing: the ring over which p is defined;
|
|
682 |
alpha:
|
|
683 |
N:
|
|
684 |
columsWidth: if == 0, no information is displayed, otherwise data is
|
|
685 |
printed in colums of columnsWitdth width.
|
|
686 |
"""
|
|
687 |
pRing = p.parent()
|
|
688 |
polynomialsList = []
|
|
689 |
pVariables = p.variables()
|
|
690 |
iVariable = pVariables[0]
|
|
691 |
tVariable = pVariables[1]
|
|
692 |
polynomialAtPower = copy(p)
|
|
693 |
currentPolynomial = pRing(1)
|
|
694 |
pIdegree = p.degree(iVariable)
|
|
695 |
pTdegree = p.degree(tVariable)
|
|
696 |
maxIdegree = pIdegree * alpha
|
|
697 |
currentIdegree = currentPolynomial.degree(iVariable)
|
|
698 |
nAtAlpha = N^alpha
|
|
699 |
nAtPower = nAtAlpha
|
|
700 |
polExpStr = ""
|
|
701 |
# We first introduce all the monomials in i alone multiplied by N^alpha.
|
|
702 |
for iPower in xrange(0, maxIdegree + 1):
|
|
703 |
if columnsWidth !=0:
|
|
704 |
polExpStr = spo_expression_as_string(iPower, iBound,
|
|
705 |
0, tBound,
|
|
706 |
0, alpha)
|
|
707 |
print "->", polExpStr
|
|
708 |
currentExpression = iVariable^iPower * nAtAlpha * iBound^iPower
|
|
709 |
currentPolynomial = pRing(currentExpression)
|
|
710 |
polynomialsList.append(currentPolynomial)
|
|
711 |
# End for iPower
|
|
712 |
# We work from p^1 * N^alpha-1 to p^alpha * N^0
|
|
713 |
for pPower in xrange(1, alpha + 1):
|
|
714 |
# First of all the p^pPower * N^(alpha-pPower) polynomial.
|
|
715 |
nAtPower /= N
|
|
716 |
if columnsWidth !=0:
|
|
717 |
polExpStr = spo_expression_as_string(0, iBound,
|
|
718 |
0, tBound,
|
|
719 |
pPower, alpha-pPower)
|
|
720 |
print "->", polExpStr
|
|
721 |
currentPolynomial = polynomialAtPower * nAtPower
|
|
722 |
polynomialsList.append(currentPolynomial)
|
|
723 |
# Exit when pPower == alpha
|
|
724 |
if pPower == alpha:
|
|
725 |
return polynomialsList
|
|
726 |
# We now introduce the mixed i^k * t^l monomials by i^m * p^n * N^(alpha-n)
|
|
727 |
for iPower in xrange(1, pIdegree + 1):
|
|
728 |
if columnsWidth != 0:
|
|
729 |
polExpStr = spo_expression_as_string(iPower, iBound,
|
|
730 |
0, tBound,
|
|
731 |
pPower, alpha-pPower)
|
|
732 |
print "->", polExpStr
|
|
733 |
currentExpression = i^iPower * iBound^iPower * nAtPower
|
|
734 |
currentPolynomial = pRing(currentExpression) * polynomialAtPower
|
|
735 |
polynomialsList.append(currentPolynomial)
|
|
736 |
# End for iPower
|
|
737 |
polynomialAtPower *= p
|
|
738 |
# End for pPower loop
|
|
739 |
return polynomialsList
|
|
740 |
# End spo_polynomial_to_proto_matrix_4
|
|
741 |
|
|
742 |
def spo_proto_to_column_matrix(protoMatrixColumns):
|
|
743 |
"""
|
|
744 |
Create a column (each row holds the coefficients for one monomial) matrix.
|
|
745 |
|
|
746 |
Parameters
|
|
747 |
----------
|
| 652 |
748 |
protoMatrixColumns: a list of coefficient lists.
|
| 653 |
749 |
"""
|
| 654 |
750 |
numColumns = len(protoMatrixColumns)
|
| ... | ... | |
| 663 |
759 |
for rowIndex in xrange(0, len(protoMatrixColumns[colIndex])):
|
| 664 |
760 |
if protoMatrixColumns[colIndex][rowIndex] != 0:
|
| 665 |
761 |
baseMatrix[rowIndex, colIndex] = \
|
| 666 |
|
protoMatrixColumns[colIndex][rowIndex] * \
|
| 667 |
|
knownMonomialsList[rowIndex](boundVar1, boundVar2)
|
|
762 |
protoMatrixColumns[colIndex][rowIndex]
|
| 668 |
763 |
return baseMatrix
|
| 669 |
764 |
# End spo_proto_to_column_matrix.
|
| 670 |
765 |
#
|
| 671 |
|
def spo_proto_to_row_matrix(protoMatrixRows, \
|
| 672 |
|
knownMonomialsList, \
|
| 673 |
|
boundVar1, \
|
| 674 |
|
boundVar2):
|
|
766 |
def spo_proto_to_row_matrix(protoMatrixRows):
|
| 675 |
767 |
"""
|
| 676 |
|
Create a row (each column holds the evaluation one monomial at boundVar1 and
|
| 677 |
|
boundVar2 values) matrix.
|
|
768 |
Create a row (each column holds the coefficients corresponding to one
|
|
769 |
monomial) matrix from the protoMatrixRows list.
|
| 678 |
770 |
|
| 679 |
771 |
Parameters
|
| 680 |
772 |
----------
|
| ... | ... | |
| 692 |
784 |
for colIndex in xrange(0, len(protoMatrixRows[rowIndex])):
|
| 693 |
785 |
if protoMatrixRows[rowIndex][colIndex] != 0:
|
| 694 |
786 |
baseMatrix[rowIndex, colIndex] = \
|
| 695 |
|
protoMatrixRows[rowIndex][colIndex] * \
|
| 696 |
|
knownMonomialsList[colIndex](boundVar1,boundVar2)
|
|
787 |
protoMatrixRows[rowIndex][colIndex]
|
| 697 |
788 |
#print rowIndex, colIndex,
|
| 698 |
789 |
#print protoMatrixRows[rowIndex][colIndex],
|
| 699 |
790 |
#print knownMonomialsList[colIndex](boundVar1,boundVar2)
|