【作者】 王云；

【导师】 董天；

【作者基本信息】 吉林大学 ， 计算数学， 2010， 硕士

【摘要】 多元多项式环中理想的理想基是研究符号计算、计算代数等前沿交叉学科的主要代数工具之一.鉴于许多符号算法的计算量过大,近年来符号数值混合计算越来越受到国内外学者的关注.而多元理想边界基的数值稳定性比著名的Grobner基要好,因此多元边界基的理论和算法也日益丰富起来.本文综述了当前主要的多元多项式环中理想的边界基理论和符号算法,其中算法均给出了计算实例,并着重介绍了2006年提出的KK边界基算法.在此基础之上,讨论了计算二元消逝理想边界基的问题并进行了相关的实验和分析.更多还原

【Abstract】 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:= <T≤dn>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 := <T≤dn>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.更多还原