This paper studies the minimal monomial basis of the n-variable Birkhoff interpolation problem. First, the authors give a fast B-Lex algorithm which has an explicit geometric interpretation to compute the minimal mono...This paper studies the minimal monomial basis of the n-variable Birkhoff interpolation problem. First, the authors give a fast B-Lex algorithm which has an explicit geometric interpretation to compute the minimal monomial interpolation basis under lexieographie order and the algorithm is in fact a generalization of lex game algorithm. In practice, people usually desire the lowest degree interpolation polynomial, so the interpolation problems need to be solved under, for example, graded monomial order instead of lexicographie order. However, there barely exist fast algorithms for the non- lexicographic order problem. Hence, the authors in addition provide a criterion to determine whether an n-variable Birkhoff interpolation problem has unique minimal monomial basis, which means it owns the same minimal monomial basis w.r.t, arbitrary monomial order. Thus, for problems in this case, the authors can easily get the minimal monomial basis with little computation cost w.r.t, arbitrary monomial order by using our fast B-Lex algorithm.展开更多
基金supported by the National Natural Science Foundation of China under Grant No.11271156Science and Technology Development Plan of Jilin Province under Grant No.20130101179JCPublic Computing Platform in Jilin Province
文摘This paper studies the minimal monomial basis of the n-variable Birkhoff interpolation problem. First, the authors give a fast B-Lex algorithm which has an explicit geometric interpretation to compute the minimal monomial interpolation basis under lexieographie order and the algorithm is in fact a generalization of lex game algorithm. In practice, people usually desire the lowest degree interpolation polynomial, so the interpolation problems need to be solved under, for example, graded monomial order instead of lexicographie order. However, there barely exist fast algorithms for the non- lexicographic order problem. Hence, the authors in addition provide a criterion to determine whether an n-variable Birkhoff interpolation problem has unique minimal monomial basis, which means it owns the same minimal monomial basis w.r.t, arbitrary monomial order. Thus, for problems in this case, the authors can easily get the minimal monomial basis with little computation cost w.r.t, arbitrary monomial order by using our fast B-Lex algorithm.
