The Fast Algorithms From Algebraic Sets To Monomial Bases Of Quotient Ring

In this paper, we mainly introduction three fast algorithms which are fromalgebraic sets to monomial bases of quotient ring with respect to lex order : algo-rithm MB, algorithm of constructΔset, and the Lex game algorithm. Then weanalyze and compare them from the following aspects : basis of the algorithms,steps of the algorithms, complexity of the algorithms and so on.Let is a finite subset .I(P) is the vanishing ideal of P. The threealgorithms in our text is all begin with algebraic sets P, do not compute theGro¨bner bases of I(P), but construct the monomial bases of F/I(P) immedi-ately:or the index set of monomial bases:1995,L.Cerlienco and M.Mureddu first proposed an algorithm by meansof combinatorial method– algorithm MB.Let ;For 1≤s≤n, define following projection: is assumed to be emptysequence);With respect to the lex order of , algorithm MB is :Given a list: , determine an ordered set .MB1.[Initialize]Set (in the beginning the coordinates of all the elements of are zero)MB2.[Put the first i points of the list inSetMB3.[Find which coordinate of di+1 has to be changed,say di+1,s]Set(s - 1 is the length of the longest initial segment shared by Pi+1 and somepoints P_j∈Q. if s > 1,then in successive steps this value decreases)MB4.[Find the points that determine the sth coordinate of di+1]Set E←{j|P_j∈Q,Ï€_s-1(P_j) =Ï€_s-1(P_i+1),Ï€^s(d_j) =Ï€^s(d_i+1)}.(E contains the indices of the points of Q which have the first s - 1 coor-dinates equal to those of Pi+1 and whose corresponding elements in have then - s rightmost coordinates equal to those of d_i+1. E is always non-empty.)MB5.[Assign the value to the sth coordinate of d_i+1]Set d_i+1,s←(1 + max{d_i+1,s|j∈E}).MB6.[Did you determine the first coordinate of di+1?]If s > 1MB6.1.[Find the points that determine another coordinate of di+1]Set Q←{P_j|1≤j≤i,Ï€_s-1(d_j) =Ï€_s-1(d(i+1)) = (d_i+1,s,...,d_i+1,n)}.(Q contains the points of different from P_i+1 whose corresponding ele-ments in have the n - s + 1 rightmost coordinates equal to those of d_i+1)MB6.2.[Is Q empty ?]If ,return to step MB3.MB7.[Increase i]Set i←i + 1.If i < N,return to step MB2.MB8.[Done] Terminate the algorithm.The following theorem proof the correctness of the algorithm MB :Theorem 1: is a monomial linear basis for with respect to the lexorder of .Following the algorithm MB, some people proposed other similar algo-rithms from different angles.2003, Shuhong Gao,VirG'?nia M.Rodrigues and Jeffrey Stroomer [8] studythe relationship between algebraic sets, and certain Gro¨bner bases of the van-ishing ideal defined by algebraic sets. Furthermore, they proposed an algorithmof construct monomial bases–algorithm of constructΔset.The main basis of the algorithm of constructΔset is :Theorem 2: Let be lower sets. For any point a = (a₂,...,a_n)∈N^n-1, letδ(a) denote the number of lower setsΔ_i that contain a. Then tomerge theΔ_i, 1≤i≤k is to form the lower setΔconsisting of all points(j,a₂,...,a_n), where 0≤j≤δ(a₂,...,a_n).Then with respect to the lex order of ,the algorithmto constructΔ(P) is the following :(1) Construct T(P) from P.(2) If n = 1, thenΔ(P) is {0, 1,..., |P| - 1}.(3) Otherwise, let the subtrees of the root node of T(P) is S₁,...,S_k, andassume this algorithm has recursively constructed eachΔ(P(S_i)). ThenΔ(P)is produced by merging theΔ(P(S_i)), 1≤i≤k. 2005, Balint Felszeghy,Balazs Rath and Lajos Ronyai proposed anothersimilar algorithm by defining a funny game–the Lex game algorithm.Let W = (w₁,...,w_n) is an n dimensional vector of natural numbers. Wedefine the lex gameLex(P; W) as follow:We have two players named Lea and Stan. They both knowP and W. Stanthinks of a point P = (y₁,...,y_n)∈P, Lea has to find out one coordinate of Punder the following rules.First, she can guess wn elements of F for the value of yn. If she succeeds bygiving yn, then Lea wins and the game is over. Otherwise Stan lets her know thereal value of yn. In the next round Lea tries to find out y_n-1 with w_n-1 guesses.The game goes on in the same fashion. We stop when either Lea correctlydeclares one of the y1 (and then wins the game), or Stan reveals y₁. In that caseStan wins. Of course the game will never end in a draw.Forβ∈F, letIf Lea could not find out yn in a Lex(P;(w₁,...,w_n)) game, then they continueas if they have just started a game.LetB be the set of coordinate values that occur in the elements of P . Wethus haveP∈Bⁿ. We may always assume that Lea's guesses for yi are all fromthe set B,The main basis of the Lex game algorithm is :Theorem 3: If n > 1, then if and only if thereexist at least w_n + 1 elementsβ∈B such that .Then with respect to the lex order of , the Lex gamealgorithm is the following : 1)First, construct reverse tree U(P) from P. Then for (β₁,...,β_n)∈P,P_{βn···βi} corresponds to the subtree of a node V , who is on the n - i + 1thlevel of U(P). Sm(I(P_{βn···βi})) has a shorter form SV .2)If V is a leaf then we set SV = {1}. Suppose that we have all thestandard monomials of the vertices at the n - i + 1th level. Let V be a vertexon the n ? ith level and suppose that its children are V₁,...,V_r. Now S_V can becomputed as follows. Initialize SV to be the empty set. For j = 1,...,r and foreach , letand put in SV .Then we analyze and compare these three algorithms.Compare the basis of the algorithms, the essence of these three algo-rithms is the same, but only get from different angles. Algorithm MB and theLex game algorithm are given by means of combinatorial method, algorithm ofconstructΔset is given by structure nature of Gro¨bner bases . Indeed, they alldepend on the following theory: with respect to the lex order, the projection ofalgebraic set and the variety of the projection of it's vanishing ideal is the same,that isIt is precisely because the above nature exists with respect to lex order, therehave these three fast algorithms from algebraic set to monomial bases.Compare the steps of the algorithms, algorithm MB is by adding points,comparing whether the corresponding coordinates is same to get monomialbases. Algorithm of constructΔset getΔ(Ï€^i-1(P)) fromΔ(Ï€ⁱ(P)); the Lexgame algorithm get Sm(Ï€_i+1(P)) from Sm(Ï€_i(P)). But in fact the main steps of these three algorithms are equivalent.Compare the complexity of the algorithms, the complexity of the threealgorithms is basically square-class, that is, for a algebraic sets consists of mpoints of n-dimensional, the complexity of the algorithm is less than O(m²n²).Among them, the Lex game algorithm is the fastest, its complexity is onlyO(mnk), where k = |B|. While the complexity of the 3M algorithm isO(n²m³). It's easy to see that for the calculation of the monomial bases with re-spect to lex order, the three algorithms introduced in this paper is very effective.