On the unique minimal monomial basis of Birkhoff interpolation problem
On the unique minimal monomial basis of Birkhoff interpolation problem
复制标题
DOI：
10.1007/s11424-015-4138-5
复制
发表时间：
2015-12
影响因子：
2.1
通讯作者：
Xiaopeng Zheng;Junjie Chai;Mengci Song;Na Lei
中科院分区：
文献类型：
--
作者：
Xiaopeng Zheng;Junjie Chai;Mengci Song;Na Lei
本文研究了时变Birkhoff插值问题的极小单项基。首先，给出了一个快速的B-Lex算法，该算法具有显式的几何解释，可用于计算字典序下的最小单项插值基，该算法实际上是Lex对策算法的推广。在实际应用中，人们往往希望得到最低次的插值多项式，因此插值问题需要在分次单项式序下而不是字典序下求解。然而，几乎没有存在快速算法的非字典序问题。因此，作者还提供了一个标准，以确定是否一个n-变量Birkhoff插值问题有唯一的最小单项基，这意味着它拥有相同的最小单项基w.r.t.任意单项顺序。因此，对于这种情况下的问题，作者可以很容易地得到的最小单项式基与小的计算成本w.r.t.任意单项式顺序使用我们的快速B-Lex算法。
This paper studies the minimal monomial basis of then-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 lexicographic 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 lexicographic order. However, there barely exist fast algorithms for the nonlexicographic 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.