Last active
February 25, 2021 12:04
-
-
Save TristanVaccon/1eea714c0ae80cba427de0c5e1bcdcd1 to your computer and use it in GitHub Desktop.
Tate FGLM
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from copy import* | |
| ################################## | |
| # Linear preliminary # | |
| # # | |
| ################################## | |
| def diagonalisable_in_glnZp_with_blocks_growing_valuation_random_eigenvalues(dim=6,blocks=[2,1,3],p=5,prec=10): | |
| R = Zp(p,prec) | |
| diag0 = [[R.random_element() for i in range(blocks[u])] for u in range(len(blocks))] | |
| diag = sum([[p**(u-diag0[u][i].valuation())*diag0[u][i] for i in range(blocks[u])] for u in range(len(blocks))],[]) | |
| D = diagonal_matrix([QQ(ZZ(a)) for a in diag]) | |
| U = MatrixSpace(ZZ,dim,dim).random_element() | |
| while U.det().valuation(p) != 0: | |
| U = MatrixSpace(ZZ,dim,dim).random_element() | |
| A = U*D*U**(-1) | |
| Rp = MatrixSpace(Zp(p,prec),dim,dim) | |
| A=Rp(A) | |
| return A | |
| def SNF_rec_valuated_approx(M): | |
| # Return P,P^(-1), Delta, Q, Q^(-1) so as PMQ = Delta and Delta is the approximate Smith Normal Form of M. | |
| n = M.nrows() | |
| m = M.ncols() | |
| K = M.base_ring() | |
| pc = K.gen().precision_relative() | |
| Mtilde = copy(M) | |
| P = MatrixSpace(K,n,n)(1) | |
| Pinv = MatrixSpace(K,n,n)(1) | |
| Q = MatrixSpace(K,m,m)(1) | |
| Qinv = MatrixSpace(K,m,m)(1) | |
| if n*m == 0: | |
| return MatrixSpace(K,n,n)(1),MatrixSpace(K,n,n)(1),M,MatrixSpace(K,m,m)(1),MatrixSpace(K,m,m)(1) | |
| #looking for the coefficient with minimal valuation | |
| min_index = [0,0] | |
| min_val = M[0,0].valuation() | |
| for j in range(m): | |
| for i in range(n): | |
| if M[i,j].valuation()<min_val : | |
| min_index = [i,j] | |
| min_val = M[i,j].valuation() | |
| i = min_index[0] | |
| j = min_index[1] | |
| if M[i,j].is_zero(): | |
| return P,Pinv,Mtilde,Q,Qinv | |
| #permutation of rows to put this coefficient on first row | |
| l = [u for u in range(1,n+1)] | |
| l[0] = i+1 | |
| l[i] = 1 | |
| Permrow = Permutation(l).to_matrix() | |
| P = Permrow * P | |
| Pinv = Pinv*Permrow | |
| Mtilde = Permrow * Mtilde | |
| #permutation of columns to put this coefficient on first column | |
| l = [u for u in range(1,m+1)] | |
| l[0] = j+1 | |
| l[j] = 1 | |
| Permcol = Permutation(l).to_matrix() | |
| Q = Q * Permcol | |
| Qinv = Permcol*Qinv | |
| Mtilde = Mtilde*Permcol | |
| #dilating for normalization of Mtilde | |
| x = Mtilde[0,0] | |
| #a = K((x/(K.uniformizer()**(x.valuation()))).lift()) | |
| #a = x.unit_part() | |
| a = K((x/(K.uniformizer()**(x.valuation()))).lift_to_precision(pc)) | |
| ainv = a.inverse_of_unit() | |
| Pdilat = MatrixSpace(K,n,n)(1) | |
| Pdilat[0,0] = ainv | |
| Pdilatinv = MatrixSpace(K,n,n)(1) | |
| Pdilatinv[0,0] = a | |
| Mtilde = Pdilat*Mtilde | |
| P = Pdilat*P | |
| Pinv = Pinv*Pdilatinv | |
| #pivoting | |
| for ir in range(1,n): | |
| coeff = -Mtilde[ir,0]/(K.uniformizer()**(x.valuation())) | |
| if coeff != 0: | |
| coeff.lift_to_precision(pc+coeff.valuation()) | |
| else: | |
| coeff.lift_to_precision(pc) | |
| Mtilde.add_multiple_of_row(ir, 0, coeff) | |
| P.add_multiple_of_row(ir, 0, coeff) | |
| Pinv.add_multiple_of_column(0,ir,-coeff) | |
| for jr in range(1,m): | |
| coeff = -Mtilde[0,jr]/(K.uniformizer()**(x.valuation())) | |
| if coeff != 0: | |
| coeff.lift_to_precision(pc+coeff.valuation()) | |
| else: | |
| coeff.lift_to_precision(pc) | |
| Mtilde.add_multiple_of_column(jr, 0, coeff) | |
| Q.add_multiple_of_column(jr, 0, coeff) | |
| Qinv.add_multiple_of_row(0,jr,-coeff) | |
| #recursion | |
| P2,P2inv,Mtilde2,Q2,Q2inv = SNF_rec_valuated_approx(Mtilde[range(1,n),range(1,m)]) | |
| #augmentation | |
| Mtilde[range(1,n),range(1,m)] = Mtilde2 | |
| P2augm = MatrixSpace(K,n,n)(1) | |
| P2augminv = MatrixSpace(K,n,n)(1) | |
| P2augm[range(1,n),range(1,n)] = copy(P2) | |
| P2augminv[range(1,n),range(1,n)] = copy(P2inv) | |
| Q2augm = MatrixSpace(K,m,m)(1) | |
| Q2augminv = MatrixSpace(K,m,m)(1) | |
| Q2augm[range(1,m),range(1,m)] = copy(Q2) | |
| Q2augminv[range(1,m),range(1,m)] = copy(Q2inv) | |
| P = P2augm*P | |
| Pinv = Pinv*P2augminv | |
| Q = Q*Q2augm | |
| Qinv = Q2augminv*Qinv | |
| return P,Pinv,Mtilde,Q,Qinv | |
| def SNF_precisee(P0,Pinv0,M,Q0,Qinv0): | |
| # Return P,P^(-1), Delta, Q, Q^(-1) so as PMQ = Delta and Delta is the Smith Normal Form of M. | |
| #Beware : we demand full-rank... | |
| n = M.nrows() | |
| m = M.ncols() | |
| K = M.base_ring() | |
| Mtilde = copy(M) | |
| P = copy(P0) | |
| Pinv = copy(Pinv0) | |
| Q = copy(Q0) | |
| Qinv = copy(Qinv0) | |
| t = min(n,m) | |
| success = True | |
| for i in range(t): | |
| x = Mtilde[i,i] | |
| if x.is_zero(): | |
| return P,Pinv,Mtilde,Q,Qinv,False | |
| a = x.lift()/x | |
| ainv=x/(x.lift()) | |
| Pdilat = MatrixSpace(K,n,n)(1) | |
| Pdilat[i,i] = a | |
| Pdilatinv = MatrixSpace(K,n,n)(1) | |
| Pdilatinv[i,i] = ainv | |
| Mtilde = Pdilat*Mtilde | |
| P = Pdilat*P | |
| Pinv = Pinv*Pdilatinv | |
| Mtilde[i,i] = Mtilde[i,i].lift() | |
| if t == m: | |
| for j in range(n): | |
| if j != i: | |
| coeff = -Mtilde[j,i]/(Mtilde[i,i]) | |
| Mtilde.add_multiple_of_row(j, i, coeff) | |
| P.add_multiple_of_row(j, i, coeff) | |
| Pinv.add_multiple_of_column(i,j,-coeff) | |
| Mtilde[j,i]=K(0) | |
| else: | |
| for j in range(m): | |
| if j != i: | |
| coeff = -Mtilde[i,j]/(Mtilde[i,i]) | |
| Mtilde.add_multiple_of_column(j, i, coeff) | |
| Q.add_multiple_of_column(j, i, coeff) | |
| Qinv.add_multiple_of_row(i,j,-coeff) | |
| Mtilde[i,j]=K(0) | |
| return P,Pinv,Mtilde,Q,Qinv,True | |
| def SNF_totale(M): | |
| P,Pinv,Mtilde,Q,Qinv = SNF_rec_valuated_approx(M) | |
| P,Pinv,Delta,Q,Qinv,success = SNF_precisee(P,Pinv,Mtilde,Q,Qinv) | |
| return P,Pinv,Delta,Q,Qinv,success | |
| def my_kernel_basis_from_SNF(Delta,Q): | |
| #compute the numerical kernel and outputs an orthonormal basis of it | |
| i=0 | |
| n = min(Delta.nrows(), Delta.ncols()) | |
| while (i<n and not(Delta[i,i].is_zero())): | |
| i+=1 | |
| return i, [Q.column(j) for j in range(i,Delta.ncols())] | |
| def my_kernel_basis(M): | |
| #compute the numerical kernel and outputs an orthonormal basis of it | |
| P,Pinv,Mtilde,Q,Qinv,success = SNF_totale(M) | |
| i, ker_col = my_kernel_basis_from_SNF(Mtilde,Q) | |
| #return Matrix(M.base_ring(),M.nrows(), len(ker_col),ker_col) | |
| return(ker_col) | |
| def my_image_basis_from_SNF(Delta,Pinv): | |
| #From the SNF, compute the numerical image and outputs a basis of it | |
| i=0 | |
| n = min(Delta.nrows(), Delta.ncols()) | |
| while (i<n and not(Delta[i,i].is_zero())): | |
| i+=1 | |
| return i, Matrix([Delta[j,j]*Pinv.column(j) for j in range(i)]).transpose() | |
| def my_image_basis(M): | |
| #compute the numerical image and outputs a basis of it | |
| P,Pinv,Mtilde,Q,Qinv,success = SNF_totale(M) | |
| i, im_mat = my_image_basis_from_SNF(Mtilde,Pinv) | |
| #return Matrix(M.base_ring(),M.nrows(), len(ker_col),ker_col) | |
| return(im_mat) | |
| def my_orth_image_basis_from_SNF(Delta,Pinv): | |
| #From the SNF, compute the numerical image and outputs a basis of it | |
| i=0 | |
| n = min(Delta.nrows(), Delta.ncols()) | |
| while (i<n and not(Delta[i,i].is_zero())): | |
| i+=1 | |
| if i == 0: | |
| return(0,Matrix(Delta.parent().base_ring(),Delta.nrows(),0)) | |
| return i, Matrix([Pinv.column(j) for j in range(i)]).transpose() | |
| def my_orth_image_basis(M): | |
| #compute the numerical image and outputs a basis of it | |
| P,Pinv,Mtilde,Q,Qinv,success = SNF_totale(M) | |
| i, im_col = my_orth_image_basis_from_SNF(Mtilde,Pinv) | |
| #return Matrix(M.base_ring(),M.nrows(), len(ker_col),ker_col) | |
| return(im_col) | |
| def quotient_computation(Z,B): | |
| #Computes a basis of the quotient of B by Z | |
| #We assume Z is orthonormal | |
| p = Z.parent().base_ring().gen() | |
| vv = min([u.valuation() for u in B.coefficients()]) | |
| a = Z.ncols() | |
| b = B.ncols() | |
| P,Pinv,Delta,Q,Qinv,success = SNF_totale(((p**vv)*Z).augment(B)) | |
| # print("mon test du quotient") | |
| # print_val(Delta) | |
| my_quo = [Delta[j,j]*Pinv.column(j) for j in range(a,min(a+b,Z.nrows())) if Delta[j,j] !=0] | |
| return(Matrix(my_quo).transpose()) | |
| def my_writing_in_basis_from_SNF(P,Pinv,Mtilde,Q,Qinv,Y): | |
| #Solve Pinv Mtilde Qinv X = Y | |
| #We assume there is a solution | |
| #We assume Mtilde has less columns than rows | |
| n = Mtilde.nrows() | |
| YY = P*Y | |
| for i in range(n): | |
| if not(Mtilde[i,i].is_zero()): | |
| YY.set_row_to_multiple_of_row(i,i,Mtilde[i,i]**(-1)) | |
| ZZ = YY.submatrix(0,0,Mtilde.ncols(),Y.ncols()) | |
| return(Q*ZZ) | |
| def print_val(Mat): | |
| Mval = MatrixSpace(ZZ,Mat.nrows(),Mat.ncols())(0) | |
| for i in range(Mat.nrows()): | |
| for j in range(Mat.ncols()): | |
| if Mat[i,j] != 0: | |
| Mval[i,j]=Mat[i,j].valuation() | |
| else: | |
| Mval[i,j]=-8 | |
| print(Mval) | |
| ################################## | |
| # FGLM preliminary # | |
| # (classical case) # | |
| ################################## | |
| def list_monom(P,d): | |
| r""" | |
| Return an ordered list of the monomials of P of degree d | |
| INPUT: | |
| - ``P`` -- a polynomial ring | |
| - ``d`` -- an integer | |
| OUTPUT: | |
| The list of monomials in P of degree d, ordered from the biggest to the smallest according to the monomial ordering on P | |
| EXAMPLES:: | |
| sage: S.<x,y,z>=Qp(5)[] | |
| sage: from sage.rings.polynomial.padics.toy_MatrixF5 import list_monom | |
| sage: list_monom(S,2) | |
| [x^2, x*y, y^2, x*z, y*z, z^2] | |
| """ | |
| if d == 0: | |
| return [P(1)] | |
| l1 = [ a for a in P.gens()] | |
| if d == 1: | |
| return l1 | |
| ld1 = list_monom(P,d-1) | |
| ld = [[x*u for x in l1] for u in ld1] | |
| ld = sum(ld,[]) | |
| s = [] | |
| for i in ld: | |
| if i not in s: | |
| s.append(i) | |
| s.sort() | |
| s.reverse() | |
| return s | |
| def coefficient_precis(f,v): | |
| mon = f.monomials() | |
| if mon.count(v)>0: | |
| return f.coefficients()[mon.index(v)] | |
| else: | |
| return 0 | |
| def Stair(G,D=None): | |
| # Compute the monomials below the stairs defined by the Groebner basis G | |
| # We demand that Ideal(G) is of dimension 0 | |
| #D is a bound on the degree of elements of the Stair | |
| P = G[0].parent() | |
| LG = [g.lm() for g in G] | |
| if D is not None: | |
| dmax = D-1 | |
| else: | |
| dmax = sum([g.degree() for g in LG]) | |
| stair = [] | |
| for d in range(dmax+1): | |
| l = list_monom(P,d) | |
| for mon in l: | |
| divide = false | |
| for lg in LG: | |
| if P.monomial_divides(lg,mon): | |
| divide = true | |
| break | |
| if not(divide): | |
| stair.append(mon) | |
| stair.sort() | |
| return stair | |
| def multiplication_matrices(G,D=None): | |
| # Compute the multiplication matrices for G | |
| # We demand that Ideal(G) is of dimension 0 | |
| P = G[0].parent() | |
| R = P.base_ring() | |
| n = len(P.gens()) | |
| LG = [g.lm() for g in G] | |
| stair = Stair(G,D) | |
| multstair = stair + sum([[a*mon for a in P.gens()] for mon in stair],[]) | |
| multstair = set(multstair) | |
| multstair = [wxc for wxc in multstair] | |
| multstair.sort() | |
| dim = len(stair) | |
| T = [Matrix(R,dim,dim) for i in range(n)] | |
| for mon in multstair: | |
| divofmon = [i for i in range(n) if P.monomial_divides(P.gens()[i],mon)] | |
| #First Case | |
| if mon in stair: | |
| for i in divofmon: | |
| u=P.gens()[i] | |
| T[i][stair.index(mon),stair.index(P.monomial_quotient(mon,u))]=R(1) | |
| else: | |
| if LG.count(mon)>0: | |
| #Second Case | |
| j = LG.index(mon) | |
| h=mon-G[j] | |
| for i in divofmon: | |
| u=P.gens()[i] | |
| if stair.count(P.monomial_quotient(mon,u))>0: | |
| for v in stair: | |
| T[i][stair.index(v),stair.index(P.monomial_quotient(mon,u))]=coefficient_precis(h,v) | |
| else: | |
| #Third Case | |
| #Find a divisor in the border: mon = x_i * v with v in the border | |
| my_div_var_1 = None | |
| for j in divofmon: | |
| if not(P.monomial_quotient(mon,P.gens()[j]) in stair): | |
| my_div_var_1 = j | |
| break | |
| v = P.monomial_quotient(mon,P.gens()[my_div_var_1]) | |
| #Find the reduction of v (by writing it as v = x_l * e) | |
| divofv= [i for i in range(n) if P.monomial_divides(P.gens()[i],v)] | |
| my_div_var_2 = None | |
| for l in divofv: | |
| if P.monomial_quotient(mon,P.gens()[l]) in stair: | |
| my_div_var_2 = l | |
| break | |
| V = T[my_div_var_2][range(dim),stair.index(P.monomial_quotient(v,P.gens()[my_div_var_2]))] | |
| W = T[my_div_var_1]*V | |
| for i in divofmon: | |
| u=P.gens()[i] | |
| if stair.count(P.monomial_quotient(mon,u))>0: | |
| T[i][range(dim),stair.index(P.monomial_quotient(mon,u))]=W | |
| return T | |
| def my_update(s,Q,ll): | |
| l = copy(ll) | |
| delta=Q.nrows() | |
| i0=s | |
| for i in range(s, delta): | |
| if l[i,0] != 0: | |
| i0 = i | |
| break | |
| Q.swap_rows(s,i0) | |
| l.swap_rows(s,i0) | |
| Q.set_row_to_multiple_of_row(s,s,l[s,0]**(-1)) | |
| l.set_row_to_multiple_of_row(s,s,l[s,0]**(-1)) | |
| for j in range(s+1,delta): | |
| Q.add_multiple_of_row(j,s,-l[j,0]) | |
| l.add_multiple_of_row(j,s,-l[j,0]) | |
| return(Q) | |
| def fglm_strat_for_new_stair(T,P2, representation_of_one): | |
| # print("test initial des matrices") | |
| # print(T) | |
| R = P2.base_ring() | |
| n = len(P2.gens()) | |
| new_lm =[] | |
| degre = T[0].nrows() | |
| V = Matrix(R,degre,1) | |
| V[range(degre),0] = representation_of_one | |
| B2=[P2(1)] | |
| L = [P2.gens()[i] for i in range(n)] | |
| L.sort() | |
| Ldict = {P2.gens()[i]:(0,i) for i in range(n)} | |
| Q = MatrixSpace(R,degre,degre)(1) | |
| #Q.swap_rows(0,representation_of_one) | |
| Q = my_update(0,Q,representation_of_one) | |
| while len(L)>0: | |
| m = L.pop(0) | |
| j = Ldict[m][0] | |
| i = Ldict[m][1] | |
| del Ldict[m] | |
| v = T[i]*V[range(degre),j] | |
| s = len(B2) | |
| lamb = Q*v | |
| if lamb[range(s,degre),0].is_zero(): | |
| new_lm.append(m) | |
| else: | |
| B2.append(B2[j]*P2.gens()[i]) | |
| V2 = Matrix(R,degre,s+1) | |
| V2[range(degre),range(s)] = V | |
| V2[range(degre),s] = v | |
| V = V2 | |
| L2 = [B2[s]*P2.gens()[l] for l in range(n)] | |
| L = L+L2 | |
| L = set(L) | |
| L = [ l for l in L] | |
| L.sort() | |
| for l in range(n): | |
| Ldict[B2[s]*P2.gens()[l]]=(s,l) | |
| Q = my_update(s,Q,lamb) | |
| Lcopy = [aa for aa in L] | |
| for mon in L: | |
| for g in new_lm: | |
| if P2.monomial_divides(g,mon): | |
| Lcopy.remove(mon) | |
| break | |
| L = [bb for bb in Lcopy] | |
| return(new_lm,B2) | |
| ################################## | |
| # Algo 1 : Big # | |
| # # | |
| ################################## | |
| def big_s_factor(P,s): | |
| #compute the Big_s factor of P, i.e. the maximal factor | |
| # with roots of valuation < s | |
| """ | |
| EXAMPLES:: | |
| sage: K = Qp(p,100) | |
| sage: A = PolynomialRing(K, 'x') | |
| sage: x = A.gen() | |
| sage: P = (x-1/K(p)**2)*(x-1/K(p))**3*(x-p)**2*(x-2*p) | |
| sage: Q = big_s_factor(P,0) | |
| sage:(Q - (x-1/K(p)**2)*(x-1/K(p))**3) | |
| sage:O(7^100)*x^4 + O(7^98)*x^3 + O(7^97)*x^2 + O(7^96)*x + O(7^95) | |
| """ | |
| l = set(P.newton_slopes()) | |
| Q = prod([P.factor_of_slope(u) for u in l if u<s]) | |
| return(Q) | |
| def big_s_subspace(M,s): | |
| #compute the Big_s subspace of M, i.e. the maximal subspace | |
| #with eigenvalues of valuation < s | |
| """ | |
| EXAMPLES:: | |
| sage: p = 7 | |
| sage: prec = 100 | |
| sage: M = diagonalisable_in_glnZp_with_blocks_growing_valuation_random_eigenvalues(6,[2,1,3],p,prec) | |
| sage: S = big_s_subspace(M, 2) | |
| sage: S.ncols() | |
| 3 | |
| """ | |
| chi = M.characteristic_polynomial('x',"df") | |
| chi_big = big_s_factor(chi,s) | |
| if chi.parent()(chi_big).degree() == 0: | |
| return Matrix(M.parent().base_ring(),M.nrows(),0) | |
| U = chi_big(M) | |
| S = Matrix(my_kernel_basis(U)).transpose() | |
| return(S) | |
| ################################## | |
| # # | |
| # Algo 2 : Saturation # | |
| # # | |
| ################################## | |
| def PowerSumIteration(listeA,U,w): | |
| # Computes sum_{i_j <2^w} A_1^{i_1}\times \dots \times A_n^{i_n} (Span(U)) | |
| # We assume the matrices A_i's are commuting | |
| """ | |
| EXAMPLES:: | |
| sage: p = 7 | |
| sage: prec = 100 | |
| sage: A1 = diagonalisable_in_glnZp_with_blocks_growing_valuation_random_eigenvalues(6,[2,1,3],p,prec) | |
| sage: A2 = A1*A1*A1 | |
| sage: U = Matrix(A1.base_ring(),6,2,[1,0,0,0,0,p,0,0,0,0,0,0]) | |
| sage: D = PowerSumIteration([A1, A2],U,4) | |
| """ | |
| D = U | |
| n = len(listeA) | |
| for i in range(n): | |
| M = listeA[i] | |
| for k in range(w): | |
| temp = D.augment(M*D) | |
| D = my_image_basis(temp) | |
| M = M*M | |
| return(D) | |
| ################################## | |
| # # | |
| # Algo 5 : New Mult Matrix # | |
| # # | |
| ################################## | |
| def new_mult_mat(listT,stair,u): | |
| delta = len(stair) | |
| n = len(listT) | |
| p = listT[0].base_ring().gen() | |
| #computing the tilde{T}_i | |
| listTtilde = [] | |
| for i in range(n): | |
| listTtilde.append(p**(u[i])*listT[i]) | |
| #computing B^0 | |
| B0 = listT[0].parent()(1) | |
| for i in range(delta): | |
| vv = sum([u[j]*stair[i].degrees()[j] for j in range(n)]) | |
| B0[i,i] = p**vv | |
| #Computing a basis of the sum of the big's | |
| Z = Matrix(listT[0].base_ring(),delta,0) | |
| for i in range(n): | |
| BTi = big_s_subspace(listT[i],u[i]) | |
| Z = Z.augment(BTi) | |
| Z = my_orth_image_basis(Z) | |
| if Z.ncols()==delta: | |
| return([],None) | |
| C = quotient_computation(Z,B0) | |
| # print("test ici") | |
| # print(Z.ncols()) | |
| # print(C.ncols()) | |
| D = PowerSumIteration(listTtilde,C, ceil(log(delta))+1) | |
| # print(D.ncols()) | |
| D = quotient_computation(Z,D) | |
| d = D.ncols() | |
| # print(d) | |
| P,Pinv,Mtilde,Q,Qinv,success = SNF_totale(Z.augment(D)) | |
| #Writing 1 in basis D | |
| # one_in_D = None | |
| # for j in range(D.ncols()): | |
| # if D[0,j] == 1 and D[range(1, D.nrows()),j]==0: | |
| # one_in_D = j | |
| # break | |
| one_in_B = Matrix(listT[0].base_ring(),delta,1) | |
| one_in_B[0,0]=1 | |
| one_in_B = quotient_computation(Z,one_in_B) | |
| one_in_D = my_writing_in_basis_from_SNF(P,Pinv,Mtilde,Q,Qinv,one_in_B) | |
| one_in_D = one_in_D.submatrix(delta-d,0,d,1) | |
| #Computing the normalized multiplication matrices in D | |
| # print("on est là") | |
| # print(one_in_D) | |
| listS = [] | |
| for i in range(n): | |
| Y = listTtilde[i]*D | |
| XX = my_writing_in_basis_from_SNF(P,Pinv,Mtilde,Q,Qinv,Y) | |
| X = XX.submatrix(delta-d,0,d,d) | |
| listS.append(X) | |
| return(listS, one_in_D) | |
| ################################## | |
| # # | |
| # Algo 6 : Final FGLM # | |
| # # | |
| ################################## | |
| def algo6(listT,u, A, representation_of_one): | |
| #We assume that the matrices in listT are given in a K^0 basis so that we can reduce them | |
| #mod p | |
| #A is the target Tate algebra | |
| if len(listT)==0: | |
| return([A(1)]) | |
| p = listT[0].base_ring().gen() | |
| delta = listT[0].nrows() | |
| n = len(listT) | |
| R = listT[0].base_ring() | |
| kk = R.residue_field() | |
| Matk = MatrixSpace(kk,delta,delta) | |
| def to_A(mon): | |
| d = mon.exponents()[0] | |
| return A({d:1}) | |
| listTred = [Matk(T) for T in listT] | |
| Pred = PolynomialRing(kk, 'z',n, order = A.term_order()) | |
| # print("mon nouveau test") | |
| # print(delta) | |
| # print(representation_of_one.nrows()) | |
| # print(representation_of_one) | |
| new_lm, B2 = fglm_strat_for_new_stair(listTred,Pred, representation_of_one) | |
| # print("resultat modulaire") | |
| # print(new_lm) | |
| # print(B2) | |
| #compute M and N using listT | |
| B2.sort() | |
| M = Matrix(R,delta,delta) | |
| M[range(delta),0]=representation_of_one | |
| # print("M intermediaire") | |
| # print(M) | |
| N = Matrix(R,delta, len(new_lm)) | |
| listT_denormalized = [p**(-u[i]) *listT[i] for i in range(n) ] | |
| for uu in range(delta): | |
| for i in range(n): | |
| mon = Pred.gens()[i]*B2[uu] | |
| if mon in new_lm: | |
| ii = new_lm.index(mon) | |
| N[range(delta),ii] = listT_denormalized[i]*M[range(delta),uu] | |
| if mon in B2: | |
| ii = B2.index(mon) | |
| M[range(delta),ii] = listT_denormalized[i]*M[range(delta),uu] | |
| # print("derniers calculs") | |
| # print(M) | |
| # print(N) | |
| Q = M**(-1)*N | |
| # Compute G | |
| G= [] | |
| for j in range(len(new_lm)): | |
| g = to_A(new_lm[j]) | |
| g = g -sum([Q[i,j]*to_A(B2[i]) for i in range(delta)]) | |
| G.append(g) | |
| return(G) | |
| ################################################# | |
| # # | |
| # Tate FGLM (from multiplication matrices) # | |
| # # | |
| ################################################# | |
| def total_FGLM_from_multiplication_matrices(listT,B,u,A): | |
| listS, one_in_D = new_mult_mat(listT,B,u) | |
| G=algo6(listS,u, A, one_in_D) | |
| return(G) | |
| print("#####################################################################") | |
| print("# #") | |
| print("# Toy implementation of the FGLM algorithms for Tate Algebras #") | |
| print("# #") | |
| print("#####################################################################") | |
| print("(mostly the algorithms of Sections 2 and 4 over Q_p)") | |
| print("") | |
| print("%%%%%%%%%%%%%%%%%") | |
| print("%A first example%") | |
| print("%%%%%%%%%%%%%%%%%") | |
| K = Qp(2,100) | |
| AA = PolynomialRing(K,['x','y'],2) | |
| x = AA.gens()[0] | |
| y = AA.gens()[1] | |
| G0 = [x**2-K(1/2)*y**2,y**3-K(1/2)*x] | |
| print("We start with the following GB defining an ideal I over Qp[x,y]:") | |
| print(G0) | |
| print("We aim at computing a GB for I in the Tate Algebra Qp{x,y ; 0,0}.") | |
| listT = multiplication_matrices(G0) | |
| listT = [u for u in listT] | |
| print("") | |
| print("Here are the multiplication matrices for the ideal over Qp[x,y].") | |
| print("Please note that the linear dimension of the quotient is 6.") | |
| print("Multiplication by x:") | |
| print(listT[0]) | |
| print("Multiplication by y:") | |
| print(listT[1]) | |
| B = Stair(G0) | |
| u = [0,0] | |
| A = TateAlgebra(K, names=('x1','y1')) | |
| listS, one_in_D = new_mult_mat(listT,B,u) | |
| print("") | |
| print("Here are the new multiplication matrices.") | |
| print("Please note that the dimension of the new quotient is 2") | |
| print("Multiplication by x:") | |
| print(listS[0]) | |
| print("Multiplication by y:") | |
| print(listS[1]) | |
| G = algo6(listS,u, A, one_in_D) | |
| #G = total_FGLM_from_multiplication_matrices(listT,B,u,A) | |
| print("") | |
| print("Finally, here is the new Gröbner basis in the Tate Algebra Qp{x,y ; 0,0}") | |
| print(G) | |
| print("%%%%%%%%%%%%%%%%%%") | |
| print("%A second example%") | |
| print("%%%%%%%%%%%%%%%%%%") | |
| K = Qp(2,10) | |
| AA = PolynomialRing(K,['x','y'],2) | |
| x = AA.gens()[0] | |
| y = AA.gens()[1] | |
| G0 = [x+K(1/2)*y,y**2+K(16)] | |
| print("We start with the following GB defining an ideal I over Qp[x,y]:") | |
| print(G0) | |
| print("We aim at computing a GB for I in the Tate Algebra Qp{x,y ; 0,2}.") | |
| listT = multiplication_matrices(G0) | |
| listT = [u for u in listT] | |
| print("") | |
| print("Here are the multiplication matrices for the ideal over Qp[x,y].") | |
| print("Please note that the linear dimension of the quotient is 2.") | |
| print("Multiplication by x:") | |
| print(listT[0]) | |
| print("Multiplication by y:") | |
| print(listT[1]) | |
| B = Stair(G0) | |
| u = [0,2] | |
| A = TateAlgebra(K,log_radii=u, names=('x1','y1')) | |
| x1 = A.gens()[0] | |
| y1 = A.gens()[1] | |
| listS, one_in_D = new_mult_mat(listT,B,u) | |
| print("") | |
| print("Here are the new multiplication matrices.") | |
| print("Please note that the dimension of the new quotient is 2") | |
| print("Multiplication by x:") | |
| print(listS[0]) | |
| print("Multiplication by p^2y:") | |
| print(listS[1]) | |
| G = algo6(listS,u, A, one_in_D) | |
| #G = total_FGLM_from_multiplication_matrices(listT,B,u,A) | |
| print("") | |
| print("Finally, here is the new Gröbner basis in the Tate Algebra Qp{x,y ; 0,2}") | |
| print(G) | |
| # G2 = ideal([x1+K(1/2)*y1,y1**2+K(16)]).groebner_basis() | |
| # print(G2) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment