# Bivariate Quasi-Tower Sets and Their Associated Lagrange Interpolation Bases

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

###### Abstract

As we all known, there is still a long way for us to solve arbitrary
multivariate Lagrange interpolation in theory. Nevertheless, it is well
accepted that theories about Lagrange interpolation on special point sets
should cast important lights on the general solution. In this paper, we
propose a new type of bivariate point sets, quasi-tower sets, whose geometry
is more natural than some known point sets such as cartesian sets and tower
sets. For bivariate Lagrange interpolation on quasi-tower sets, we construct
the associated degree reducing interpolation monomial and Newton bases w.r.t.
common monomial orderings theoretically. Moreover, by inputting these bases
into Buchberger-Möller algorithm, we obtain the reduced Gröbner bases for
vanishing ideals of quasi-tower sets much more efficiently than before.

###### keywords:

Bivariate Lagrange interpolation , Quasi-Tower set , Degree reducing
interpolation basis , Buchberger-Möller algorithm

###### MSC:

13P10 , 65D05 , 12Y05

fundfundfootnotetext: This work was supported in part by the National Grand
Fundamental Research 973 Program of China (No. 2004CB318000).

##  1 Introduction

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

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

where $\Pi^{2}:=\mathbb{F}[x,y]$ is the bivariate polynomial ring over
$\mathbb{F}$.

In most cases, for fixed monomial ordering $\prec$, only the bases for the
_degree reducing interpolation space_ $\mathcal{P}\subset\Pi^{2}$(see [1]) are
pursued for Lagrange interpolation (1). Let $\\{p_{1},\ldots,p_{\mu}\\}$ be a
basis for $\mathcal{P}$ satisfying $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 certain reordering of $\Xi$, then we call $\\{p_{1},\ldots,p_{\mu}\\}$ a
_degree reducing interpolation Newton basis_(DRINB) w.r.t. $\prec$ for (1).
Moreover, $\mathcal{N}_{\prec}(\Xi)$, the _Gröbner éscalier_ of
$\mathcal{I}(\Xi)$ w.r.t. $\prec$(see [2]), is the _degree reducing
interpolation monomial basis_(DRIMB) w.r.t. $\prec$ for (1).

Let $\mathcal{I}(\Xi)\subset\Pi^{2}$ be the vanishing ideal of $\Xi$ and
$\mathcal{G}_{\prec}(\Xi)$ the reduced Gröbner basis for $\mathcal{I}(\Xi)$
w.r.t.$\prec$. In 1982, [3] proposed Buchberger-Möller(BM for short) algorithm
for computing bases of vanishing ideals. Specifically, with inputted $\Xi$ and
$\prec$, BM algorithm outputs $\mathcal{G}_{\prec}(\Xi)$,
$\mathcal{N}_{\prec}(\Xi)$, and a DRINB for Lagrange interpolation (1), namely
arbitrary bivariate Lagrange interpolation can be solved with it algorithmly.
Nonetheless, the poor complexity of BM algorithm(see [4]) severely constrains
its applications.

Since the geometry of $\Xi$ is a dominant factor for the structures of
$\mathcal{G}_{\prec}(\Xi)$ and $\mathcal{N}_{\prec}(\Xi)$, theories about
Lagrange interpolation on point sets with describable special geometries will
certainly throw light on the general theoretical solution of (1). [5, 6]
studied multivariate Lagrange interpolation on cartesian sets(aka lower point
sets) and [7] investigated bivariate Lagrange interpolation on tower sets.

This paper will introduce, in Section 3, a new type of bivariate point sets,
quasi-tower sets, that is more natural than cartesian and tower sets. As the
section of main results, Section 4 will discover the degree reducing
interpolation bases w.r.t. certain common monomial ordering such as graded lex
order for bivariate Lagrange interpolation on quasi-tower sets theoretically.
Finally, Section 5 will give an algorithm for computing reduced Gröbner bases
for vanishing ideals of quasi-tower sets.

The following section will serve as a preparation for the paper.

##  2 Preliminary

Let $\mathbb{N}_{0}$ and $\mathbb{T}^{2}$ be the monoid of nonnegative
integers and bivariate monomials in $\Pi^{2}$ respectively. A monomial in
$\mathbb{T}^{2}$ has the form $X^{\bm{\alpha}}:=x^{\alpha_{1}}y^{\alpha_{2}}$
for $\bm{\alpha}=(\alpha_{1},\alpha_{2})\in\mathbb{N}_{0}^{2}$.

As in [8], we use
$\prec_{\text{lex}},\prec_{\text{invlex}},\prec_{\text{grlex}}$, and
$\prec_{\text{grevlex}}$ to represent lexicographic order, inverse
lexicographic order, graded lex order, and graded reverse lex order
respectively. Hereafter, we always assume that $y\prec x$ for any fixed
monomial ordering $\prec$.

For a nonzero $f\in\Pi^{2}$, we let $\mathrm{LM}_{\prec}(f)$ and
$\bm{\delta_{\prec}(f)}$ signify the _leading monomial_ and _leading
bidegree_($\mathrm{LM}(f)=X^{\bm{\delta_{\prec}(f)}}$) of $f$ w.r.t. $\prec$
respectively. Furthermore, set

$f\prec g:=\bm{\delta_{\prec}(f)}\prec\bm{\delta_{\prec}(g)}.$

Let $\mathcal{A}$ be an arbitrary finite subset of $\mathbb{N}_{0}^{2}$. We
say that it is _lower_ if

$\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}$

always holds for any $\bm{\alpha}=(\alpha_{1},\alpha_{2})\in\mathcal{A}$. When
$\mathcal{A}$ is lower, we let $m_{j}=\max_{(h,j)\in\mathcal{A}}h,0\leq
j\leq\nu$, with $\nu=\max_{(0,k)\in\mathcal{A}}k$. Since $\mathcal{A}$ can be
determined uniquely by $(\nu+1)$-tuple $(m_{0},m_{1},\ldots,m_{\nu})$, we
represent it as

$\mathcal{A}=\mathrm{L}_{x}(m_{0},m_{1},\ldots,m_{\nu}).$

Likewise, it can also be represented as
$\mathrm{L}_{y}(n_{0},\ldots,n_{m_{0}})$ with
$n_{i}=\max_{(i,k)\in\mathcal{A}}k$, $0\leq i\leq m_{0}$.

As in [7], we constructed two particular lower sets
$S_{x}(\Xi),S_{y}(\Xi)\subset\mathbb{N}_{0}^{2}$ from $\Xi$. In more details,
we cover $\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$. Set

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

which equals to $\mathrm{L}_{x}(m_{0},m_{1},\ldots,m_{\nu})$. In like fashion,
we cover $\Xi$ by lines $l_{0}^{y},l_{1}^{y},\ldots,l_{\lambda}^{y}$ parallel
to the $y$-axis and denote the points on $l_{i}^{y}$ by
$u_{i0}^{y},\ldots,u_{i,n_{i}}^{y}$ with $n_{0}\geq\cdots\geq n_{\lambda}\geq
0$. We have

$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, the sets of abscissae and ordinates are defined as

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

A point set $\Xi$ satisfying $S_{x}(\Xi)=S_{y}(\Xi)$ is called a cartesian set
that has the following property:

######  Proposition 1.

[7] A point set $\Xi\subset\mathbb{F}^{2}$ is cartesian if and only if

$H_{0}(\Xi)\supseteq H_{1}(\Xi)\supseteq\cdots\supseteq H_{\nu}(\Xi)$

or

$V_{0}(\Xi)\supseteq V_{1}(\Xi)\supseteq\cdots\supseteq V_{\lambda}(\Xi).$

Enlightened by the notion of cartesian sets, [7] introduced tower sets in
$\mathbb{F}^{2}$ as follows.

######  Definition 1.

[7] We say that a set $\Xi$ of distinct points in $\mathbb{F}^{2}$ is
$x$-_tower_ if lower set
$S_{x}(\Xi)=\mathrm{L}_{x}(m_{0},m_{1},\ldots,m_{\nu})\subset\mathbb{N}_{0}^{2}$
with $m_{0}>m_{1}>\cdots>m_{\nu}\geq 0$ such that

$\Xi:=\\{(x_{ij},y_{j}):(i,j)\in S_{x}(\Xi)\\},$

where $x_{ij}\in H_{0}(\Xi),(i,j)\in S_{x}(\Xi)$, are distinct for fixed $j$.
Its full name is $S_{x}(\Xi)$-$x$-_tower_ set. Similarly, if lower set
$S_{y}(\Xi)=\mathrm{L}_{y}(n_{0},n_{1},\ldots,n_{\lambda})\subset\mathbb{N}_{0}^{2}$,
$n_{0}>n_{1}>\cdots>n_{\lambda}\geq 0$, such that

$\Xi:=\\{(x_{i},y_{ij}):(i,j)\in S_{y}(\Xi)\\},$

where $y_{ij}\in V_{0}(\Xi),(i,j)\in S_{y}(\Xi)$, are distinct for fixed $i$,
we will call $\Xi$ a $y$-_tower_ set(or $S_{y}(\Xi)$-$y$-_tower_ set in its
full name).

About the bivariate Lagrange interpolation on a tower set, [7] proved the
succeeding theorem.

######  Theorem 2.

[7] Given an $x$-tower set $\Xi\subset\mathbb{F}^{2}$. The DRIMB w.r.t.
$\prec_{\mathrm{grlex}}$ or $\prec_{\mathrm{lex}}$ for (1) is

$\\{x^{i}y^{j}:(i,j)\in S_{x}(\Xi)\\}.$

If $\Xi$ is $y$-tower, then the DRIMB w.r.t. $\prec_{\mathrm{grevlex}}$ or
$\prec_{\mathrm{invlex}}$ for (1) is

$\\{x^{i}y^{j}:(i,j)\in S_{y}(\Xi)\\}.$

##  3 Quasi-Tower Sets

In this section, we will introduce the notion of generalized tower and quasi-
tower sets and compare them with tower sets and cartesian sets.

######  Definition 2.

Let $\Xi$ be a set of distinct points in $\mathbb{F}^{2}$. We call $\Xi$ a
_generalized $x$-tower_ set if
$S_{x}(\Xi)=\mathrm{L}_{x}(m_{0},m_{1},\ldots,m_{\nu})\subset\mathbb{N}_{0}^{2}$
with $m_{0}>m_{1}>\cdots>m_{\nu}\geq 0$ such that

$\Xi:=\\{(x_{ij},y_{j}):(i,j)\in S_{x}(\Xi)\\},$

where $x_{ij}$ are distinct for fixed $j$. In like fashion, if lower set
$S_{y}(\Xi)=\mathrm{L}_{y}(n_{0},n_{1},\ldots,n_{\lambda})\subset\mathbb{N}_{0}^{2}$,
$n_{0}>n_{1}>\cdots>n_{\lambda}\geq 0$, such that

$\Xi:=\\{(x_{i},y_{ij}):(i,j)\in S_{y}(\Xi)\\},$

where $y_{ij}$ are distinct for fixed $i$, we will call $\Xi$ a _generalized
$y$-tower_ set.

Observe Definition 1 and 2. We find that they are similar to each other except
two more conditions in Definition 1 which implies that a tower set is always
generalized tower, namely the notion of generalized tower sets is actually a
generalization of tower sets’. Therefore, what interests us most now should be
the generalized tower sets that are not tower.

######  Definition 3.

If $\Xi\subset\mathbb{F}^{2}$ is a generalized $x$-tower set that is not
$x$-tower, then we call it a _quasi- $x$-tower_ set. Similarly, a
non-$y$-tower generalized $y$-tower set is called a _quasi- $y$-tower_ set.

From Definition 2 and 3 we know that the geometry of quasi-tower sets is much
freer than tower sets’ in the sense that they need not fulfill the two extra
conditions that demand $x_{ij}\subset H_{0}(\Xi)$ for $x$-tower and
$x_{ij}\subset V_{0}(\Xi)$ for $y$-tower. The following propositions will show
us how did quasi-tower sets acquire their name.

######  Proposition 3.

Let $\Xi$ be a quasi-$x$-tower set with
$S_{x}(\Xi)=\mathrm{L}_{x}(m_{0},\ldots,m_{\nu})$. If $B\subset\mathbb{F}^{2}$
is a set of distinct horizontal points such that $B\cap\Xi=\emptyset$ and
$\bigcup_{i=0}^{\nu}H_{i}(\Xi)\subsetneq H_{0}(B)$, then $\Xi\cup B$ is
$x$-tower and will be known as a _derived $x$-tower_ set from $\Xi$ with _base
set_ $B$.

######  Proof 1.

By hypothesis, we assume that
$S_{y}(\Xi)=\mathrm{L}_{y}(n_{0},n_{1},\ldots,n_{\lambda})$ and
$B=\\{(x_{0}^{B},y^{B}),(x_{1}^{B},y^{B}),\ldots,(x_{m_{B}}^{B},y^{B})\\}$
where $x_{i}^{B}\neq x_{j}^{B},i\neq j$, and
$y^{B}\notin\bigcup_{j=0}^{\lambda}V_{j}(\Xi)$. Recall the construction
process of $S_{x}(\Xi)$ in Section 2. Since
$\bigcup_{i=0}^{\nu}H_{i}(\Xi)\subsetneq H_{0}(B)$ and $\Xi$ is
quasi-$x$-tower, we can deduce easily that

$S_{x}(\Xi\cup B)=\mathrm{L}_{x}(m_{B},m_{0},\ldots,m_{\nu}),$

where $m_{B}>m_{0}>\cdots>m_{\nu}\geq 0$. From Definition 2 and 3, $\Xi$ is
quasi-$x$-tower implies that

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

where $x_{ij}^{\Xi}$ are distinct for fixed $j$, hence, we have

$\Xi\cup B=\\{(x_{ij},y_{j}):(i,j)\in S_{x}(\Xi\cup B)\\}$

where

$\displaystyle x_{i0}$ $\displaystyle=x_{i}^{B},y_{0}=y^{B},$ $\displaystyle
i$ $\displaystyle=0,1,\ldots,m_{B},$ $\displaystyle x_{i,j+1}$
$\displaystyle=x_{ij}^{\Xi},y_{j+1}=y_{j}^{\Xi},$ $\displaystyle i$
$\displaystyle=0,1,\ldots,m_{j}^{\Xi},j=0,1,\ldots,\nu,$

and $x_{ij}$ are distinct for fixed $j$. Therefore, by Definition 1, $\Xi\cup
B$ is $x$-tower. ∎

In the same way, we can prove the following proposition for quasi-$y$-tower
sets.

######  Proposition 4.

Let $\Xi$ be a quasi-$y$-tower set with
$S_{y}(\Xi)=\mathrm{L}_{y}(n_{0},n_{1},\ldots,n_{\lambda})$. If
$B\subset\mathbb{F}^{2}$ is a set of distinct vertical points such that
$B\cap\Xi=\emptyset$ and $\bigcup_{j=0}^{\lambda}V_{j}(\Xi)\subsetneq
V_{0}(B)$, then $\Xi\cup B$ is $y$-tower and will be named a _derived
$y$-tower_ set from $\Xi$ with _base set_ $B$.

Proposition 3 and 4 imply the following corollary immediately.

######  Corollary 5.

Let $\Xi\subset\mathbb{F}^{2}$ be a quasi-tower set. Then there are infinite
derived tower sets from $\Xi$.

######  Example 1.

$\displaystyle\Xi=\\{$
$\displaystyle(0.2,0.4),(0.4,0.4),(0.8,0.4),(1,0.4),(1.2,0.4),(1.6,0.4),$
$\displaystyle(2,0.4),(0,0.6),(0.6,0.6),(1.4,0.6),(1.8,0.6),(2.2,0.6),$
$\displaystyle(0.6,1.1),(1,1.1),(1.2,1.1),(1.8,1.1),(1.2,1.45),(1.8,1.45),$
$\displaystyle(2.4,1.45),(0.2,1.8),(1.4,1.8)\\}\subset\mathbb{Q}^{2}$

is a quasi-$x$-tower set(shown in (a) of Figure 1) and

$\displaystyle B=\\{$
$\displaystyle(0,0),(0.2,0),(0.4,0),(0.6,0),(0.8,0),(1,0),$
$\displaystyle(1.2,0),(1.4,0),(1.6,0),(1.8,0),(2,0),(2.2,0),(2.4,0)\\}.$

Obviously, $\Xi\cup B$(shown in (b) of Figure 1) is an $x$-tower set that is
derived from $\Xi$ with base set $B$.

(a) $\Xi$ (b) $\Xi\cup B$

Figure 1: A quasi-$x$-tower set $\Xi$ and a derived $x$-tower set $\Xi\cup B$
from $\Xi$ with base set $B$

Proposition 6 of [7] discovered the relation between cartesian sets and tower
sets. The next proposition shows the relation between cartesian sets and
quasi-tower sets.

######  Proposition 6.

A quasi-tower set is not a cartesian set and vice versa.

######  Proof 2.

From Definition 3 we can deduce easily that a point set
$\Xi\subset\mathbb{F}^{2}$ is quasi-$x$-tower if and only if it is a
generalized $x$-tower set such that there exists at least one point
$\xi\in\Xi$ whose abscissa is not in $H_{0}(\Xi)$. Proposition 1 implies the
statement of this proposition immediately for quasi-$x$-tower sets. The
quasi-$y$-tower cases can be proved similarly. ∎

##  4 Bases for Lagrange Interpolation on Quasi-Tower Sets

In this section, we will present the degree reducing interpolation bases for
Lagrange interpolation on quasi-tower sets w.r.t.
$\prec_{\mathrm{lex}},\prec_{\mathrm{grevlex}}$ etc. theoretically. Let us
begin with the following lemmas.

######  Lemma 7.

Fix monomial ordering $\prec_{\mathrm{grlex}}$. Let

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

be an $x$-tower set in $\mathbb{F}^{2}$ with
$S_{x}(\Xi^{\prime})=\mathrm{L}_{x}(m_{0},m_{1},\ldots,m_{\nu})$. If
$\mathcal{G}_{\prec_{\mathrm{grlex}}}(\Xi^{\prime})=\\{g_{1},g_{2},\ldots,g_{s}\\}$
with $g_{s}\prec_{\mathrm{grlex}}\cdots\prec_{\mathrm{grlex}}g_{1}$, then

  1. (i)

$s=\nu+2$.

  2. (ii)

$g_{1}=(x-x_{0,0})(x-x_{1,0})\cdots(x-x_{m_{0},0})$.

  3. (iii)

$g_{s}=(y-y_{0})(y-y_{1})\cdots(y-y_{\nu})$.

  4. (iv)

$g_{j}\in\langle y-y_{0}\rangle$ and

$\mathrm{LM}_{\prec_{\mathrm{lex}}}(g_{j})=\mathrm{LM}_{\prec_{\mathrm{grlex}}}(g_{j})=x^{m_{j-1}+1}y^{j-1},\quad
j=2,\ldots,s-1.$

  5. (v)

$\mathcal{I}(\\{(x_{0,0},y_{0}),\ldots,(x_{m_{0},0},y_{0})\\})=\langle
g_{1},y-y_{0}\rangle.$

######  Proof 3.

From Theorem 2 we know that
$\mathcal{N}_{\prec_{\mathrm{grlex}}}(\Xi^{\prime})=\\{x^{i}y^{j}:(i,j)\in
S_{x}(\Xi^{\prime})\\}$. Since
$S_{x}(\Xi^{\prime})=\mathrm{L}_{x}(m_{0},m_{1},\ldots,m_{\nu})$, it is easily
checked that

$\\{\mathrm{LM}_{\prec_{\mathrm{grlex}}}(g_{i}):1\leq i\leq
s\\}=\\{x^{m_{j}+1}y^{j}:0\leq j\leq\nu\\}\cup\\{y^{\nu+1}\\},$

which implies (i) readily. In the proof of Theorem 2(For brevity, we refer the
reader to [7] for details), we find that
$(x-x_{0,0})(x-x_{1,0})\cdots(x-x_{m_{0},0}),(y-y_{0})(y-y_{1})\cdots(y-y_{\nu})\in\mathcal{G}_{\prec_{\mathrm{grlex}}}(\Xi^{\prime})$.
Since $\Xi^{\prime}$ is $x$-tower, we have $m_{0}>m_{1}>\cdots>m_{\nu}\geq 0$.
Thus, for $0\leq j\leq\nu-1$,

$\displaystyle\deg x^{m_{j}+1}y^{j}$ $\displaystyle=m_{j}+1+j$
$\displaystyle\geq m_{j+1}+1+j+1$ $\displaystyle=\deg x^{m_{j+1}+1}y^{j+1}.$

Next, we claim that $\deg x^{m_{j}+1}y^{j}\geq\deg y^{\nu+1}$, that is
$m_{j}\geq\nu-j$, $j=0,\ldots,\nu$. In fact, it is easy to see from
$m_{0}>m_{1}>\cdots>m_{\nu}\geq 0$ that $m_{j}-m_{\nu}\geq\nu-j$, hence,
$m_{j}\geq\nu-j,j=0,\ldots,\nu$. Therefore, (ii), (iii) follows.

Still from the proof of Theorem 2, we know that $g_{j}\in\langle
y-y_{0}\rangle$ and there is no monomial $x^{\alpha_{1}}y^{\alpha_{2}}$ of
$g_{j}$ except $\mathrm{LM}_{\prec_{\mathrm{grlex}}}(g_{j})$ satisfying
$\alpha_{1}\geq m_{j-1}+1$. Therefore, the definition of
$\prec_{\mathrm{lex}}$ implies (iv).

