# A Bivariate Preprocessing Paradigm for Buchberger-Möller Algorithm

Xiaoying Wang, Shugong Zhang  Tian Dong<EMAIL_ADDRESS>School of
Mathemathics, Key Lab. of Symbolic Computation and Knowledge Engineering
(Ministry of Education), Jilin University, Changchun 130012, PR China

###### Abstract

For the last almost three decades, since the famous Buchberger-Möller(BM)
algorithm emerged, there has been wide interest in vanishing ideals of points
and associated interpolation polynomials. Our paradigm is based on the theory
of bivariate polynomial interpolation on cartesian point sets that gives us
related degree reducing interpolation monomial and Newton bases directly.
Since the bases are involved in the computation process as well as contained
in the final output of BM algorithm, our paradigm obviously simplifies the
computation and accelerates the BM process. The experiments show that the
paradigm is best suited for the computation over finite prime fields that have
many applications.

###### keywords:

Buchberger-Möller algorithm , Bivariate Lagrange interpolation , Degree
reducing interpolation space , Cartesian set

###### MSC:

13P10 , 65D05 , 12Y05

††journal: Journal of Computational and Applied
Mathematicsfundfundfootnotetext: This work was supported in part by the
National Grand Fundamental Research 973 Program of China (No. 2004CB318000).

##  1 Introduction

For an arbitrary field $\mathbb{F}$, we let $\mathbb{F}_{q}$ a finite prime
field of size $q$ and $\Pi^{d}:=\mathbb{F}[x_{1},\ldots,x_{d}]$ the
$d$-variate polynomial ring over $\mathbb{F}$. Given a preassigned set of
distinct affine points $\Xi\subset\mathbb{F}^{d}$, it is well-known that the
set of all polynomials in $\Pi^{d}$ vanishing at $\Xi$ constitutes a radical
zero-dimensional ideal, denoted by $\mathcal{I}(\Xi)$, which is called the
_vanishing ideal_ of $\Xi$.

Recent years, there has been considerable interest in vanishing ideals of
points in many branches of mathematics such as algebraic geometry[1],
multivariate interpolation[2, 3], coding theory[4, 5], statistics[6], and even
computational molecular biology[7, 8]. As is well known, the most significant
milestone of the computation of vanishing ideals is the algorithm presented in
[9] by Hans Michael Möller and Bruno Buchberger known as Buchberger-Möller
algorithm(BM algorithm for short). For any point set
$\Xi\subset\mathbb{F}^{d}$ and fixed term order $\prec$, BM algorithm yields
the reduced Gröbner basis for $\mathcal{I}(\Xi)$ w.r.t. $\prec$ and a
$\prec$-degree reducing interpolation Newton basis for $d$-variate Lagrange
interpolation on $\Xi$. The algorithm also produces the Gröbner éscalier of
$\mathcal{I}(\Xi)$ w.r.t. $\prec$ as a byproduct. Afterwards, in 1993, BM
algorithm was applied in [10] in order to solve the renowned FGLM-problem. In
the same year, [11] merged BM and FGLM algorithms into four variations that
can solve more general zero-dimensional ideals therefore related ideal
interpolation problems [3]. The algorithms are referred as MMM algorithms.

Although very important, BM algorithm (and MMM algorithms) has a very poor
complexity that limits its applications. In this decade, many authors proposed
new algorithms that can reduce the complexity but mostly suitable for special
cases. [12] presented a modular version of BM algorithm that is best suited to
the computation over $\mathbb{Q}$. [13, 14, 15] presented algorithms for
obtaining, with relatively little effort, the Gröbner éscalier of a vanishing
ideal w.r.t. the (inverse) lexicographic order that can lead to an
interpolation Newton basis or the reduced Gröbner basis for the vanishing
ideal after solving a linear system.

For a fixed point set $\Xi$ in $\mathbb{F}^{d}$ and a term order $\prec$, it
is well known that there are _two_ factors that determine the Gröbner éscalier
of $\mathcal{I}(\Xi)$ w.r.t. $\prec$ thereby the reduced Gröbner basis for
$\mathcal{I}(\Xi)$ and related degree reducing interpolation Newton bases (up
to coefficients). One is apparently the cardinal of $\Xi$. It is the unique
determinate factor in univariate cases. Another one is the geometry (the
distribution of the points) of $\Xi$ that is dominating in multivariate cases
but not taken into consideration by BM and MMM algorithms. Recent years, [16,
17, 18] studied multivariate Lagrange interpolation on a special kind of point
sets, cartesian point sets (aka lower point sets), and constructed the
associated Gröbner éscalier and degree reducing interpolation Newton bases
theoretically. We know from [9, 11] that, for a cartesian subset of $\Xi$ (it
always exists!), certain associated degree reducing interpolation Newton basis
forms part of the output of BM algorithm w.r.t. some reordering of $\Xi$.
Therefore, finding a large enough cartesian subset of $\Xi$ with little enough
effort will reduce the complexity of BM algorithm.

Following this idea, the paper proposes a preprocessing paradigm for BM
algorithm with the organization as follows. The next section is devoted as a
preparation for the paper. And then, the main results of us are presented in
two sections. Section 3 will pursue the paradigm for two special term orders
while Section 4 will set forth our solution for other more general cases. In
the last section, Section 5, some implementation issues and experimental
results will be illustrated.

##  2 Preliminary

In this section, we will introduce some notation and recall some basic facts
for the reader’s convenience. For more details, we refer the reader to [19,
20].

We let $\mathbb{N}_{0}$ denote the monoid of nonnegative integers. A
_polynomial_ $f\in\Pi^{2}$ is of the form

$f=\sum_{\bm{\alpha}\in\mathbb{N}_{0}^{2}}f_{\bm{\alpha}}X^{\bm{\alpha}},\hskip
22.76228pt\\#\\{\bm{\alpha}\in\mathbb{N}_{0}^{2}:0\neq
f_{\bm{\alpha}}\in\mathbb{F}\\}<\infty,$

where _monomial_ $X^{\bm{\alpha}}=x^{\alpha_{1}}y^{\alpha_{2}}$ with
$\bm{\alpha}=(\alpha_{1},\alpha_{2})$. The set of bivariate monomials in
$\Pi^{2}$ is denoted by $\mathbb{T}^{2}$.

Fix a term order $\prec$ on $\Pi^{2}$ that may be lexicographical order
$\prec_{\text{lex}}$, inverse lexicographical order $\prec_{\text{inlex}}$, or
total degree inverse lexicographical order $\prec_{\text{tdinlex}}$ etc. For
all $f\in\Pi^{2}$, with $f\neq 0$, we may write

$f=f_{\bm{\gamma_{1}}}X^{\bm{\gamma_{1}}}+f_{\bm{\gamma_{2}}}X^{\bm{\gamma_{2}}}+\cdots+f_{\bm{\gamma_{r}}}X^{\bm{\gamma_{r}}},$

where $0\neq
f_{\bm{\gamma_{i}}}\in\mathbb{F},\bm{\gamma_{i}}\in\mathbb{N}_{0}^{2},i=1,\ldots,r$,
and $X^{\bm{\gamma_{1}}}\succ X^{\bm{\gamma_{2}}}\succ\cdots\succ
X^{\bm{\gamma_{r}}}$. We shall call
$\mathrm{LT}(f):=f_{\bm{\gamma_{1}}}X^{\bm{\gamma_{1}}}$ the _leading term_
and $\mathrm{LM}(f):=X^{\bm{\gamma_{1}}}$ the _leading monomial_ of $f$.
Furthermore, for a non-empty subset $F\subset\Pi^{2}$, put

$\mathrm{LT}(F):=\\{\mathrm{LT}(f):f\in F\\}.$

As in [21], we define the $\prec\mspace{-8.0mu}-$_degree_ of a polynomial
$f\in\Pi^{2}$ to be the leading bidegree w.r.t. $\prec$

$\delta(f):=\bm{\gamma},\quad X^{\bm{\gamma}}=\mathrm{LM}(f),$

with $\delta(0)$ undefined. Further, for any finite dimensional subset
$F\subset\Pi^{2}$, define

$\delta(F):=\max_{f\in F}\delta(f).$

Finally, for any $f,g\in\Pi^{2}$, if $\delta(f)\prec\delta(g)$ then we say
that $f$ is of _lower degree_ than $g$ and use the abbreviation

$f\prec g:=\delta(f)\prec\delta(g).$

In addition, $f\preceq g$ is interpreted as the degree of $f$ is lower than or
equal to that of $g$.

Let $\mathcal{A}$ be a finite subset of $\mathbb{N}_{0}^{2}$. $\mathcal{A}$ is
called a _lower_ set if, for any
$\bm{\alpha}=(\alpha_{1},\alpha_{2})\in\mathcal{A}$, we always have

$\mathrm{R}(\bm{\alpha}):=\\{(\alpha^{\prime}_{1},\alpha^{\prime}_{2})\in\mathbb{N}_{0}^{2}:0\leq\alpha^{\prime}_{i}\leq\alpha_{i},i=1,2\\}\subset\mathcal{A}.$

Especially, $\bm{0}\in\mathcal{A}$. Moreover, we set
$m_{j}=\max_{(h,j)\in\mathcal{A}}h,0\leq j\leq\nu$, with
$\nu=\max_{(0,k)\in\mathcal{A}}k$. Clearly, $\mathcal{A}$ can be determined
uniquely by the ordered $(\nu+1)$-tuple $(m_{0},m_{1},\ldots,m_{\nu})$ hence
represented as $\mathrm{L}_{x}(m_{0},m_{1},\ldots,m_{\nu})$. Swapping the
roles of $x$ and $y$, we can also represent $\mathcal{A}$ as
$\mathrm{L}_{y}(n_{0},n_{1},\ldots,n_{m_{0}})$ with
$n_{i}=\max_{(i,k)\in\mathcal{A}}k,0\leq i\leq m_{0}$. It should be noticed
that $\nu=n_{0}$.

Given a set $\Xi=\\{\xi^{(1)},\ldots,\xi^{(\mu)}\\}\subset\mathbb{F}^{2}$ of
$\mu$ distinct points. For prescribed values
$f_{i}\in\mathbb{F},i=1,\ldots,\mu$, find all polynomials $p\in\Pi^{2}$
satisfying

$p(\xi^{(i)})=f_{i},\quad i=1,\ldots,\mu.$ (1)

We call it the problem of _bivariate Lagrange interpolation_. Note that in
most cases, especially from a numerical point of view, we are not interested
in all such $p$’s but a “degree reducing” one, as in the univariate cases.

######  Definition 1.

[2] Fix term order $\prec$. We call a subspace $\mathcal{P}\subset\Pi^{2}$ a
_degree reducing interpolation space_ w.r.t. $\prec$ for the bivariate
Lagrange interpolation (1) if

DR1.

$\mathcal{P}$ is an _interpolation space_ , i.e., for any
$f_{i}\in\mathbb{F},i=1,\ldots,\mu$, there is a unique $p\in\mathcal{P}$ such
that $p$ satisfies (1). In other words, the interpolation problem is _regular_
w.r.t. $\mathcal{P}$.

DR2.

$\mathcal{P}$ is $\prec\mspace{-8.0mu}-$_reducing_ , i.e., when
$L_{\mathcal{P}}$ denotes the Lagrange projector with range $\mathcal{P}$,
then the interpolation polynomial

$L_{\mathcal{P}}q\preceq q,\hskip 14.22636pt\forall q\in\Pi^{2}.$

For interpolation problem (1), a given interpolation space
$\mathcal{P}\subset\Pi^{2}$ will give rise to an _interpolation scheme_ that
is referred as $(\Xi,\mathcal{P})$, cf. [20]. Since (1) is regular w.r.t.
$\mathcal{P}$, we can also say that $(\Xi,\mathcal{P})$ is regular. Moreover,
if $\mathcal{P}$ is degree reducing w.r.t. $\prec$, a basis
$\\{p_{1},\ldots,p_{\mu}\\}$ for $\mathcal{P}$ will be called a _degree
reducing interpolation basis_ w.r.t. $\prec$ for (1). Assume that $p_{1}\prec
p_{2}\prec\cdots\prec p_{\mu}$. If

$p_{j}(\xi^{(i)})=\delta_{ij},\quad 1\leq i\leq j\leq\mu,$

for some suitable reordering of $\Xi$, then we call
$\\{p_{1},\ldots,p_{\mu}\\}$ a _degree reducing interpolation Newton
basis_(DRINB) w.r.t. $\prec$ for (1).

Let $G_{\prec}$ be the reduced Gröbner basis for the vanishing ideal
$\mathcal{I}(\Xi)$ w.r.t.$\prec$. The set

$\mathrm{N}_{\prec}(\mathcal{I}(\Xi)):=\\{x^{\bm{\alpha}}\in\mathbb{T}^{2}:\mathrm{LT}(g)\nmid
x^{\bm{\alpha}},\forall g\in G_{\prec}\\}$

is called the _Gröbner éscalier_ of $\mathcal{I}(\Xi)$ w.r.t. $\prec$. From
[2, 21], the interpolation space spanned by
$\mathrm{N}_{\prec}(\mathcal{I}(\Xi))$, denoted by $\mathcal{P}_{\prec}(\Xi)$,
is canonical since it is the unique degree reducing interpolation space
spanned by monomials w.r.t. $\prec$ for (1). Hence, we call
$\mathrm{N}_{\prec}(\mathcal{I}(\Xi))$ the _degree reducing interpolation
monomial basis_(DRIMB) w.r.t. $\prec$ for (1), with
$\\#\mathrm{N}_{\prec}(\mathcal{I}(\Xi))=\mu$. Let

$\mathrm{N}_{\prec}(\Xi):=\\{\bm{\alpha}:x^{\bm{\alpha}}\in\mathrm{N}_{\prec}(\mathcal{I}(\Xi))\\}\subset\mathbb{N}_{0}^{2}.$

We can deduce easily that $\mathrm{N}_{\prec}(\Xi)$ is a lower set and
obviously has a one-to-one correspondence with
$\mathrm{N}_{\prec}(\mathcal{I}(\Xi))$. Therefore, interpolation scheme
$(\Xi,\mathcal{P}_{\prec}(\Xi))$ can be equivalently represented as
$(\Xi,\mathrm{N}_{\prec}(\Xi))$.

According to [17], we can construct two particular lower sets from $\Xi$,
denoted by $S_{x}(\Xi),S_{y}(\Xi)$, which reflect the geometry of $\Xi$ in
certain sense.

Specifically, we cover the points in $\Xi$ by lines
$l_{0}^{x},l_{1}^{x},\ldots,l_{\nu}^{x}$ parallel to the $x$-axis and assume
that, without loss of generality, there are $m_{j}+1$ points, say
$u_{0j}^{x},u_{1j}^{x},\ldots,u_{m_{j},j}^{x}$, on $l_{j}^{x}$ with $m_{0}\geq
m_{1}\geq\cdots\geq m_{\nu}\geq 0$ hence the ordinates of $u_{ij}^{x}$ and
$u_{i^{\prime}j}^{x},i\neq i^{\prime}$, same. Now, we set

$S_{x}(\Xi):=\\{(i,j):0\leq i\leq m_{j},\ 0\leq j\leq\nu\\},$

which apparently equals to $\mathrm{L}_{x}(m_{0},m_{1},\ldots,m_{\nu})$. We
can also cover the points by lines
$l_{0}^{y},l_{1}^{y},\ldots,l_{\lambda}^{y}$ parallel to the $y$-axis and
denote the points on line $l_{i}^{y}$ by
$u_{i0}^{y},u_{i1}^{y},\ldots,u_{i,n_{i}}^{y}$ with $n_{0}\geq
n_{1}\geq\cdots\geq n_{\lambda}\geq 0$ hence the abscissae of $u_{ij}^{y}$ and
$u_{ij^{\prime}}^{y},j\neq j^{\prime}$, same. Similarly, we put

$S_{y}(\Xi):=\\{(i,j):0\leq i\leq\lambda,\ 0\leq j\leq
n_{i}\\}=\mathrm{L}_{y}(n_{0},n_{1},\ldots,n_{\lambda}).$

In addition, we can also define the sets of abscissae and ordinates

$\displaystyle H_{j}(\Xi):=$ $\displaystyle\\{\bar{x}:(\bar{x},\bar{y})\in
l_{j}^{x}\cap\Xi\\},\quad 0\leq j\leq\nu,$ (2) $\displaystyle V_{i}(\Xi):=$
$\displaystyle\\{\bar{y}:(\bar{x},\bar{y})\in l_{i}^{y}\cap\Xi\\},\quad 0\leq
i\leq\lambda.$

######  Definition 2.

[17] We say that a set $\Xi$ of distinct points in $\mathbb{F}^{2}$ is
_cartesian_ if there exists a lower set $\mathcal{A}$ such that $\Xi$ can be
written as

$\Xi=\\{(x_{i},y_{j}):(i,j)\in\mathcal{A}\\},$

where the $x_{i}$’s are distinct numbers, and similarly the $y_{j}$’s. We also
say that $\Xi$ is $\mathcal{A}$-cartesian.

To the best of our knowledge, there are two criteria for determining whether a
2-dimensional point set is cartesian.

######  Theorem 1.

[17] A set of distinct points $\Xi\subset\mathbb{F}^{2}$ is cartesian if and
only if $S_{x}(\Xi)=S_{y}(\Xi)$.

######  Theorem 2.

[18] A set of distinct points $\Xi\subset\mathbb{F}^{2}$ is cartesian if and
only if

$H_{0}(\Xi)\supseteq H_{1}(\Xi)\supseteq\cdots\supseteq H_{\nu}(\Xi),\quad
V_{0}(\Xi)\supseteq V_{1}(\Xi)\supseteq\cdots\supseteq V_{\lambda}(\Xi).$

About the bivariate Lagrange interpolation on a cartesian set, [17] proved the
succeeding theorem.

######  Theorem 3.

[17] Given a cartesian set $\Xi\subset\mathbb{F}^{2}$, there exists a unique
lower set $\mathcal{A}\in\mathbb{N}_{0}^{2}$ such that $\Xi$ is
$\mathcal{A}$-cartesian and the Lagrange interpolation scheme
$(\Xi,\mathcal{A})$ is regular.

Finally, we will redescribe the classical BM algorithm with the notation
established above.

######  Algorithm 1.

(BM Algorithm)

Input: A set of distinct points
$\Xi=\\{\xi^{(i)}:i=1,\ldots,\mu\\}\subset\mathbb{F}^{d}$ and a fixed term
order $\prec$.
Output: The 3-tuple $(G,N,Q)$, where $G$ is the reduced Gröbner basis for
$\mathcal{I}(\Xi)$ w.r.t. $\prec$, $N$ is the Gröbner éscalier of
$\mathcal{I}(\Xi)$ (the DRIMB for (1) also) w.r.t. $\prec$, and $Q$ is a DRINB
w.r.t. $\prec$ for (1).
BM1. Start with lists $G=[\ ],N=[\ ],Q=[\ ],L=[1]$, and a matrix $B=(b_{ij})$
over $\mathbb{F}$ with $\mu$ columns and zero rows initially.
BM2. If $L=[\ ]$, return $(G,N,Q)$ and stop. Otherwise, choose the monomial
$t=\mbox{min}_{\prec}L$, and delete $t$ from $L$.
BM3. Compute the evaluation vector $(t(\xi^{(1)}),\ldots,t(\xi^{(\mu)}))$, and
reduce it against the rows of $B$ to obtain

