Laboratoire de l'Informatique et du Parallélisme » Pobyso

def spo_polynomial_to_polynomials_list_5(p, alpha, N, iBound, tBound,

                                         columnsWidth=0):

    """

    From p, alpha, N build a list of polynomials use to create a base

    that will eventually be reduced with LLL.

    The bounds are computed for the coefficients that will be used to

    form the base.

    We try to introduce only one new monomial at a time, to obtain a

    triangular matrix (it is easy to compute the volume of the underlining

    latice if the matrix is triangular).

    There are many possibilities to introduce the monomials: our goal is also 

    to introduce each of them on the diagonal with the smallest coefficient.

    The method depends on the structure of the polynomial. Here it is adapted

    to the a_n*i^n + ... + a_1 * i - t + b form.     

    Parameters

    ----------

    p: the (bivariate) polynomial;

    alpha:

    N:

    iBound:

    tBound:

    columsWidth: if == 0, no information is displayed, otherwise data is 

                 printed in colums of columnsWitdth width.

    """

    pRing = p.parent()

    polynomialsList = []

    pVariables = p.variables()

    iVariable = pVariables[0]

    tVariable = pVariables[1]

    polynomialAtPower = copy(p)

    currentPolynomial = pRing(1)

    pIdegree = p.degree(iVariable)

    pTdegree = p.degree(tVariable)

    maxIdegree = pIdegree * alpha

    currentIdegree = currentPolynomial.degree(iVariable)

    nAtAlpha = N^alpha

    nAtPower = nAtAlpha

    polExpStr = ""

    # We first introduce all the monomials in i alone multiplied by N^alpha.

    for iPower in xrange(0, maxIdegree + 1):

        if columnsWidth !=0:

            polExpStr = spo_expression_as_string(iPower, iBound,

                                                 0, tBound, 

                                                 0, alpha)

            print "->", polExpStr

        currentExpression = iVariable^iPower * nAtAlpha * iBound^iPower

        currentPolynomial = pRing(currentExpression)

        polynomialsList.append(currentPolynomial)

    # End for iPower

    # We work from p^1 * N^alpha-1 to p^alpha * N^0

    for pPower in xrange(1, alpha + 1):

        # First of all the p^pPower * N^(alpha-pPower) polynomial.

        nAtPower /= N

        if columnsWidth !=0:

            polExpStr = spo_expression_as_string(0, iBound,

                                                 0, tBound,

                                                 pPower, alpha-pPower)

            print "->", polExpStr

        currentPolynomial = polynomialAtPower * nAtPower

        polynomialsList.append(currentPolynomial)

        # Exit when pPower == alpha

        if pPower == alpha:

            return polynomialsList

        for iPower in xrange(1, pIdegree + 1):

            iCurrentPower = pIdegree + iPower

            for tPower in xrange(pPower-1, 0, -1):

                print "tPower:", tPower

                if columnsWidth != 0:

                    polExpStr = spo_expression_as_string(iCurrentPower, iBound,

                                                         tPower, tBound, 

                                                         0, alpha)

                    print "->", polExpStr

                currentExpression = i^iCurrentPower * iBound^iCurrentPower * t^tPower * tBound^tPower *nAtAlpha 

                currentPolynomial = pRing(currentExpression)

                polynomialsList.append(currentPolynomial)

                iCurrentPower += pIdegree 

            # End for tPower 

        # We now introduce the mixed i^k * t^l monomials by i^m * p^n * N^(alpha-n)

            if columnsWidth != 0:

                polExpStr = spo_expression_as_string(iPower, iBound,

                                                     0, tBound, 

                                                     pPower, alpha-pPower)

                print "->", polExpStr

            currentExpression = i^iPower * iBound^iPower * nAtPower

            currentPolynomial = pRing(currentExpression) * polynomialAtPower

            polynomialsList.append(currentPolynomial) 

        # End for iPower

        polynomialAtPower *= p  

    # End for pPower loop

    return polynomialsList 

# End spo_polynomial_to_proto_matrix_5