Finally, (v) is a direct consequence of Lemma 8 in [7]. ∎

######  Lemma 8.

[8] Let $\Xi$ and $\Xi^{\prime}$ be varieties in $\mathbb{F}^{d}$. Then

$\mathcal{I}(\Xi):\mathcal{I}(\Xi^{\prime})=\mathcal{I}(\Xi-\Xi^{\prime}).$

######  Lemma 9.

[8] Let $\mathcal{I}$ be an ideal and $g$ an element of $\Pi^{2}$. If
$\\{h_{1},\ldots,h_{p}\\}$ is a basis of the ideal $\mathcal{I}\cap\langle
g\rangle$, then $\\{h_{1}/g,\ldots,h_{p}/g\\}$ is a basis of
$\mathcal{I}:\langle g\rangle$.

The following theorem shows us the degree reducing interpolation bases for
bivariate Lagrange interpolation on quasi-$x$-tower sets w.r.t.
$\prec_{\mathrm{grlex}}$.

######  Theorem 10.

Let $\Xi$ be a quasi-$x$-tower set in $\mathbb{F}^{2}$. The DRIMB for Lagrange
interpolation on $\Xi$ w.r.t. $\prec_{\mathrm{grlex}}$ is

$\mathcal{N}_{\prec_{\mathrm{grlex}}}(\Xi)=\\{x^{i}y^{j}:(i,j)\in
S_{x}(\Xi)\\}.$

######  Proof 4.

Firstly, we assume that $S_{x}(\Xi)=\mathrm{L}_{x}(m_{1},\ldots,m_{\nu})$. By
Corollary 5, there exists a derived $x$-tower set from $\Xi$, say
$\Xi^{\prime}$, with base set
$B=\\{(x_{0},y_{0}),(x_{1},y_{0}),\ldots,(x_{m_{0}},y_{0})\\}$. Thus,
Proposition 3 implies that
$S_{x}(\Xi^{\prime})=\mathrm{L}_{x}(m_{0},m_{1},\ldots,m_{\nu})$. Moreover, it
follows from (v) of Lemma 7 that

$\displaystyle\mathcal{I}(B)$
$\displaystyle=\langle(x-x_{0})(x-x_{1})\cdots(x-x_{m_{0}}),y-y_{0}\rangle$
$\displaystyle=\langle(x-x_{0})(x-x_{1})\cdots(x-x_{m_{0}})\rangle+\langle
y-y_{0}\rangle.$

Since $B\cap\Xi=\emptyset$, Lemma 8 leads to
$\mathcal{I}(\Xi)=\mathcal{I}(\Xi^{\prime}-B)=\mathcal{I}(\Xi^{\prime}):\mathcal{I}(B)$.
Therefore, we have

$\displaystyle\mathcal{I}(\Xi)$
$\displaystyle=\mathcal{I}(\Xi^{\prime}):\big{(}\langle(x-x_{0})(x-x_{1})\cdots(x-x_{m_{0}})\rangle+\langle
y-y_{0}\rangle\big{)}$
$\displaystyle=\big{(}\mathcal{I}(\Xi^{\prime}):\langle(x-x_{0})(x-x_{1})\cdots(x-x_{m_{0}})\rangle\big{)}\cap\big{(}\mathcal{I}(\Xi^{\prime}):\langle
y-y_{0}\rangle\big{)}.$

To be sure, it follows from (ii) of Lemma 7 that
$\langle(x-x_{0})(x-x_{1})\cdots(x-x_{m_{0}})\rangle\subset\mathcal{I}(\Xi^{\prime})$,
hence,

$\mathcal{I}(\Xi^{\prime}):\langle(x-x_{0})(x-x_{1})\cdots(x-x_{m_{0}})\rangle=\Pi^{2},$

which means

$\mathcal{I}(\Xi)=\mathcal{I}(\Xi^{\prime}):\langle y-y_{0}\rangle.$

Recalling Lemma 7, we suppose that
$\mathcal{G}_{\prec_{\mathrm{grlex}}}(\Xi^{\prime})=\\{g_{1},g_{2},\ldots,g_{\nu+2}\\}$
with $g_{\nu+2}\prec_{\mathrm{grlex}}\cdots\prec_{\mathrm{grlex}}g_{1}$.
Hence, we have

$\displaystyle g_{1}$ $\displaystyle=(x-x_{0})(x-x_{1})\cdots(x-x_{m_{0}}),$
$\displaystyle g_{i}$ $\displaystyle\in\langle y-y_{0}\rangle,\quad
i=2,\ldots,\nu+2.$

Next, for the basis for $\mathcal{I}(\Xi)$, we should compute the basis for
$\mathcal{I}(\Xi^{\prime})\cap\langle y-y_{0}\rangle$ so that we can apply
Lemma 9. Let $t$ be a new variable. According to [8],

$\displaystyle\mathcal{I}(\Xi^{\prime})\cap\langle y-y_{0}\rangle$
$\displaystyle=\langle t\mathcal{I}(\Xi^{\prime}),(1-t)\langle
y-y_{0}\rangle\rangle\cap\Pi^{2}$ $\displaystyle=\langle
tg_{1},tg_{2},\ldots,tg_{\nu+2},(1-t)(y-y_{0})\rangle\cap\Pi^{2}.$