$(v_{1},\ldots,v_{\mu})=(t(\xi^{(1)}),\ldots,t(\xi^{(\mu)}))-\sum_{i}a_{i}(b_{i1},\ldots,b_{i\mu}),\quad
a_{i}\in\mathbb{F}.$

BM4.. If $(v_{1},\ldots,v_{\mu})=(0,\ldots,0)$, then append the polynomial
$t-\sum_{i}a_{i}q_{i}$ to the list $G$, where $q_{i}$ is the $i$th element of
$Q$. Remove from $L$ all the multiples of $t$. Continue with BM2.
BM5. Otherwise $(v_{1},\ldots,v_{\mu})\neq(0,\ldots,0)$, add
$(v_{1},\ldots,v_{\mu})$ as a new row to $B$ and $t-\sum_{i}a_{i}q_{i}$ as a
new element to $Q$. Append the monomial $t$ to $N$, and add to $L$ those
elements of $\\{x_{1}t,\ldots,x_{d}t\\}$ that are neither multiples of an
element of $L$ nor of $\mathrm{LT}(G)$. Continue with BM2.

##  3 Special cases

In this section, we will focus on $\prec_{\mathrm{lex}}$ and
$\prec_{\mathrm{inlex}}$ that may be the most talked about term orders. For
these special cases, our preprocessing paradigm will first provide exact $N,Q$
of the 3-tuple output $(G,N,Q)$ to BM algorithm directly and effortlessly. And
then, $G$ can be obtained by BM algorithm easily. Note that we will continue
with all the notation that we established for $S_{x}(\Xi)$ and $S_{y}(\Xi)$ in
the previous section.

######  Proposition 4.

Let $\Xi$ be a set of $\mu$ distinct points
$u_{mn}^{x}=(x_{mn},y_{mn})\in\mathbb{F}^{2},(m,n)\in S_{x}(\Xi)$. The points
give rise to polynomials

$\phi_{ij}^{x}=\varphi_{ij}^{x}\prod_{t=0}^{j-1}(y-y_{0t})\prod_{s=0}^{i-1}(x-x_{sj}),\quad(i,j)\in
S_{x}(\Xi),$ (3)

where
$\varphi_{ij}^{x}=1/\prod_{t=0}^{j-1}(y_{0j}-y_{0t})\prod_{s=0}^{i-1}(x_{ij}-x_{sj})\in\mathbb{F}$,
and the empty products are taken as 1. Then we have

$\phi_{ij}^{x}(u_{mn}^{x})=\delta_{(i,j),(m,n)},\quad(i,j)\succeq_{\mathrm{inlex}}(m,n).$

######  Proof 1.

Fix $(i,j)\in S_{x}(\Xi)$. Recalling the definition of $u_{ij}^{x}$, we have
$y_{0j}=y_{ij}$. If $(i,j)=(m,n)$, by $y_{00}\neq y_{01}\neq\cdots\neq y_{0j}$
and $x_{0j}\neq x_{1j}\neq\cdots\neq x_{ij}$, we have

$\phi_{ij}^{x}(u_{ij}^{x})=\varphi_{ij}^{x}\prod_{t=0}^{j-1}(y_{ij}-y_{0t})\prod_{s=0}^{i-1}(x_{ij}-x_{sj})=\varphi_{ij}^{x}\prod_{t=0}^{j-1}(y_{0j}-y_{0t})\prod_{s=0}^{i-1}(x_{ij}-x_{sj}),$

which implies $\phi_{ij}^{x}(u_{ij}^{x})=1$.

Otherwise, if $(i,j)\succ_{\mathrm{inlex}}(m,n)$, we have $j>n$, or $j=n,i>m$.
When $j>n$, we have

$\displaystyle\phi_{ij}^{x}(u_{mn}^{x})$
$\displaystyle=\varphi_{ij}^{x}(y_{mn}-y_{00})\cdots(y_{mn}-y_{0n})\cdots(y_{mn}-y_{0,j-1})\prod_{s=0}^{i-1}(x_{mn}-x_{sj})$
$\displaystyle=\varphi_{ij}^{x}(y_{0n}-y_{00})\cdots(y_{0n}-y_{0n})\cdots(y_{0n}-y_{0,j-1})\prod_{s=0}^{i-1}(x_{mn}-x_{sj})$
$\displaystyle=0,$

and when $j=n,i>m$,

$\displaystyle\phi_{ij}^{x}(u_{mn}^{x})$
$\displaystyle=\varphi_{ij}^{x}\prod_{t=0}^{j-1}(y_{mn}-y_{0t})(x_{mn}-x_{0j})\cdots(x_{mn}-x_{mj})\cdots(x_{mn}-x_{i-1,j})$
$\displaystyle=\varphi_{ij}^{x}\prod_{t=0}^{n-1}(y_{mn}-y_{0t})(x_{mn}-x_{0n})\cdots(x_{mn}-x_{mn})\cdots(x_{mn}-x_{i-1,n})$
$\displaystyle=0,$

which leads to

$\phi_{ij}^{x}(u_{mn}^{x})=0,\quad(i,j)\succ_{\mathrm{inlex}}(m,n).$

∎

Similarly, we can prove the following proposition:

######  Proposition 5.

Let $\Xi$ be a set of $\mu$ distinct points
$u_{mn}^{y}=(x_{mn},y_{mn})\in\mathbb{F}^{2},(m,n)\in S_{y}(\Xi)$. We define
the polynomials

$\phi_{ij}^{y}=\varphi_{ij}^{y}\prod_{s=0}^{i-1}(x-x_{s0})\prod_{t=0}^{j-1}(y-y_{it}),\quad(i,j)\in
S_{y}(\Xi),$ (4)

where
$\varphi_{ij}^{y}=1/\prod_{s=0}^{i-1}(x_{i0}-x_{s0})\prod_{t=0}^{j-1}(y_{ij}-y_{it})\in\mathbb{F}$.
The empty products are taken as 1. Then,

$\phi_{ij}^{y}(u_{mn}^{y})=\delta_{(i,j),(m,n)},\quad(i,j)\succeq_{\mathrm{lex}}(m,n).$

In 2004, [17] proved that the Lagrange interpolation schemes
$(\Xi,S_{x}(\Xi))$ and $(\Xi,S_{y}(\Xi))$ are both regular. Here we reprove
the regularities in another way for the purpose of presenting the degree
reducing interpolation bases theoretically .

######  Theorem 6.

Resume the notation in _Proposition 4_ and _5_. Then the Lagrange
interpolation schemes $(\Xi,S_{x}(\Xi))$ and $(\Xi,S_{y}(\Xi))$ are regular.
Furthermore,
(i) the set $N_{x}:=\\{x^{i}y^{j}:(i,j)\in S_{x}(\Xi)\\}$ is the _DRIMB_ as
well as $Q_{x}:=\\{\phi_{ij}^{x}:(i,j)\in S_{x}(\Xi)\\}$ is a _DRINB_ w.r.t.
$\prec_{\mathrm{lex}}$ for the interpolation problem (1).
(ii) the set $N_{y}:=\\{x^{i}y^{j}:(i,j)\in S_{y}(\Xi)\\}$ is the _DRIMB_ as
well as $Q_{y}:=\\{\phi_{ij}^{y}:(i,j)\in S_{y}(\Xi)\\}$ is a _DRINB_ w.r.t.
$\prec_{\mathrm{inlex}}$ for (1).

######  Proof 2.

We only give the proof for $S_{x}(\Xi)$. The statements about $S_{y}(\Xi)$ can
be proved likewise.

First, we will show the regularity of the interpolation scheme
$(\Xi,S_{x}(\Xi))$. Let
$\mathcal{P}_{x}:=\mathrm{Span}_{\mathbb{F}}N_{x}\subset\Pi^{2}$ with
$\dim\mathcal{P}_{x}=\\#\Xi=\mu$. Obviously, $N_{x}$ is the monomial basis for
it. By (3), we can check easily that

$\mathrm{Span}_{\mathbb{F}}Q_{x}\subseteq\mathcal{P}_{x}.$

Construct a square matrix $B_{\mu\times\mu}$ whose $(h,k)$ entry is
$\phi_{h}^{x}(u_{k}^{x})$ where $\phi_{h}^{x},u_{k}^{x}$ are $h$th and $k$th
elements of $Q_{x}$ and $\Xi=\\{u_{mn}^{x}:(m,n)\in S_{x}(\Xi)\\}$ w.r.t. the
increasing $\prec_{\mathrm{inlex}}$ on $(i,j)$ and $(m,n)$ respectively. From
Proposition 4, $B_{\mu\times\mu}$ is upper unitriangular which implies that
$\mathrm{Span}_{\mathbb{F}}Q_{x}=\mathcal{P}_{x}$ and $Q_{x}$ forms a Newton
basis for $\mathcal{P}_{x}$. It follows that $\mathcal{P}_{x}$ is an
interpolation space for Lagrange interpolation (1) therefore the scheme
$(\Xi,\mathcal{P}_{x})$ is regular. Since
$(\Xi,S_{x}(\Xi))=(\Xi,\mathcal{P}_{x})$, according to Section 2,
$(\Xi,S_{x}(\Xi))$ is regular.

