Révision 77 pobysoPythonSage/src/sageSLZ/sagePolynomialOperations.sage

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
  
    
        print    


  		





  140
  287
  
    
# End spo_add_polynomial_coeffs_to_matrix


  		





  141
  288
  
    

  		












Formats disponibles :
  Unified diff