Since $g_{i}\in\langle y-y_{0}\rangle,i=2,\ldots,\nu+2$,
$g_{i}/(y-y_{0})\in\Pi^{2}$, hence,

$\displaystyle tg_{i}+(g_{i}/(y-y_{0}))(1-t)(y-y_{0})$ $\displaystyle=$
$\displaystyle(g_{i}/(y-y_{0}))t(y-y_{0})+(g_{i}/(y-y_{0}))(1-t)(y-y_{0})$
$\displaystyle=$ $\displaystyle(g_{i}/(y-y_{0}))(y-y_{0})$ $\displaystyle=$
$\displaystyle g_{i},$

holds for $i=2,\ldots,\nu+2$. Thus,

$\mathcal{I}(\Xi^{\prime})\cap\langle y-y_{0}\rangle=\langle
tg_{1},(1-t)(y-y_{0}),g_{2},\ldots,g_{\nu+2}\rangle\cap\Pi^{2}.$

Since
$\mathcal{G}_{\prec_{\mathrm{grlex}}}(\Xi^{\prime})=\\{g_{1},g_{2},\ldots,g_{\nu+2}\\}$,
it is easily checked from Buchberger’s S-pair criterion and (iv) of Lemma 7
that

$\\{tg_{1},(1-t)(y-y_{0}),g_{2},\ldots,g_{\nu+2}\\}$

is the reduced Gröbner basis for $\langle
t\mathcal{I}(\Xi^{\prime}),(1-t)(y-y_{0})\rangle$ w.r.t.
$\prec_{\mathrm{lex}}$ with $y\prec_{\mathrm{lex}}x\prec_{\mathrm{lex}}t$.
Consequently,

$\mathcal{I}(\Xi^{\prime})\cap\langle y-y_{0}\rangle=\langle
g_{2},\ldots,g_{\nu+2}\rangle,$

hence,

$\mathcal{I}(\Xi)=\mathcal{I}(\Xi^{\prime}):\langle y-y_{0}\rangle=\langle
g_{2}/(y-y_{0}),\ldots,g_{\nu+2}/(y-y_{0})\rangle,$

follows from Lemma 9. In fact, we can deduce that

$\displaystyle\mathcal{G}_{\prec_{\mathrm{grlex}}}(\Xi)$
$\displaystyle=\\{g_{2}/(y-y_{0}),\ldots,g_{\nu+2}/(y-y_{0})\\}$
$\displaystyle=:\\{g_{1}^{\prime},\ldots,g_{\nu+1}^{\prime}\\}.$

By Lemma 7, $\Xi^{\prime}$ is $x$-tower implies that

$\\{\mathrm{LM}_{\prec_{\mathrm{grlex}}}(g_{j}):1\leq
j\leq\nu+2\\}=\\{x^{m_{j}+1}y^{j}:0\leq j\leq\nu\\}\cup\\{y^{\nu+1}\\},$

therefore,

$\\{\mathrm{LM}_{\prec_{\mathrm{grlex}}}(g_{j}^{\prime}):1\leq
j\leq\nu+1\\}=\\{x^{m_{j}+1}y^{j-1}:1\leq j\leq\nu\\}\cup\\{y^{\nu}\\}.$

As a result, since $S_{x}(\Xi)=\mathrm{L}_{x}(m_{1},\ldots,m_{\nu})$, we have

$\mathcal{N}_{\prec_{\mathrm{grlex}}}(\Xi)=\\{x^{i}y^{j}:(i,j)\in
S_{x}(\Xi)\\}$

which finishes the proof. ∎

Theorem 10 has solved the DRIMB problems w.r.t. $\prec_{\mathrm{grlex}}$.
Next, let us turn to DRINB problems.

######  Theorem 11.

Let $\Xi\subset\mathbb{F}^{2}$ be a quasi-$x$-tower set of points

$u_{mn}^{x}=(x_{mn},y_{n}),\quad(m,n)\in S_{x}(\Xi),$

which give rise to polynomials

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

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

$Q_{x}=\\{\phi_{ij}^{x}:(i,j)\in S_{x}(\Xi)\\}$

is a _DRINB_ w.r.t. $\prec_{\mathrm{grlex}}$ for (1) satisfying

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

######  Proof 5.

Fix $(i,j)\in S_{x}(\Xi)$. When $(i,j)=(m,n)$, since $x_{0j}\neq
x_{1j}\neq\cdots\neq x_{ij}$ and $y_{0}\neq y_{1}\neq\cdots\neq y_{j}$,

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

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

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

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

$\displaystyle\phi_{ij}^{x}(u_{mn}^{x})$
$\displaystyle=\varphi_{ij}^{x}\prod_{t=0}^{j-1}(y_{n}-y_{t})(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_{n}-y_{t})(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{invlex}}(m,n),$

namely $Q_{x}$ is a Newton basis for $\mathrm{Span}_{\mathbb{F}}Q_{x}$. By
Theorem 10, it is easy to see that
$\mathrm{Span}_{\mathbb{F}}Q_{x}=\mathrm{Span}_{\mathbb{F}}{\mathcal{N}_{\prec_{\mathrm{grlex}}}(\Xi)}$.
Therefore, $Q_{x}$ is a DRINB w.r.t. $\prec_{\mathrm{grlex}}$ for (1). ∎

Similarly, we can prove the following theorems:

######  Theorem 12.

Let $\Xi$ be a quasi-$y$-tower set in $\mathbb{F}^{2}$. The DRIMB for Lagrange
interpolation on $\Xi$ w.r.t. $\prec_{\mathrm{grevlex}}$ is