Next, we shall verify that the statements in (i), which is equivalent to the
statement that $\mathcal{P}_{x}$ is a degree reducing interpolation space
w.r.t. $\prec_{\mathrm{lex}}$ for (1) that coincides with
$\mathcal{P}_{\prec_{\mathrm{lex}}}(\Xi)$. Since the arguments above have
proved that $\mathcal{P}_{x}$ satisfies the DR1 condition in Definition 1,
what is left for us is to check the DR2 condition. From [21], we only need to
check it for monomials.

Take a monomial $x^{i_{0}}y^{j_{0}}\in\mathbb{T}^{2}$. We shall prove that

$L_{\mathcal{P}_{x}}x^{i_{0}}y^{j_{0}}\preceq_{\mathrm{lex}}x^{i_{0}}y^{j_{0}}.$
(5)

Since $\mathcal{P}_{x}$ satisfies DR1, $L_{\mathcal{P}_{x}}x^{i_{0}}y^{j_{0}}$
is the unique polynomial in $\mathcal{P}_{x}$ that matches
$x^{i_{0}}y^{j_{0}}$ on $\Xi$. Therefore, when $x^{i_{0}}y^{j_{0}}\in N_{x}$,
we have $L_{\mathcal{P}_{x}}x^{i_{0}}y^{j_{0}}=x^{i_{0}}y^{j_{0}}$ , namely
(5) is true for this case. Assume that

$S_{x}(\Xi)=\mathrm{L}_{x}(m_{0},\ldots,m_{n_{0}})=\mathrm{L}_{y}(n_{0},\ldots,n_{m_{0}}).$

It is easy to see that $\delta(\mathcal{P}_{x})=(m_{0},n_{m_{0}})$. If
$x^{m_{0}}y^{n_{m_{0}}}\prec_{\mathrm{lex}}x^{i_{0}}y^{j_{0}}$ then
$\delta(L_{\mathcal{P}_{x}}x^{i_{0}}y^{j_{0}})\preceq_{\mathrm{lex}}\delta(\mathcal{P}_{x})=(m_{0},n_{m_{0}})\prec_{\mathrm{lex}}(i_{0},j_{0})=\delta(x^{i_{0}}y^{j_{0}})$
that leads to (5) for the case.

Thus, what remains for us is to check (5) for $x^{i_{0}}y^{j_{0}}\notin N_{x}$
with $(i_{0},j_{0})\prec_{\mathrm{lex}}(m_{0},n_{m_{0}})$ that implies $0\leq
i_{0}<m_{0},j_{0}>n_{i_{0}}$. For this, we only need to verify that

$L_{\mathcal{P}_{x}}x^{i_{0}}y^{j_{0}}\in\mathrm{Span}_{\mathbb{F}}\\{x^{i}y^{j}:(i,j)\in
F_{i_{0}}\\},$ (6)

where $F_{i_{0}}=\\{(i,j)\in
S_{x}(\Xi):(i,j)\prec_{\mathrm{lex}}(i_{0},j_{0})\\}\subset S_{x}(\Xi).$ If
$x^{i_{0}}y^{j_{0}}\in\mathcal{I}(\Xi)$, then
$L_{\mathcal{P}_{x}}x^{i_{0}}y^{j_{0}}=0\prec_{\mathrm{lex}}x^{i_{0}}y^{j_{0}}$.
The statement (6) becomes trivial in this case. Otherwise, if we can find a
polynomial $p\in\Pi^{2}$ such that

$\displaystyle p=x^{i_{0}}y^{j_{0}}-\sum_{(i,j)\in
F_{i_{0}}}a_{ij}x^{i}y^{j}\in\mathcal{I}(\Xi),$ (7)

where $a_{ij}\in\mathbb{F}$ are not all zero, then (6) follows.

According to Section 2, our point set
$\Xi=\\{u_{ij}^{x}=(x_{ij},y_{ij}):(i,j)\in S_{x}(\Xi)\\}$. Let
$\Xi^{\prime}=\\{u_{mn}^{x}\in\Xi:(m,n)\in F_{i_{0}}\\}\subset\Xi$. Now, we
claim that there exists a unique polynomial $p$ of the form (7) such that
$p\in\mathcal{I}(\Xi^{\prime})$, which is equivalent to the statement that the
linear system

$\displaystyle\sum_{(i,j)\in
F_{i_{0}}}a_{ij}x_{mn}^{i}y_{mn}^{j}=x_{mn}^{i_{0}}y_{mn}^{j_{0}},\quad
u_{mn}^{x}\in\Xi^{\prime},$ (8)

has a unique solution.

