Theory And Algorithm Of Multivariate Border Bases

Border bases are important component of numerical polynomial algebra, and one of important part on researching function interpolation. As an important ideal bases, border bases have been becoming more and more appropriate algebra tools on solving practical problems, attracting more and more attention from experts and professionals. Early in 1988, Auzinger and Stetter used border bases to solve zero-dimensional polynomial systems of equations. In 2005, Kehrein and Kreuzer studied general theory of border bases from the perspective of pure algebra and laid a foundation for the algebraic theory of border bases.This paper mainly introduces theory and associated algorithm of multivariate border bases, and make reader have a completely knowledge of border bases through concrete ex-amples.Definition 1 Let O c Tn is an finite term set, if it is closed under divisors, i.e. if t∈O and t'/t imply t'∈O. The border of a non-empty order ideal O is the set of terms (?)O= T1n·O\O={xit:1≤i≤n,t∈O}\O, for an empty order ideal, we define (?)={1}.Definition 2 Let O={t1,…,tμ} be an order ideal with border (?)O={b1,…,bv}. Let G={g1,…, gv) cΠn be a set of polynomials. Then the set G is an O-border prebasis if the polynomials have the formDefinition 3 Let I (?)Πn is a ideal and let O={t1,…,tμ} be an order ideal. Let G={g1,…, gv} is an O-border prebasis and G(?)I. Then the set G is an O-border basis if the residue classes of the terms in O constitute a vector basis ofΠn/I.We have a important theory about existence and uniqueness of border bases.Theorem 1 [13](Existence and Uniqueness of Border Bases)Let O={t1,…, tμ} be an order ideal,let I be a zero-dimensional ideal inΠn,and assume that the residue classes of the elements in O form a K-vector space basis ofΠn/I.Then1. There exists a unique O-border basis G of I.2. Let G'be an O-border prebasis whose elements are in I.Then G'is the O-border basis G of I.3. Let k be the field of definition of I.Then we have G c k[x1,…, xn].From above theory we can notice that the border basis of a zero-dimensional ideal is unique if it exists, and the border basis is independent of term ordering only depending order ideal.The paper also offers some popular border bases algorithm, and particular the algorithm used in bibliography [15] which is realized. Over this basis, combined with the algorithm SPBM in bibliography [22], we give a symbolic algorithm which is used to compute border bases of bivariate vanishing ideal. In order to supply the algorithm, we introduce associated content of algorithm as following.We cover the points in V which is a point set V c K2 by lines parallel to the x-axis, and marked the lines l0x,l1x,...,lvx according to the number of points from more to less on lines including V. Assume that there are mj+1 points on line ljx, including V and marked these points u0jx, u1jx,..., um,jx. Then we define We can also cover the points in V by lines parallel to the y-axis, and marked the lines l0y,l1y,...,lλy according to the number of points from more to less on lines including V. As-sume that there are ni+1 points on line ljx including V and marked these points ui0y,..., ui,niy. Then we defineProposition 1 [22] Assume that V c K2 is a set ofμdistinct points umnx= (xmn,ymn)∈K2,(m,n)∈Sx(V). Let where and the empty products are taken as 1. Then we have The main algorithm follows:Proposition 2 [15](KK Border Basis Algorithm)Let (?) = {f1,…, fs} (?)Πn be a set of polynomials that generates a zero-dimensional ideal I = (?)Πn. Letσbe a degree-compatible term order. The following algorithm com-putes the Oσ(Ⅰ)-border basis {g1,…, gv}.(1)Let d := max{deg(fi) : 1≤i≤s} and L:= K.(2)Compute a vector space basis V = {v1,…, vr} of (?)K with pairwise different leading terms.(3)Compute a basis extension so that the elements of VσW' have pairwise different leading terms.(4)Let W = {vr+1,……, vr+ρ} = {v∈W' : deg(v)≤d}.(5)Ifρ> 0 then replace V with V∪W, increase r byρ, and go to step (3).(6)Let O := T≤dn\{LTσ(v1),…, LTσ(vr)}.(7)If (?)O(?) L then increase d by 1, update L := K and continue with step (3).(8)Apply the Final Reduction Algorithm and return the polynomial g1,…, gv it computes.Proposition 3 [21](BM Algorithm)Let V = {v(i) : i = 1,…,μ} (?) Kn,σis a term order. The algorithm is used to computeσ-Grobner basis G of vanishing ideal, order ideal O and interpolation Newton basis Q. Concrete steps are as following.(1)Started with lists G = [], O = [], Q = [], L = [1], and a matrix B = (bij) withμcolumns and zero rows.(2) If L = [], return (G, O, Q) and stop. Otherwise, choose the monomial t = minσL, and delete t from L.(3) Compute the evaluation vector (t(v(1)),…, t(v(μ))), and reduce it against the rows of B to obtain(4)If (v1,…, vμ) = (0,…, 0), then append the polynomial t-∑iaiqi to the list G, where qi is the ith element of Q. Remove from L all the multiples of t. Continue with (2). (5) Otherwise (v1,…, vμ)≠(0,…,0), add (v1,…, vμ) as a new row to B and t-∑iaiqi, as a new element to Q. Append the monomial t to O, and add to L those elements of{x1t,…, xdt} that are neither multiples of an element of L nor of LT(G). Continue with (2).Proposition 4 [22](SPBM)We fix lexicographical order and assume V is the same as declared in proposition 1. The following algorithm computes reduced Grobner basis of the vanishing ideal I(V) in lexicographical order.(1)Construct lower set Sx(V) according to above.(2)Compute the sets and whereΦijx is defined as proposition 1.(3)Construct the border set (?)O of O.(4)In inverse lexicographical order,we arrange polynomialΦijx and grid umnx from high to low according to suffix, the result separately marked with and Construct the matrix(5)Goto proposition 3(2) of BM algorithm with O, Q, (?)O, B for the reduced Grobner basis G.We can conduct a lot of computer experiments through realizing above algorithm. We compute border bases of vanishing ideals of some special grids(rectangle grid, cartesian set and circles grid with same center). The result of experiment verifies the associated theory of border bases.