$\mathcal{N}_{\prec_{\mathrm{grevlex}}}(\Xi)=\\{x^{i}y^{j}:(i,j)\in
S_{y}(\Xi)\\}.$

######  Theorem 13.

Let $\Xi\subset\mathbb{F}^{2}$ be a quasi-$y$-tower set of points

$u_{mn}^{y}=(x_{m},y_{mn}),(m,n)\in S_{y}(\Xi).$

We define the polynomials

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

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

$Q_{y}=\\{\phi_{ij}^{x}:(i,j)\in S_{y}(\Xi)\\}$ (2)

is a _DRINB_ w.r.t. $\prec_{\mathrm{grevlex}}$ for (1) satisfying

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

So far, we have discovered the degree reducing interpolation bases for
Lagrange interpolation on quasi-tower sets w.r.t. $\prec_{\mathrm{grlex}}$ and
$\prec_{\mathrm{grevlex}}$. Next, we should turn to $\prec_{\mathrm{lex}}$ and
$\prec_{\mathrm{invlex}}$ cases.

######  Lemma 14.

[9] Let

$\displaystyle\Xi$
$\displaystyle=\\{u_{mn}^{x}=(x_{mn}^{x},y_{mn}^{x}):(m,n)\in S_{x}(\Xi)\\}$
$\displaystyle=\\{u_{mn}^{y}=(x_{mn}^{y},y_{mn}^{y}):(m,n)\in S_{y}(\Xi)\\}$

be a set of distinct points in $\mathbb{F}^{2}$. Then

(i) the set $\\{x^{i}y^{j}:(i,j)\in S_{x}(\Xi)\\}$ is the _DRIMB_ as well as
$\\{\phi_{ij}^{x}:(i,j)\in S_{x}(\Xi)\\}$ is a _DRINB_ w.r.t.
$\prec_{\mathrm{lex}}$ for (1), where

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

with
$\varphi_{ij}^{x}=1/\prod_{t=0}^{j-1}(y_{0j}^{x}-y_{0t}^{x})\prod_{s=0}^{i-1}(x_{ij}^{x}-x_{sj}^{x})\in\mathbb{F}$
and the empty products taken as 1;

(ii) the set $\\{x^{i}y^{j}:(i,j)\in S_{y}(\Xi)\\}$ is the _DRIMB_ as well as
$\\{\phi_{ij}^{y}:(i,j)\in S_{y}(\Xi)\\}$ is a _DRINB_ w.r.t.
$\prec_{\mathrm{invlex}}$ for (1), where

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

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

Finally, Theorem 10-13 and Lemma 14 together give rise to our main theorem.

######  Theorem 15.

Let

$\Xi^{x}=\\{u_{ij}^{x}=(x_{ij}^{x},y_{j}^{x}):(i,j)\in S_{x}(\Xi^{x})\\}$

be a quasi-$x$-tower set in $\mathbb{F}^{2}$. Then the set
$\\{x^{i}y^{j}:(i,j)\in S_{x}(\Xi^{x})\\}$ is the _DRIMB_ as well as
$\\{\phi_{ij}^{x}:(i,j)\in S_{x}(\Xi^{x})\\}$ is a _DRINB_ w.r.t.
$\prec_{\mathrm{lex}}$ or $\prec_{\mathrm{grlex}}$ for (1), where

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

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

If

$\Xi^{y}=\\{u_{ij}^{y}=(x_{i}^{y},y_{ij}^{y}):(i,j)\in
S_{y}(\Xi^{y})\\}\subset\mathbb{F}^{2}$

is a quasi-$y$-tower set. Then the set $\\{x^{i}y^{j}:(i,j)\in
S_{y}(\Xi^{y})\\}$ is the _DRIMB_ as well as $\\{\phi_{ij}^{y}:(i,j)\in
S_{y}(\Xi^{y})\\}$ is a _DRINB_ w.r.t. $\prec_{\mathrm{invlex}}$ or
$\prec_{\mathrm{grevlex}}$ for (1), where

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

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

######  Example 2.

Let us continue with Example 1. Observeing Figure 1, we have

$S_{x}(\Xi)=\mathrm{L}_{x}(6,4,3,2,1).$

Therefore, according to Theorem 15,