Note that $\mathrm{Span}_{\mathbb{F}}\\{x^{i}y^{j}:(i,j)\in
F_{i_{0}}\\}=\mathrm{Span}_{\mathbb{F}}\\{\phi^{x}_{ij}:(i,j)\in
F_{i_{0}}\\}$. We can conclude that the rank of the coefficient matrix of (8)
is equal of that of the matrix $B^{\prime}_{\\#F_{i_{0}}\times\\#F_{i_{0}}}$,
which is a submatrix of $B$ whose $(h,k)$ entry is $\phi_{h}^{x}(u_{k}^{x})$
where $\phi_{h}^{x},u_{k}^{x}$ are $h$th and $k$th elements of
$\\{\phi_{ij}^{x}:(i,j)\in F_{i_{0}}\\}$ and $\Xi^{\prime}=\\{u_{mn}^{x}\\}$
w.r.t. the increasing $\prec_{\mathrm{inlex}}$ on $(i,j)$ and $(m,n)$
respectively. By (3), we see easily that $B^{\prime}$ is upper unitriangular
which implies that the coefficient matrix of (8) is of full rank. Accordingly,
there is a unique polynomial $p\in\mathcal{I}(\Xi^{\prime})$ that has the form
(7).

Now we shall verify that
$p(u_{ij}^{x})=0,u_{ij}^{x}\in\Xi\setminus\Xi^{\prime}$. By the definition of
$\Xi^{\prime}$, we know that $i>i_{0}$ here. Let

$q(x):=p(x,y_{ij})=\sum_{s=0}^{i_{0}}b_{s}x^{s}\in\Pi^{1},\quad
b_{s}\in\mathbb{F}.$

Since $y_{0j}=y_{1j}=\cdots=y_{i_{0},j}=y_{ij}$ and
$u_{0j}^{x},u_{1j}^{x},\ldots,u_{i_{0},j}^{x}\in\Xi^{\prime}$, it follows that

$q(x_{sj})=p(x_{sj},y_{ij})=p(x_{sj},y_{sj})=p(u_{sj}^{x})=0,\quad
s=0,\ldots,i_{0},$

namely $q(x)$ has $i_{0}+1$ zero points that clearly implies $q(x)\equiv 0$.
Since $p(u_{ij}^{x})=q(x_{ij})=0$, we have $p\in\mathcal{I}(\Xi)$. By (6), (5)
is true in this case. As a result, for any $f\in\Pi^{2}$, we have

$L_{\mathcal{P}_{x}}f\preceq_{\mathrm{lex}}f,$

that is to say $\mathcal{P}_{x}$ satisfies DR2.

Consequently, by Definition 1, $\mathcal{P}_{x}$ is a degree reducing
interpolation space w.r.t. $\prec_{\mathrm{lex}}$ for Lagrange interpolation
(1). Hence $N_{x}$ is the DRIMB and $Q_{x}$ is a Newton basis w.r.t.
$\prec_{\mathrm{lex}}$ for (1).∎

Note that $\mathcal{P}_{\prec_{\mathrm{lex}}}(\Xi)$ is the unique degree
reducing interpolation space spanned by monomials w.r.t.
$\prec_{\mathrm{lex}}$, thus we have
$\mathcal{P}_{x}=\mathcal{P}_{\prec_{\mathrm{lex}}}(\Xi)$. Therefore,
$N_{x}=N_{\prec_{\mathrm{lex}}}(\mathcal{I}(\Xi))$ holds, which means that
$N_{x}$ is also the Gröbner éscalier of $\mathcal{I}(\Xi)$ w.r.t.
$\prec_{\mathrm{lex}}$.

######  Corollary 7.

If $\Xi\subset\mathbb{F}^{2}$ is an $\mathcal{A}$-cartesian set, then
$\mathcal{A}=S_{x}(\Xi)=S_{y}(\Xi)$.

######  Proof 3.

Since $\Xi$ is cartesian, by Theorem 1 and 6, we have $S_{x}(\Xi)=S_{y}(\Xi)$
hence $(\Xi,S_{x}(\Xi))=(\Xi,S_{y}(\Xi))$ are both regular. But from Theorem
3, only $\mathcal{A}$ can make $(\Xi,\mathcal{A})$ regular, therefore
$\mathcal{A}=S_{x}(\Xi)=S_{y}(\Xi)$.∎

From Algorithm 1 we know that $G,N,Q$ are essential elements of BM algorithm
and compose its output. For $\prec_{\mathrm{lex}}$ and
$\prec_{\mathrm{inlex}}$ cases, Theorem 6 presents us $N$ and $Q$
theoretically hence we can obtain them with little effort. According to [11],
the leading terms of $G$ are contained in the border set of $N$. Therefore, we
can get $G$ faster than compute $G$ directly with BM algorithm. Now is our
algorithm.

######  Algorithm 2.

(SPBM)

Input: A set of distinct affine points $\Xi\subset\mathbb{F}^{2}$ and fixed
$\prec_{\mathrm{lex}}$ or $\prec_{\mathrm{inlex}}$.

Output: The 3-tuple $(G,N,Q)$, where $G$ is the reduced Gröbner basis of
$\mathcal{I}(\Xi)$, $N$ is the Gröbner éscalier
$\mathrm{N}(\mathcal{I}(\Xi))$, and $Q$ is a DRINB for the Lagrange
interpolation on $\Xi$.
SPBM1. Construct lower set $S_{x}(\Xi)$ or $S_{y}(\Xi)$ according to Section
2.
SPBM2. Compute the sets $N$ and $Q$ by Theorem 6.
SPBM3. Construct the border set $L:=\\{x\cdot t:t\in N\\}\bigcup\\{y\cdot
t:t\in N\\}\setminus N$ and the matrix $B$ that is same to the
$B_{\mu\times\mu}$ in the proof of Theorem 6.
SPBM4. Goto BM2 of BM algorithm for the reduced Gröbner basis $G$.

######  Example 1.

Let

$\Xi=\\{(0,1),(0,3),(1,0),(1,2),(1,3),(1,4),(2,1),(2,2),(3,1)\\}\subset\mathbb{Q}^{2}.$

First, we choose lines $x=1,x=0,x=2,x=3$ as
$l_{0}^{y},l_{1}^{y},l_{2}^{y},l_{3}^{y}$ respectively (Shown in (a) of Figure
1), therefore we have

$S_{y}=\\{(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(2,0),(2,1),(3,0)\\},$

which is illutrated in (b) of Figure 1.

(a) $\Xi$ (b) $S_{y}$

Figure 1: The point set and related $S_{y}$ of Example 1.

Thus, by Theorem 6, we have

$\displaystyle N=\\{$ $\displaystyle
1,y,y^{2},y^{3},x,xy,x^{2},x^{2}y,x^{3}\\};$ $\displaystyle Q=\\{$
$\displaystyle
1,\frac{1}{2}y,\frac{1}{3}y^{2}-\frac{2}{3}y,\frac{1}{8}y^{3}-\frac{5}{8}y^{2}+\frac{3}{4}y,-x+1,-\frac{1}{2}xy+\frac{1}{2}y+\frac{1}{2}x-\frac{1}{2},$
$\displaystyle\frac{1}{2}x^{2}-\frac{1}{2}x,\frac{1}{2}x^{2}y-\frac{1}{2}xy-\frac{1}{2}x^{2}+\frac{1}{2}x,\frac{1}{6}x^{3}-\frac{1}{2}x^{2}+\frac{1}{3}x\\}.$

Next, from SPBM3, the border set
$L=\\{y^{4},xy^{2},xy^{3},x^{2}y^{2},x^{3}y,x^{4}\\}$ and the matrix

$B=\left(\begin{array}[]{cccc}1&1&1&\cdots\\\ 0&1&3/2&\cdots\\\
0&0&1&\cdots\\\ \vdots&\vdots&\vdots&\ddots\\\ \end{array}\right).$

Finally, turn to BM2 with these $N,Q,L,B$, we can get the reduced Gröbner
basis

$\displaystyle G=\\{$ $\displaystyle
x^{4}-6x^{3}+11x^{2}-6x,x^{3}y-3x^{2}y+2xy-x^{3}+3x^{2}-2x,$ $\displaystyle
xy^{2}-y^{2}+\frac{1}{2}x^{2}y-\frac{9}{2}xy+4y-\frac{1}{2}x^{2}+\frac{7}{2}x-3,$
$\displaystyle
y^{4}-9y^{3}+26y^{2}-\frac{9}{2}x^{2}y+\frac{15}{2}xy-27y-3x^{3}+\frac{39}{2}x^{2}-\frac{51}{2}x+9\\}.$

for $\mathcal{I}(\Xi)$ w.r.t. $\prec_{\mathrm{inlex}}$.

######  Example 2.

Given a bivariate point set

$\Xi=\\{(0,0),(0,2),(0,3),(1,1),(\frac{5}{2},0),(\frac{5}{2},1),(\frac{5}{2},2),(4,0),(4,2)\\}\subset\mathbb{Q}^{2}.$

We choose lines $y=0,y=2,y=1,y=3$ as $l_{0}^{x},l_{1}^{x},l_{2}^{x},l_{3}^{x}$
respectively (Illustrated in (a) of Figure 2), which follows that

$S_{x}=\\{(0,0),(1,0),(2,0),(0,1),(1,1),(2,1),(0,2),(1,2),(0,3)\\}.$

(a) $\Xi$ (b) $S_{x}$

Figure 2: Illustrations for Example 2.

Thus, with SPBM algorithm, we have

$\displaystyle N=\\{$ $\displaystyle
1,x,x^{2},y,xy,x^{2}y,y^{2},xy^{2},y^{3}\\},$ $\displaystyle Q=\\{$
$\displaystyle
1,\frac{1}{4}x,-\frac{4}{15}x^{2}+\frac{16}{15}x,\frac{1}{2}y,\frac{1}{8}xy,-\frac{2}{15}x^{2}y+\frac{8}{15}xy,-y^{2}+2y,$
$\displaystyle-\frac{2}{3}xy^{2}+\frac{2}{3}y^{2}+\frac{4}{3}xy-\frac{4}{3}y,\frac{1}{6}y^{3}-\frac{1}{2}y^{2}+\frac{1}{3}y\\},$
$\displaystyle G=\\{$ $\displaystyle
y^{4}-6y^{3}+11y^{2}-6y,xy^{3}-3xy^{2}+2xy,x^{2}y^{2}-2x^{2}y-\frac{7}{2}xy^{2}$
$\displaystyle+7xy-\frac{5}{4}y^{3}+\frac{25}{4}y^{2}-\frac{15}{2}y,x^{3}-\frac{13}{2}x^{2}-3xy^{2}+6xy$
$\displaystyle+10x-\frac{15}{4}y^{3}+\frac{75}{4}y^{2}-\frac{45}{2}y\\}.$

##  4 General cases

Next, we will discuss how to accelerate BM algorithm with respect to term
orders other than $\prec_{\mathrm{lex}}$ or $\prec_{\mathrm{inlex}}$. In [17],
the author proposed that if the set of points $\Xi$ is cartesian, then we can
obtain the interpolation basis without any difficulty, see Theorem 3. But in
general $\Xi$ may not be cartesian. However, we have the following
proposition.

######  Proposition 8.

There must exist at least one cartesian subset for any non-empty set of points
in $\mathbb{F}^{2}$.

######  Proof 4.

Let $\Xi$ be a non-empty set of points. Hence, there exists at least one point
$\xi\in\Xi$. But $\xi$ itself can construct a cartesian subset
$\\{\xi\\}\subset\Xi$.∎

######  Definition 3.

Let $\Xi$ be a set of points in $\mathbb{F}^{2}$ and $\Xi^{\prime}$ be a
cartesian subset of $\Xi$. We say that $\Xi^{\prime}$ is a _maximal cartesian
subset_ of $\Xi$ if any cartesian proper subset $\Xi^{\prime\prime}$ of $\Xi$
containing $\Xi^{\prime}$ is such that $\Xi^{\prime\prime}=\Xi^{\prime}$. In
addition, a _maximal row subset_ of $\Xi$ is a non-empty subset that equals
the intersection of $\Xi$ and a horizontal line.

From Proposition 8 we know that, for a set of given points, we can surely find
a maximal cartesian subset of it. Is it unique? Unfortunately, the answer is
often false.

######  Example 3.

Recall Example 2, let

$\displaystyle\Xi^{\prime}_{1}$ $\displaystyle=$
$\displaystyle\\{(0,0),(0,2),(\frac{5}{2},0),(\frac{5}{2},1),(\frac{5}{2},2),(4,0),(4,2)\\},$
$\displaystyle\Xi^{\prime}_{2}$ $\displaystyle=$
$\displaystyle\\{(0,0),(0,2),(0,3),(\frac{5}{2},0),(\frac{5}{2},2),(4,0),(4,2)\\},$
$\displaystyle\Xi^{\prime}_{3}$ $\displaystyle=$
$\displaystyle\\{(1,1),(\frac{5}{2},0),(\frac{5}{2},1),(\frac{5}{2},2)\\}.$

We can check easily that $\Xi_{1}^{\prime},\Xi_{2}^{\prime},\Xi_{3}^{\prime}$
are all maximal cartesian subsets of $\Xi$ (Illustrated in Figure 3).

(a) $\Xi^{\prime}_{1}$ (b) $\Xi^{\prime}_{2}$

(c) $\Xi^{\prime}_{3}$

Figure 3: Maximal cartesian subsets of $\Xi$, where $\bullet$ denotes the
points in $\Xi^{\prime}_{i},i=1,2,3$, while $\circ$ denotes the points in
$\Xi\backslash\Xi^{\prime}_{i}$.

######  Lemma 9.

Let $\Xi$ be a set of distinct points in $\mathbb{F}^{2}$ and $\prec$ a fixed
term order. If $\Xi^{\prime}$ is an $\mathcal{A}^{\prime}$-cartesian subset of
$\Xi$, then

$\mathcal{A}^{\prime}=\mathrm{N}_{\prec}(\Xi^{\prime})\subset\mathrm{N}_{\prec}(\Xi),$

or equivalently,

$\\{x^{i}y^{j}:(i,j)\in\mathcal{A}^{\prime}\\}=\mathrm{N}_{\prec}(\mathcal{I}(\Xi^{\prime}))\subset\mathrm{N}_{\prec}(\mathcal{I}(\Xi)).$

######  Proof 5.

From Section 2, the Gröbner éscalier
$\mathrm{N}_{\prec}(\mathcal{I}(\Xi^{\prime}))$ is the DRIMB w.r.t. $\prec$
for the bivariate Lagrange interpolation on $\Xi^{\prime}$ hence the
interpolation scheme $(\Xi^{\prime},\mathrm{N}_{\prec}(\Xi^{\prime}))$ is
regular. Since $\mathcal{A}^{\prime}\subset\mathbb{N}_{0}^{2}$ is lower and
$\Xi^{\prime}$ is $\mathcal{A}^{\prime}$-cartesian, according to Theorem 3,
$\mathcal{A}^{\prime}$ is the unique lower set making the bivariate Lagrange
interpolation on $\Xi^{\prime}$ regular. This gives

$\mathcal{A^{\prime}}=\mathrm{N}_{\prec}(\Xi^{\prime}).$

Since $\Xi^{\prime}\subset\Xi$, from [19], we know that the vanishing ideals
satisfy $\mathcal{I}(\Xi^{\prime})\supset\mathcal{I}(\Xi)$. Denote by
$G^{\prime},G$ the reduced Gröbner bases for $\mathcal{I}(\Xi^{\prime})$ and
$\mathcal{I}(\Xi)$ w.r.t. $\prec$ respectively. We will prove
$\mathrm{N}_{\prec}(\mathcal{I}(\Xi^{\prime}))\subset\mathrm{N}_{\prec}(\mathcal{I}(\Xi))$
by contradiction. For any
$x^{i}y^{j}\in\mathrm{N}_{\prec}(\mathcal{I}(\Xi^{\prime}))$, we suppose there
were some $g\in G$ such that $\mathrm{LT}(g)|x^{i}y^{j}$. By [19],

$\langle\mathrm{LT}(G^{\prime})\rangle=\langle\mathrm{LT}(\mathcal{I}(\Xi^{\prime})\rangle\supset\mathrm{LT}(\mathcal{I}(\Xi))\supset\mathrm{LT}(G).$

Therefore,
$\mathrm{LT}(g)\in\mathrm{LT}(G)\subset\langle\mathrm{LT}(G^{\prime})\rangle$
implies that there exists some $g^{\prime}\in G^{\prime}$ such that
$\mathrm{LT}(g^{\prime})|\mathrm{LT}(g)$. Since $\mathrm{LT}(g)|x^{i}y^{j}$,
we have $\mathrm{LT}(g^{\prime})|x^{i}y^{j}$ that contradicts our assumption
on $x^{i}y^{j}$, which proves that
$\mathrm{N}_{\prec}(\mathcal{I}(\Xi^{\prime}))\subset\mathrm{N}_{\prec}(\mathcal{I}(\Xi))$
due to the definition of $\mathrm{N}_{\prec}(\mathcal{I}(\Xi))$. Finally,
$\mathrm{N}_{\prec}(\Xi^{\prime})\cong\mathrm{N}_{\prec}(\mathcal{I}(\Xi^{\prime}))$
and $\mathrm{N}_{\prec}(\Xi)\cong\mathrm{N}_{\prec}(\mathcal{I}(\Xi))$
complete the proof. ∎

######  Remark 1.

For any $\mathcal{A}$-cartesian set $\Xi$, by Corollary 7, we have
$\mathcal{A}=S_{x}(\Xi)=S_{y}(\Xi)$ that obviously leads to
$\mathcal{A}=S_{x}(\Xi)=S_{y}(\Xi)=\mathrm{N}_{\prec}(\Xi)$, according to the
Lemma above, where term order $\prec$ is arbitrary.

Now comes an algorithm for constructing a maximal cartesian subset of a given
point set in $\mathbb{F}^{2}$.

######  Algorithm 3.

(Maximal Cartesian Subset Construction Algorithm) Input: A set of distinct
points $\Xi=\\{\xi^{(i)}:i=1,\ldots,\mu\\}\subset\mathbb{F}^{2}$.
Output: A maximal cartesian subset $\Xi^{\prime}$ of $\Xi$.
MCS1. Start with an empty list $\Xi^{\prime}=[\ ]$.
MCS2. If $\Xi=[\ ]$, return the set $\Xi^{\prime}$ and stop. Otherwise,
compute lower sets $S_{x}(\Xi)$ and $S_{y}(\Xi)$.
MCS3. If $S_{x}(\Xi)=S_{y}(\Xi)$, then replace $\Xi^{\prime}$ by
$\Xi^{\prime}\cup\Xi$, return the set $\Xi^{\prime}$ and stop.
MCS4. Otherwise, we first choose a maximal row subset of $\Xi$ with maximal
cardinal number, denoted by $A$. Next, delete from $\Xi$ the points either in
$A$ or have different abscissae from the points in $A$. Finally, replace
$\Xi^{\prime}$ by $\Xi^{\prime}\cup A$ and continue with MCS2.

The following theorem ensure that this algorithm will terminate in finite
steps with a maximal cartesian subset as its output.

######  Theorem 10.

The algorithm described above will stop in a finite number of loops.
Furthermore, the set $\Xi^{\prime}$ returned by the algorithm is a maximal
cartesian subset.

######  Proof 6.

As input data of Algorithm 3, point set $\Xi$ is finite. Observing that
$\\#\Xi$ decreases actually in every loop, the algorithm will terminate in a
finite number, say $M$, of loops for sure. We assume that $M>1$ since $M=1$ is
trivial.

$\Xi^{\prime}_{\mathrm{in}}$ and $\Xi^{\prime}_{\mathrm{out}}$ signify the
input and output $\Xi^{\prime}$ of MCS4 in some loop respectively. Next, we
will prove by induction on $1\leq r\leq M-1$ that in the $r$th loop
$\Xi^{\prime}_{\mathrm{out}}$ is a cartesian set. The case $r=1$ is obvious
since $\Xi^{\prime}_{\mathrm{in}}=[\ ]$ and $\Xi^{\prime}_{\mathrm{out}}$ is
clearly cartesian as a maximal row subset of $\Xi$. Assume the statement is
true for $r=l<M-1$. When $r=l+1$, by the induction hypothesis,
$\Xi^{\prime}_{\mathrm{in}}$ is cartesian. Therefore, by Corollary 7, we
assume that

$\Xi^{\prime}_{\mathrm{in}}=\\{(x_{i},y_{j}):(i,j)\in
S_{x}(\Xi^{\prime}_{\mathrm{in}})\\},$

where
$S_{x}(\Xi^{\prime}_{\mathrm{in}})=\mathrm{L}_{x}(m_{0},\ldots,m_{n_{0}})=\mathrm{L}_{y}(n_{0},\ldots,n_{m_{0}})$.
Observing the construction process of $\Xi^{\prime}$ in the algorithm, we see
easily that $n_{0}=n_{1}=\cdots=n_{m_{n_{0}}}$. Let the maximal row subset of
$\Xi$ we choose at this moment be
$A=\\{(\overline{x}^{(0)},\overline{y}),(\overline{x}^{(1)},\overline{y}),\ldots,(\overline{x}^{(k)},\overline{y})\\}$.
Due to the nature of $A$, we have $k\leq m_{n_{0}}$ and $\overline{y}\neq
y_{j},j=0,\ldots,n_{0}$.

We claim that the set $\Xi^{\prime}_{\mathrm{in}}\cup A$ is cartesian. In
fact, we will focus on the horizontal parallel lines
$l_{j}^{x}:y=y_{j},j=0,\ldots,n_{0},$ and $l_{n_{0}+1}^{x}:y=\overline{y}$.
Resume the notation in (2). $H_{j}(\Xi^{\prime}_{\mathrm{in}}\cup
A)=H_{j}(\Xi^{\prime}_{\mathrm{in}})=\\{x_{i}:0\leq i\leq
m_{j}\\},j=0,\ldots,n_{0}$, and $H_{n_{0}+1}(\Xi^{\prime}_{\mathrm{in}}\cup
A)=\\{\overline{x}^{(i)}:0\leq i\leq k\\}$. Since $\Xi^{\prime}_{\mathrm{in}}$
is $S_{x}(\Xi^{\prime}_{\mathrm{in}})$-cartesian, by Theorem 2, the relation
$H_{0}(\Xi^{\prime}_{\mathrm{in}}\cup A)\supseteq
H_{1}(\Xi^{\prime}_{\mathrm{in}}\cup A)\supseteq\cdots\supseteq
H_{n_{0}}(\Xi^{\prime}_{\mathrm{in}}\cup A)$ holds. From the description of
MCS4, we can deduce that $H_{n_{0}}(\Xi^{\prime}_{\mathrm{in}}\cup A)\supseteq
H_{n_{0}+1}(\Xi^{\prime}_{\mathrm{in}}\cup A)$, which leads to

$\displaystyle H_{0}(\Xi^{\prime}_{\mathrm{in}}\cup A)\supseteq
H_{1}(\Xi^{\prime}_{\mathrm{in}}\cup A)\supseteq\cdots\supseteq
H_{n_{0}+1}(\Xi^{\prime}_{\mathrm{in}}\cup A).$ (9)

Note that for any $\overline{x}^{(i)},0\leq i\leq k$, there exists
$h_{i}\in\\{0,1,\ldots,m_{n_{0}}\\}$ such that $\overline{x}^{(i)}=x_{h_{i}}$.
Therefore, we could find a permutation $\sigma$ of $\\{0,1,\ldots,m_{0}\\}$
satisfying $\sigma(i)=h_{i},i=0,\ldots,k,$ and
$\sigma(i)=i,i=m_{n_{0}}+1,\ldots,m_{0}$. Choose lines
$l_{i}^{y}:x=x_{\sigma(i)},i=0,\ldots,m_{0}$, that give rise to
$V_{i}(\Xi^{\prime}_{\mathrm{in}})=\\{y_{j}:0\leq j\leq
n_{\sigma(i)}\\},i=0,\ldots,m_{0}$. Since $n_{0}=n_{1}=\cdots=n_{m_{n_{0}}}$,
the relation
$V_{0}(\Xi^{\prime}_{\mathrm{in}})=V_{1}(\Xi^{\prime}_{\mathrm{in}})=\cdots=V_{m_{n_{0}}}(\Xi^{\prime}_{\mathrm{in}})\supseteq
V_{m_{n_{0}}+1}(\Xi^{\prime}_{\mathrm{in}})\supseteq\cdots\supseteq
V_{m_{0}}(\Xi^{\prime}_{\mathrm{in}})$ holds. Observing that
$V_{i}(\Xi^{\prime}_{\mathrm{in}}\cup
A)=V_{i}(\Xi^{\prime}_{\mathrm{in}})\cup\\{\overline{y}\\},i=0,\ldots,k$, and
$V_{i}(\Xi^{\prime}_{\mathrm{in}}\cup
A)=V_{i}(\Xi^{\prime}_{\mathrm{in}}),i=k+1,\ldots,m_{0}$, it is easy to get

$\displaystyle V_{0}(\Xi^{\prime}_{\mathrm{in}}\cup
A)=\cdots=V_{k}(\Xi^{\prime}_{\mathrm{in}}\cup A)\supseteq
V_{k+1}(\Xi^{\prime}_{\mathrm{in}}\cup A)\supseteq\cdots\supseteq
V_{m_{0}}(\Xi^{\prime}_{\mathrm{in}}\cup A).$

Thus together with (9),
$\Xi^{\prime}_{\mathrm{out}}=\Xi^{\prime}_{\mathrm{in}}\cup A$ is cartesian
due to Theorem 2, hence our statement is true.

For the $M$th loop, if $\Xi=[\ ]$, then $\Xi^{\prime}$ here equals to the
$\Xi^{\prime}_{\mathrm{out}}$ of the MCS4 of the $(M-1)$th loop that is
cartesian due to the statement above. Otherwise, since the algorithm stops in
MCS3 of this loop, $\Xi$ is a non-empty cartesian set. Similar to the
arguments above, we can prove that
$\Xi^{\prime}=\Xi^{\prime}_{\mathrm{out}}\cup\Xi$ is also cartesian.

Finally, we should verify that the output $\Xi^{\prime}$ of the algorithm is
maximal. Otherwise, there must exist a maximal
$S_{x}(\Xi^{\prime\prime})$-cartesian subset $\Xi^{\prime\prime}$ of $\Xi$
satisfying $\Xi^{\prime\prime}\supsetneqq\Xi^{\prime}$. Take a point
$\xi_{0}=(x_{i_{0}},y_{j_{0}})$ with
$(i_{0},j_{0})=\min_{\prec_{\mathrm{inlex}}}\\{(i,j)\in
S_{x}(\Xi^{\prime\prime}):(x_{i},y_{j})\in\Xi^{\prime\prime}\setminus\Xi^{\prime}\\}$.
Suppose there exists a point in $\Xi^{\prime}$ sharing the ordinate with
$\xi_{0}$. If it is chosen as a point in the maximal row subset in MCS4 of
some loop, by the definition of $\xi_{0}$, we know that $\xi_{0}$ is surely
contained in the set $\Xi$ of that step, which contradicts the definition of
the maximal row subset. Otherwise, it must appear in the cartesian set $\Xi$
in MCS3 in the final loop. Then, by the definition of $\xi_{0}$, it should be
contained in $\Xi$ hence the output set $\Xi^{\prime}$, which introduces a
contradiction. If there does not exist a point in $\Xi^{\prime}$ sharing the
ordinate with $\xi_{0}$, since $\Xi^{\prime\prime}$ is also cartesian, by
Theorem 2, it is easily to see that $\xi_{0}$ must remain in $\Xi$ in every
loop, which contradicts the termination condition. As a result, the output of
the Algorithm 3 is a maximal cartesian subset. ∎

Let us continue with the setup and notation in Algorithm 3, and assume that
the final output of it is $\Xi^{\prime}$ who is
$S_{x}(\Xi^{\prime})$-cartesian . We now discuss how to preprocess the BM
algorithm with the help of $\Xi^{\prime}$.

Define an order $\prec_{\Xi}$ on the set $\Xi$. Let
$\xi^{(1)},\xi^{(2)}\in\Xi$. We say that $\xi^{(1)}\prec_{\Xi}\xi^{(2)}$ if
one of the following conditions holds:

  * (1)

$\xi^{(1)}\in\Xi^{\prime}$, and $\xi^{(2)}\in\Xi\backslash\Xi^{\prime}$.

  * (2)

$\xi^{(1)}=(x_{i_{1}},y_{j_{1}}),\xi^{(2)}=(x_{i_{2}},y_{j_{2}})\in\Xi^{\prime}$
and $(i_{1},j_{1})\prec_{\mathrm{inlex}}(i_{2},j_{2})$ with $(i_{k},j_{k})\in
S_{x}(\Xi^{\prime}),k=1,2$.

It should be noticed that the order is not total. For the points in
$\Xi\backslash\Xi^{\prime}$, any order of them can be interpreted as
increasing. Hereafter, we will suppose that the points in
$\Xi=\\{\xi^{(1)},\ldots,\xi^{(\\#\Xi)}\\}$ have been ordered increasingly
w.r.t. $\prec_{\Xi}$, namely $\xi^{(i)}\prec_{\Xi}\xi^{(j)},0\leq
i<j\leq\\#\Xi$. By the definition of $\prec_{\Xi}$, we have
$\Xi^{\prime}=\\{\xi^{(1)},\ldots,\xi^{(\\#\Xi^{\prime})}\\}$.

According to Lemma 9, $N^{\prime}=\\{x^{i}y^{j}:(i,j)\in
S_{x}(\Xi^{\prime})\\}\subset N$, with $N$ as a member of the 3-tuple output
of BM algorithm. Thus the other monomials of $N$ are obviously contained in
$\mathbb{T}^{2}\backslash N^{\prime}$. Notice that the generators of
$\mathbb{T}^{2}\backslash N^{\prime}$ are located in the border of
$N^{\prime}$, denoted by $L$, we can continue to spot the elements in $L$ by
BM algorithm to complete $N$.

Next, we will pay attention to the computation of the Newton basis. Since
$\Xi^{\prime}$ is cartesian, recalling Proposition 4, we can construct the
polynomials $\phi_{ij}^{x}$ w.r.t. $S_{x}(\Xi^{\prime})$. Order
$\phi_{ij}^{x},(i,j)\in S_{x}(\Xi^{\prime})$, increasingly w.r.t. $(i,j)$
under $\prec_{\mathrm{inlex}}$, and denote them as
$q_{1},q_{2},\ldots,q_{\\#\Xi^{\prime}}$. Set the matrix

$B=\left(\begin{array}[]{cccc}q_{1}(\xi^{(1)})&q_{1}(\xi^{(2)})&\cdots&q_{1}(\xi^{(\\#\Xi^{\prime})})\\\
q_{2}(\xi^{(1)})&q_{2}(\xi^{(2)})&\cdots&q_{2}(\xi^{(\\#\Xi^{\prime})})\\\
\vdots&\vdots&&\vdots\\\
q_{\\#\Xi^{\prime}}(\xi^{(1)})&q_{\\#\Xi^{\prime}}(\xi^{(2)})&\cdots&q_{\\#\Xi^{\prime}}(\xi^{(\\#\Xi^{\prime})})\\\
\end{array}\right).$ (10)

By Proposition 4, $B$ is obviously upper unitriangular which implies that the
polynomials $q_{1},q_{2},\ldots,q_{\\#\Xi^{\prime}}$ constitute a Newton basis
for $\mathcal{P}_{\prec}(\Xi^{\prime})=\mathrm{Span}_{\mathbb{F}}N^{\prime}$.

All in all, with the notation above, we get our preprocessing procedure for BM
algorithm.

######  Algorithm 4.

(GPBM)

Input: A set of distinct points $\Xi\subset\mathbb{F}^{2}$ and a term order
$\prec$.

Output: The 3-tuple $(G,N,Q)$.

GPBM1: Get a maximal cartesian subset $\Xi^{\prime}$ of $\Xi$ by Algorithm 3;
GPBM2: Compute the lower set $S_{x}(\Xi^{\prime})$ w.r.t. $\Xi^{\prime}$, the
set $N:=\\{x^{i}y^{j}:(i,j)\in S_{x}(\Xi^{\prime})\\}$, and the set
$Q:=\\{q_{1},q_{2},\ldots,q_{\\#\Xi^{\prime}}\\}$ where the $q_{i}$’s are as
in (10).
GPBM3: Construct $L:=\\{x\cdot t:t\in N\\}\bigcup\\{y\cdot t:t\in
N\\}\setminus N$ and the matrix $B$ that is same to (10).
GPBM4: Goto BM2 of the BM algorithm to complete the computation and get the
whole output.

##  5 Implementation and Timings

From the above section, we can see easily that our preprocessing paradigm is
more suitable to the cases where the constructed maximal cartesian subset
$\Xi^{\prime}$ forms a relatively large proposition in $\Xi$. Especially, when
the field $\mathbb{F}$ is finite, our preprocessing will play a more important
role in consideration of the nature of finite fields. In this section, we will
present some experimental results to compare the effectiveness of our paradigm
with the classical BM. First see an example with point set of small size.

######  Example 4.

We choose the field $\mathbb{F}_{7}$, and let

$\displaystyle\Xi=\\{$ $\displaystyle(0,0),(0,1),(0,4),(0,5),(1,0),$
$\displaystyle(1,1),(1,4),(1,6),(2,1),(2,2),$
$\displaystyle(2,6),(3,2),(4,2),(4,5),(4,6),$
$\displaystyle(5,1),(5,5),(5,6),(6,0),(6,2)\\}.$

By Algorithm 3, we can construct the maximal cartesian subset

$\Xi^{\prime}=\\{(0,1),(1,1),(2,1),(5,1),(1,6),(2,6),(5,6),(1,0),(1,4)\\}$

hence get

$\displaystyle N=$ $\displaystyle\\{1,x,x^{2},x^{3},y,xy,x^{2}y,y^{2}\\},$
$\displaystyle Q=$
$\displaystyle\\{1,x,4x^{2}+3x,2x^{3}+x^{2}+4x,3y+4,3xy+4x+4y+3,$
$\displaystyle\phantom{\\{}2x^{2}y+5x^{2}+xy+6x+4y+3,6y^{2}+1,2y^{3}+5y\\},$
$\displaystyle L=$
$\displaystyle\\{y^{4},xy^{2},xy^{3},x^{2}y^{2},x^{3}y,x^{4}\\},$
$\displaystyle B=$ $\displaystyle\left(\begin{array}[]{cccc}1&1&1&\cdots\\\
0&1&2&\cdots\\\ 0&0&1&\cdots\\\ \vdots&\vdots&\vdots&\ddots\\\
\end{array}\right).$

Put these $N,Q,L,B$ into BM algorithm, we can get the final output

$\displaystyle N=$
$\displaystyle\\{1,x,x^{2},x^{3},y,xy,x^{2}y,y^{2},y^{3},xy^{2},y^{4},xy^{3},x^{2}y^{2},x^{3}y,x^{4},y^{5},xy^{4},x^{2}y^{3},$
$\displaystyle\phantom{\\{}x^{3}y^{2},x^{4}y\\},$ $\displaystyle Q=$
$\displaystyle\\{1,x,4x^{2}+3x,2x^{3}+x^{2}+4x,3y+4,3xy+4x+4y+3,$
$\displaystyle\phantom{\\{}2x^{2}y+5x^{2}+xy+6x+4y+3,6y^{2}+1,2y^{3}+5y,xy^{2}+6y^{2}+6x+1,$
$\displaystyle\phantom{\\{}y^{4}+3y^{3}+6y^{2}+4y,5xy^{3}+5y^{4}+3y^{3}+2xy+2y^{2}+4y,$
$\displaystyle\phantom{\\{}6x^{2}y^{2}+xy^{2}+x^{2}+6x,\ldots\\},$
$\displaystyle G=$ $\displaystyle\\{y^{6}+3y^{5}+2y^{4}+6y^{3}+4y^{2}+5y,$
$\displaystyle\phantom{\\{}xy^{5}+x^{4}y+6x^{3}y^{2}+x^{2}y^{3}+5xy^{4}+6y^{5}+6x^{4}+2x^{3}y+6x^{2}y^{2}+3xy^{3}+$
$\displaystyle\phantom{\\{}3y^{4}+6x^{3}+6x^{2}y+2xy^{2}+6y^{3}+x^{2}+2xy+6y^{2}+x,$
$\displaystyle\phantom{\\{}x^{2}y^{4}+x^{4}y+3x^{2}y^{3}+3xy^{4}+5y^{5}+x^{4}+6x^{3}y+3x^{2}y^{2}+2xy^{3}+4y^{4}+$
$\displaystyle\phantom{\\{}6x^{3}+4y^{3}+6x^{2}+2xy+3y^{2}+x+5y,\ldots\\}.$

In the following, several tables show the timings for the computations of BM-
problems on sets of distinct random points w.r.t. the term order
$\prec_{\mathrm{lex}}$ or $\prec_{\mathrm{tdinlex}}$. The algorithms presented
in the paper were implemented on Maple 12 installed on a laptop with 2 Gb RAM
and 1.8 GHz CPU.

Take the field $\mathbb{F}_{23}$, we have

$\\#\Xi$ | 200 | 300 | 400 | 500
---|---|---|---|---
BM | 4.968 s | 15.359 s | 34.609 s | 61.172 s
SPBM | 1.438 s | 3.766 s | 7.141 s | 7.969 s

For $\mathbb{F}_{37}$, we have

$\\#\Xi$ | 300 | 600 | 900 | 1200
---|---|---|---|---
BM | 16.265 s | 121.766 s | 420.219 s | 1060.203 s
SPBM | 4.172 s | 25.125 s | 82.000 s | 132.719 s

For $\mathbb{F}_{17}$, we have

$\\#\Xi$ | 100 | 150 | 200 | 250
---|---|---|---|---
BM | 0.875 s | 2.421 s | 4.953 s | 8.188 s
GPBM | 0.797 s | 2.125 s | 4.250 s | 5.641 s
Preprocessing | 0.015 s | 0.094 s | 0.172 s | 0.391 s
$\\#\Xi^{\prime}/\\#\Xi$ | 0.310 | 0.393 | 0.430 | 0.616

Take the field $\mathbb{F}_{29}$, we have

$\\#\Xi$ | 200 | 400 | 600 | 800
---|---|---|---|---
BM | 5.672 s | 38.063 s | 112.156 s | 235.813 s
GPBM | 5.562 s | 36.906 s | 105.828 s | 135.609 s
Preprocessing | 0.046 s | 0.313 s | 1.671 s | 8.125 s
$\\#\Xi^{\prime}/\\#\Xi$ | 0.125 | 0.178 | 0.328 | 0.711

## References

  * [1] D. A. Cox, J. Little, D. O’Shea, Using Algebraic Geometry, 2nd Edition, Vol. 185 of Graduate Texts in Mathematics, Springer, New York, 2005.
  * [2] T. Sauer, Polynomial interpolation in several variables: Lattices, differences, and ideals, in: K. Jetter, M. Buhmann, W. Haussmann, R. Schaback, J. Stöckler (Eds.), Topics in Multivariate Approximation and Interpolation, Vol. 12 of Studies in Computational Mathematics, Elsevier, Amsterdam, 2006, pp. 191–230.
  * [3] C. de Boor, Ideal interpolation, in: C. K. Chui, M. Neamtu, L. L. Schumaker (Eds.), Approximation Theory XI: Gatlinburg 2004, Nashboro Press, Brentwood TN, 2005, pp. 59–91.
  * [4] S. Sakata, Gröbner bases and coding theory, in: B. Buchberger, F. Winkler (Eds.), Gröbner Bases and Applications, Vol. 251 of London Mathematical Society Lecture Notes Series, Cambridge University Press, New York, 1998, pp. 470–485.
  * [5] M. Sala, Gröbner bases, coding, and cryptography: a guide to the state-of-art, in: M. Sala, T. Mora, L. Perret, S. Sakata, C. Traverso (Eds.), Gröbner Bases, Coding, and Cryptography, Springer, Berlin, 2009, pp. 1–8.
  * [6] L. Robbiano, Gröbner bases and statistics, in: B. Buchberger, F. Winkler (Eds.), Gröbner Bases and Applications, Vol. 251 of London Mathematical Society Lecture Notes Series, Cambridge University Press, New York, 1998, pp. 179–204.
  * [7] R. Laubenbacher, B. Stigler, A computational algebra approach to the reverse engineering of gene regulatory networks, J. Theoret. Biol. 229 (4) (2004) 523–537.
  * [8] W. Just, B. Stigler, Computing Gröbner bases of ideals of few points in high dimensions, ACM Commun. Comput. Algebra 40 (3-4) (2006) 67–78.
  * [9] H. Möller, B. Buchberger, The construction of multivariate polynomials with preassigned zeros, in: J. Calmet (Ed.), Computer Algebra: EUROCAM ’82, Vol. 144 of Lecture Notes in Computer Science, Springer, Berlin, 1982, pp. 24–31.
  * [10] J. C. Faugère, P. Gianni, D. Lazard, T. Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symbolic Comput. 16 (4) (1993) 329–344.
  * [11] M. G. Marinari, H. M. Möller, T. Mora, Gröbner bases of ideals defined by functionals with an application to ideals of projective points, Appl. Algebra Engrg. Comm. Comput. 4 (2) (1993) 103–145.
  * [12] J.Abbott, A.Bigatti, M.Kreuzer, L.Robbiano, Computing ideals of points, J. Symbolic Comput. 30 (2000) 341–356.
  * [13] L. Cerlienco, M. Mureddu, From algebraic sets to monomial linear bases by means of combinatorial algorithms, Discrete Math. 139 (1-3) (1995) 73–87.
  * [14] S. Gao, V. M. Rodrigues, J. Stroomer, Gröbner basis structure of finite sets of points (Preprint).
  * [15] B. Felszeghy, B. Ráth, L. Rónyai, The lex game and some applications, J. Symbolic Comput. 41 (6) (2006) 663–681.
  * [16] T. Sauer, Lagrange interpolation on subgrids of tensor product grids, Math. Comp. 73 (245) (2004) 181–190.
  * [17] N. Crainic, Multivariate Birkhoff-Lagrange interpolation schemes and cartesian sets of nodes, Acta Math. Univ. Comenian.(N.S.) LXXIII (2) (2004) 217–221.
  * [18] T. Chen, T. Dong, S. Zhang, The Newton interpolation bases on lower sets, J. Inf. Comput. Sci. 3 (3) (2006) 385–394.
  * [19] T. Becker, V. Weispfenning, Gröbner Bases, Vol. 141 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1993.
  * [20] R. Lorentz, Multivariate Birkhoff Interpolation, Vol. 1516 of Lecture Notes in Mathematics, Springer, Heidelberg, 1992.
  * [21] C. de Boor, Interpolation from spaces spanned by monomials, Adv. Comput. Math. 26 (1) (2007) 63–70.