$\displaystyle\mathcal{N}_{\prec_{\mathrm{grlex}}}(\Xi)=\mathcal{N}_{\prec_{\mathrm{lex}}}(\Xi)=$
$\displaystyle\\{x^{i}y^{j}:(i,j)\in S_{x}(\Xi)\\}$ (3) $\displaystyle=$
$\displaystyle\\{1,x,x^{2},x^{3},x^{4},x^{5},x^{6},y,xy,x^{2}y,x^{3}y,x^{4}y,$
$\displaystyle\phantom{\\{}y^{2},xy^{2},x^{2}y^{2},x^{3}y^{2},y^{4},xy^{4},x^{2}y^{4},y^{5},xy^{5}\\}$

and a DRINB for interpolation on $\Xi$ w.r.t. $\prec_{\mathrm{lex}}$ or
$\prec_{\mathrm{grlex}}$ is

$\displaystyle\Bigg{\\{}1,5(x-0.2),\frac{25}{6}(x-0.2)(x-0.4),\ldots,$ (4)
$\displaystyle\phantom{\\{}5(y-0.4),\frac{25}{3}x(y-0.4),\ldots,$
$\displaystyle\phantom{\\{}\frac{20}{7}(y-0.4)(y-0.6),\ldots\Bigg{\\}}.$

##  5 Algorithms and Timings

At the beginning of this section is a restatement of 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 monomial
ordering $\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{LM}_{\prec}(G):=\\{\mathrm{LM}_{\prec}(g):g\in
G\\}$. Continue with BM2.

Like TBM algorithm in [7], we have the following QTBM algorithm for quasi-
tower sets.

######  Algorithm 2.

(QTBM algorithm)

Input: A quasi-$x$-tower(quasi-$y$-tower) set $\Xi\subset\mathbb{F}^{2}$ of
$\mu$ points and a fixed monomial ordering
$\prec_{\mathrm{grlex}}$($\prec_{\mathrm{grevlex}}$) or
$\prec_{\mathrm{lex}}$($\prec_{\mathrm{invlex}}$).

Output: The 3-tuple $(G,N,Q)$, where $G$ is the reduced Gröbner basis for
$\mathcal{I}(\Xi)$, $N$ is the Gröbner éscalier of $\mathcal{I}(\Xi)$, and $Q$
is a DRINB for (1).
QTBM1. Construct lower set $S_{x}(\Xi)$($S_{y}(\Xi)$).
QTBM2. Compute the sets $N$ and $Q$ according to Theorem 15.
QTBM3. Compute the set $L:=\\{x\cdot t:t\in N\\}\bigcup\\{y\cdot t:t\in
N\\}\setminus N$.
QTBM4. Construct $\mu\times\mu$ matrix $C$ whose $(h,k)$ entry is
$\phi_{h}^{x}(u_{k}^{x})$($\phi_{h}^{y}(u_{k}^{y})$) where
$\phi_{h}^{x}$($\phi_{h}^{y}$), $u_{k}^{x}$($u_{k}^{y}$) are $h$th and $k$th
elements of $Q=\\{\phi_{ij}^{x}(\phi_{ij}^{y}):(i,j)\in
S_{x}(\Xi)(S_{y}(\Xi))\\}$ and $\Xi=\\{u_{mn}^{x}(u_{mn}^{y}):(m,n)\in
S_{x}(\Xi)(S_{y}(\Xi))\\}$ w.r.t. the increasing
$\prec_{\mathrm{invlex}}$($\prec_{\mathrm{lex}}$) on $(i,j)$ and $(m,n)$
respectively.
QTBM5. Goto BM2 with $N,Q,L,C$ for the reduced Gröbner basis $G$.

######  Example 3.

We continue with Example 1 and 2. Example 2 had obtained $N$ and $Q$ in (3)
and (4) respectively. According to QTBM3 and QTBM4, we get

$L=\\{x^{7},x^{5}y,x^{6}y,x^{4}y^{2},x^{3}y^{3},x^{2}y^{4},y^{5},xy^{5}\\}$

and

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

Finally, QTBM5 yields

$\displaystyle G=\\{(y-0.4)(y-0.6)(y-1.1)(y-1.45)(y-1.8),\ldots\\}.$

At the end, we will show the timings for the computations of BM-problems on
quasi-tower sets in finite prime fields $\mathbb{F}_{q}$ with size $q$ w.r.t.
monomial orderings $\prec_{\mathrm{grlex}}$ and $\prec_{\mathrm{invlex}}$
respectively. QTBM and BM algorithms were implemented on Maple 12 installed on
a laptop with 768 Mb RAM and 1.5 GHz CPU.

For field $\mathbb{F}_{37}$ and $\prec_{\mathrm{grlex}}$,

Algorithms $\\#\Xi$ | 300 | 500 | 800 | 1200
---|---|---|---|---
QTBM | 2.563 s | 8.773 s | 26.068 s | 63.772 s
BM | 20.690 s | 80.375 s | 288.364 s | 901.246 s

For field $\mathbb{F}_{43}$ and $\prec_{\mathrm{invlex}}$,

Algorithms $\\#\Xi$ | 500 | 800 | 1000 | 1200
---|---|---|---|---
QTBM | 8.171 s | 25.607 s | 48.170 s | 70.802 s
BM | 114.996 s | 375.610 s | 881.988 s | 1347.287

## References

  * [1] 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.
  * [2] T. Mora, Gröbner technology, in: M. Sala, T. Mora, L. Perret, S. Sakata, C. Traverso (Eds.), Gröbner Bases, Coding, and Cryptography, Springer, Berlin, 2009, pp. 11–25.
  * [3] 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.
  * [4] S. Lundqvist, Complexity of comparing monomials and two improvements of the Buchberger-Möller algorithm, in: Mathematical Methods in Computer Science, 2008, pp. 105–125.
  * [5] T. Sauer, Lagrange interpolation on subgrids of tensor product grids, Math. Comp. 73 (245) (2004) 181–190.
  * [6] T. Chen, T. Dong, S. Zhang, The Newton interpolation bases on lower sets, J. Inf. Comput. Sci. 3 (3) (2006) 385–394.
  * [7] T. Dong, T. Chen, S. Zhang, X. Wang, Bivariate Lagrange interpolation on tower interpolation sites, submitted. Preprint available online at: http://arxiv.org/abs/1001.1196.
  * [8] D. Cox, J. Little, D. O’Shea, Ideal, Varieties, and Algorithms, 3rd Edition, Undergraduate Texts in Mathematics, Springer, New York, 2007.
  * [9] X. Wang, S. Zhang, T. Dong, A bivariate preprocessing paradigm for Buchberger-Möller algorithm, submitted. Preprint available online at: http://arxiv.org/abs/1001.1186.