Algorithms for computing Gröbner bases of ideal interpolation

1.   Introduction

Let $\mathbb{F}$ be either the real field $\mathbb{R}$ or the complex field $\mathbb{C}$. Polynomial interpolation is to construct a polynomial $g$ belonging to a finite-dimensional subspace of $\mathbb{F}[{\bf X}]$ that agrees with a given function $f$ at the data set, where $\mathbb{F}[{\bf X}] : = \mathbb{F}[x_1, x_2, \dots, x_d]$ denotes the polynomial ring in $d$ variables over $\mathbb{F}$.

Based on the perfection of the theories of ideals, varieties and Gröbner bases, the so-called ideal interpolation research has developed rapidly in recent years. Ideal interpolation is defined by a linear projector whose kernel is a polynomial ideal. Such a projector is called an ideal projector. Lagrange projectors and Hermite projectors are two important classes of ideal projectors, which have been studied by many researchers [3,5,9,15]. In ideal interpolation, the interpolation condition functionals at an interpolation point $\boldsymbol{\theta} \in \mathbb{F}^d$ can be described by a linear space ${\rm span}\{\delta_{\boldsymbol{\theta}} \circ P(D), P \in P_{\boldsymbol{\theta}}\}$, where $P_{\boldsymbol{\theta}}$ is a $D$-invariant (i.e., closed under differentiation) polynomial subspace, $\delta_{\boldsymbol{\theta}}$ is the evaluation functional at $\boldsymbol{\theta}$, and $P(D)$ is the differential operator induced by polynomial $P$ [3]. The classical examples of ideal interpolation are Lagrange interpolation and univariate Hermite interpolation.

For an ideal interpolation problem, suppose that $\Delta$ is the finite set of interpolation condition functionals. Then, the set of all polynomials that vanish at $\Delta$ constitutes a 0-dimensional ideal, which is denoted by $I(\Delta)$, namely,

We refer the readers to [3,15] for more details about ideal interpolation.

The theory of Gröbner bases has been applied successfully in various fields such as symbolic computation and numerical calculation, including polynomial system solving and polynomial interpolation. In previous decades, researchers have done a lot of work on computing Gröbner bases of vanishing ideals. For any point set $\Theta \subset \mathbb{F}^d$ and any fixed monomial order, the BM algorithm yields the reduced Gröbner basis and a reducing interpolation Newton basis for a $d$-variate Lagrange interpolation on $\Theta$ [11]. The BM algorithm computes the vanishing ideal of a finite set of points in affine space without multiplicities. [1] presents a variant of the BM algorithm that is more effective for computation over $\mathbb{Q}$. Marinari, Möller, and Mora construct a linear system based on a Vandermonde-like matrix, and give an algorithm (the MMM algorithm) to compute general zero-dimensional ideals by Gaussian elimination [10]. The MMM algorithm is one of the most famous algorithms, and it has a polynomial time complexity.

As a generalization of univariate Newton interpolation, Farr and Gao give an algorithm that computes the reduced Gröbner basis for vanishing ideals under any monomial order [6]. Farr and Gao's method can also be applied to compute the vanishing ideal when the interpolation points have multiplicities, but the multiplicity set needs to be a delta set in $\mathbb{N}^d$. To avoid solving linear equations, Lederer gives an algorithm to compute the Gröbner basis of an arbitrary finite set of points under lexicographic order by induction over the dimension $d$ [8]. Jiang, Zhang, and Shang give an algorithm for computing the Gröbner basis of a single-point ideal interpolation [7]. For other literature on the computation of the Gröbner basis, see [13,14].

In this paper, algorithms are proposed to compute the reduced Gröbner basis for the vanishing ideal of a general ideal interpolation problem. We consider the general case that the multiplicity space of each point just needs to be closed under differentiation. The major idea is based on a formal power series that appeared in [4]. We focus on extracting the reduced Gröbner basis from interpolation condition functionals. First, we give the definition of "reverse" reduced team, with which the monomial interpolation basis can be obtained directly; next, we translate interpolation condition functionals into formal power series via Taylor expansion, which helps convert the general interpolation problem to a single point interpolation problem; finally, the reduced Gröbner basis is read from formal power series by Gaussian elimination.

The paper is organized as follows: Section 2 gives some necessary preliminaries and introduces the definition of "reverse" reduced team. An algorithm is proposed for computing the "reverse" reduced team in Section 3. Section 4 discusses the method to find the quotient ring basis. The algorithms for computing the reduced Gröbner basis (Algorithm $2$ for Lagrange interpolation and Algorithm $3$ for the general case) are presented in Section 5. A special example is discussed in the last section.

2.   Preliminary

Throughout the paper, $\mathbb{N}$ denotes the set of nonnegative integers. Let $\mathbb{N}^d : = \{ (\alpha_1, \alpha_2, \dots, \alpha_d) : \alpha_i \in \mathbb{N}\}$. For $\boldsymbol{\alpha} = (\alpha_1, \alpha_2, \dots, \alpha_d) \in \mathbb{N}^d$, define $\boldsymbol{\alpha}!: = \alpha_1!\alpha_2!\cdots\alpha_d!$ and denote by ${\bf X}^{\boldsymbol{\alpha}}$ the monomial $x_1^{\alpha_1} x_2^{\alpha_2} \cdots x_d^{\alpha_d}$. Let $\{{\bf X}^{\boldsymbol{\alpha_1}}, {\bf X}^{\boldsymbol{\alpha_2}}, \dots, {\bf X}^{\boldsymbol{\alpha_n}}\}$ be a finite set of monomials, and $\{L_i: \mathbb{F}[{\bf X}] \to \mathbb{F}, i = 1, 2, \dots, n\}$ be a finite set of linearly independent functionals. We can treat the matrix

as a Vandermonde-like matrix.

A polynomial $P \in \mathbb{F}[{\bf X}]$ can be considered the formal power series

where $\hat{P}(\boldsymbol{\alpha})$ are the coefficients in the polynomial $P$.

$P(D): = P(D_{x_1}, D_{x_2}, \dots, D_{x_d})$ is the differential operator induced by the polynomial $P$, where $D_{x_j}: = \frac{\partial}{\partial x_j}$ is the differentiation with respect to the $j$th variable, $j = 1, 2, \dots, d$.

Define $D^{\boldsymbol{\alpha}}: = D_{x_1}^{\alpha_1}D_{x_2}^{\alpha_2}\cdots D_{x_d}^{\alpha_d}$. The differential polynomial can be rewritten as

Given a monomial order $\prec$, the least monomial of the polynomial $P$ w.r.t. $\prec$ is defined by

Definition 1. We denote by $\Lambda\{P_1, P_2, \dots, P_n\}$ the set of all monomials that occur in the polynomials $P_1, P_2, \dots, P_n$ with nonzero coefficients.

For example, let $P_1 = 1, P_2 = x,$ and $P_3 = \frac{1}{2}x^2 +y$. Then,

Definition 2. Given a monomial order $\prec$, a set of linearly independent polynomials $\{P_1, P_2, \dots, P_n\} \subset \mathbb{F}[{\bf X}]$ is called a "reverse" reduced team w.r.t. $\prec$, if

1) the coefficient of the least monomial of the polynomial $P_i, \; 1 \le i \le n$ is 1;

2) ${\rm lm}(P_i) \not\in \Lambda \{P_j\}, \; i\neq j, \; 1 \le i, \; j \le n$.

For example, given the monomial order $\mathrm{grlex}(z \prec y \prec x)$,

are "reverse" reduced teams w.r.t. $\prec$.

3.   Computing a "reverse" reduced team by Gaussian elimination

Let $T$ and $\bar{T}$ be two sets of monomials in $\mathbb{F}[{\bf X}]$. The notation $\bar{T}-T$ is reserved for the set $\{t : t\in \bar{T}, t\notin T\}$. Given a monomial order $\prec$, $P_1, P_2, \dots, P_n \in \mathbb{F}[{\bf X}]$ are linearly independent polynomials. Algorithm 1 yields a "reverse" reduced team w.r.t. $\prec$.

Example 3. Given the monomial order $\mathrm{grlex}(y \prec x)$, $P_1 = 1$, $P_2 = x$, $P_3 = \dfrac{1}{2}x^2+y$, $P_4 = \dfrac{1}{6}x^3+xy+2y$. Using Algorithm 1, we get $({\rm{List}}, \prec) = (1, y, x, xy, x^2, x^3),$

Thus, the "reverse" reduced team is ${P_1}^* = 1$, ${P_2}^* = \dfrac{1}{2}x^2+y$, ${P_3}^* = x$, ${P_4}^* = \dfrac{1}{6}x^3-x^2+xy$.

4.   Interpolation monomial basis and quotient ring basis

Given interpolation conditions $\Delta = {\rm span}\{L_1, L_2, \dots, L_n\}$, where $L_1, L_2, \dots, L_n$ are linearly independent functionals. Let $T = \{{\bf X}^{\boldsymbol{\alpha_1}}, {\bf X}^{\boldsymbol{\alpha_2}}, \dots, {\bf X}^{\boldsymbol{\alpha_n}}\}$ be a set of monomials, then $T$ is an interpolation monomial basis for $\Delta$ if the Vandermonde-like matrix (applying the data map $\{L_i: i = 1, 2, \dots, n\}$ to the column map $\{{\bf X}^{\boldsymbol{\alpha_j}}: j = 1, 2, \dots, n\}$) is non-singular.

Definition 4. Let $T$ and $\bar{T}$ be two sets of monomials in $\mathbb{F}[{\bf X}]$ with $\bar{T}-T\neq \emptyset$ and $T-\bar{T}\neq \emptyset$. Given a monomial order $\prec$, we write $\bar{T}\prec T$, if

Definition 5 ($\prec$-minimal monomial basis [12]). Given a monomial order $\prec$ and interpolation conditions $\Delta = {\rm span}\{L_1, L_2, \dots, L_n\}$, where $L_1, L_2, \dots, L_n$ are linearly independent functionals. Let $T$ be an interpolation monomial basis for $\Delta$, then $T$ is $\prec$-minimal if there exists no interpolation monomial basis $\bar{T}$ for $\Delta$ satisfying $\bar{T} \prec T$.

First, we consider the interpolation problem at the origin.

Lemma 6. Given interpolation conditions $\Delta = \delta_{\bf 0} \circ {\rm span}\{P_1(D), P_2(D), \dots, P_n(D)\}$, where $P_1,$ $P_2, \dots, P_n \in \mathbb{F}[{\bf X}]$ are linearly independent polynomials. Let $T = \{{\bf X}^{\boldsymbol{\beta_1}}, {\bf X}^{\boldsymbol{\beta_2}}, \dots, {\bf X}^{\boldsymbol{\beta_n}}\}$ be an interpolation monomial basis for $\Delta$, then for each $P_i, 1 \le i \le n$, there exists an ${\bf X}^{\boldsymbol{\alpha_i}} \in \Lambda\{P_i\}$ satisfying ${\bf X}^{\boldsymbol{\alpha_i}} \in T$.

Proof. We will prove this by contradiction. Without loss of generality, we can assume that for every ${\bf X}^{\boldsymbol{\alpha}} \in \Lambda\{P_1\}$, ${\bf X}^{\boldsymbol{\alpha}} \not\in T$. It is observed that

Therefore, the Vandermonde-like matrix has a zero row, and it is singular. It contradicts the condition that $T = \{{\bf X}^{\boldsymbol{\beta_1}}, {\bf X}^{\boldsymbol{\beta_2}}, \dots, {\bf X}^{\boldsymbol{\beta_n}}\}$ is an interpolation monomial basis for $\Delta$. □

Given interpolation conditions $\Delta = \delta_{\bf 0} \circ {\rm span}\{P_1(D), P_2(D), \dots, P_n(D)\}$, Lemma 6 shows that we need to choose at least one monomial from each $P_i, 1 \le i \le n$ to construct the interpolation monomial basis for $\Delta$.

For $\boldsymbol{\theta} = (\theta_1, \theta_2, \dots, \theta_d) \in \mathbb{F}^d$, we denote $\boldsymbol{\theta} {\bf X} : = \sum_{i = 1}^d \theta_i x_i$. By Taylor expansion,

this indicates that

Furthermore, we get

This means that an interpolation problem at a nonzero point can be converted into one at the origin.

Theorem 7. For any $\boldsymbol{\theta} \in \mathbb{F}^d$, given a monomial order $\prec$ and interpolation conditions $\Delta = \delta_{\boldsymbol{\theta}} \circ {\rm span}\{P_1(D), P_2(D), \dots, P_n(D)\}$. If $\{P_1, P_2, \dots, P_n\}$ is a "reverse" reduced team w.r.t. $\prec$, then $\{{\rm lm}(P_1), {\rm lm}(P_2), \dots, {\rm lm}(P_n)\}$ is the $\prec$-minimal monomial basis for $\Delta$.

Proof. Let ${\tilde {P}_i}(D) = {e^{\boldsymbol{\theta} D}} P_i(D), 1 \le i \le n$. By (4.2), we have

According to Lemma 6, we choose at least one monomial from each $\tilde {P}_i, 1 \le i \le n$ to construct the interpolation monomial basis. On the other hand, $P_i, 1 \le i \le n$ are assumed to be linearly independent, which implies that the cardinal number of the interpolation monomial basis is $n$. Thus, it is easy to see that $\{{\rm lm}(\tilde {P}_1), {\rm lm}(\tilde {P}_2), \dots, {\rm lm}(\tilde {P}_n)\}$ is the minimal choice w.r.t. $\prec$. We only need to prove $\{{\rm lm}(\tilde {P}_1), {\rm lm}(\tilde {P}_2), \dots, {\rm lm}(\tilde {P}_n)\}$ is an interpolation monomial basis for $\Delta$.

Let $P_i = \sum \hat{P_i}(\boldsymbol{\alpha}) {\bf X}^{\boldsymbol{\alpha}} + {\bf X}^{\boldsymbol{\beta_i}}$, ${\rm lm}(P_i) = {\bf X}^{\boldsymbol{\beta_i}}, 1 \le i \le n$. Since $\{P_1, P_2, \dots, P_n\}$ is a "reverse" reduced team w.r.t. $\prec$, it means

Without loss of generality, we can assume that ${\rm lm}(P_1)\prec {\rm lm}(P_2)\prec \dots \prec{\rm lm}(P_n)$, then we have

Notice that ${\rm lm}(\tilde {P}_i) = {\rm lm}(e^{\boldsymbol{\theta} {\bf X}} \cdot P_i) = {\rm lm}(e^{\boldsymbol{\theta} {\bf X}}) \cdot {\rm lm}(P_i) = {\rm lm}(P_i), 1 \le i \le n$, we have

Thus, we have

So, the Vandermonde-like matrix is an upper triangular matrix with nonzero diagonal elements, i.e., it is non-singular. It follows that

is the $\prec$-minimal monomial basis for $\Delta$. □

In ideal interpolation, the $\prec$-minimal monomial basis is equivalent to the monomial basis of the quotient ring w.r.t. $\prec$ [12]. The following theorem can be obtained directly by Theorem 7, and we list it here without proof.

Theorem 8. For any $\boldsymbol{\theta} \in \mathbb{F}^d$, given a monomial order $\prec$ and interpolation conditions $\Delta = \delta_{\boldsymbol{\theta}} \circ {\rm span}\{P_1(D), P_2(D), \dots, P_n(D)\}$. If $\{P_1, P_2, \dots, P_n\}$ is a "reverse" reduced team w.r.t. $\prec$, then $\{{\rm lm}(P_1), {\rm lm}(P_2), \dots, {\rm lm}(P_n)\}$ is the monomial basis of the quotient ring $\mathbb{F}[{\bf X}]/ I(\Delta)$ w.r.t. $\prec$.

The following example shows the application of Theorem 8.

Example 9. Given the ideal interpolation conditions

Using $\mathrm{grlex}(y \prec x)$, we know $P_1 = 1$, $P_2 = x$, $P_3 = \frac{1}{2}x^2+y$, and $P_4 = \frac{1}{6}x^3+xy+2y$. By Algorithm 1, or Example 3, we have

By Theorem 8, $\{{\rm lm}(P_1^*), {\rm lm}(P_2^*), {\rm lm}(P_3^*), {\rm lm}(P_4^*)\} = \{1, y, x, xy\}$ is the monomial basis of the quotient ring $\mathbb{F}[{\bf X}]/ I(\Delta)$.

5.   The algorithms to compute the reduced Gröbner bases

In order to describe algorithms more conveniently, we introduce some notations. Let $\mathbb{F}[[{\bf X}]]$ be the ring of formal power series. Let $T$ be a set of monomials in $\mathbb{F}[{\bf X}]$. For any $f \in \mathbb{F}[[{\bf X}]]$, we denote by

a "truncated polynomial".

Given a monomial order $\prec$ and Lagrange interpolation conditions $\Delta$, Algorithm 2 yields the reduced Gröbner basis for $I(\Delta)$ w.r.t. $\prec$.

In Line 11 and Line 14, we use the same skill (recording the reversible matrix used for each calculation) as the MMM algorithm to calculate the rank of the matrix by Gaussian elimination. It is obvious that Algorithm 2 terminates. The following theorem shows its correctness.

Theorem 10. The output $\{G_1, G_2, \dots, G_m\}$ in Algorithm 2 is the reduced Gröbner basis for $I(\Delta)$.

Proof. By (4.1),

Suppose that $\{(e^{\boldsymbol{\theta_1} {\bf X}})^{*}, (e^{\boldsymbol{\theta_2} {\bf X}})^{*}, \dots, (e^{\boldsymbol{\theta_n} {\bf X}})^{*}\}$ is a "reverse" reduced team of $e^{\boldsymbol{\theta_1} {\bf X}}, e^{\boldsymbol{\theta_2} {\bf X}}, \dots, e^{\boldsymbol{\theta_n} {\bf X}}$. Comparing Line 13 in Algorithm 2 and Line 11 in Algorithm 1, we have

By Theorem 8, $Q$ is the monomial basis of the quotient ring $\mathbb{F}[{\bf X}]/ I(\Delta)$. On the other hand, since $Q$ is a lower set [2], it is easy to check that $G$ is the set of the leading monomials of the reduced Gröbner basis. Thus, we only need to prove that $G_i = {\bf X}^{\boldsymbol{\alpha_i}}-\sum_{j = 1}^n\left(\frac{(\boldsymbol{\alpha_i})!}{(\boldsymbol{\beta_j})!}\hat{P}_j^{*}(\boldsymbol{\alpha_i})\right) {\bf X}^{\boldsymbol{\beta_j}}$ in Line 30 lies in $I(\Delta)$. Due to $\{P_1^{*}, P_2^{*}, \dots, P_n^{*}\}$ in Line 28 is a "reverse" reduced team, it follows that ${\rm lm}(P_j^{*}) = {\bf X}^{\boldsymbol{\beta_j}} \not\in \Lambda\{P_k^{*}\}, j\neq k, 1 \le j, k \le n$. Hence, we have

Since $\{P_{k}, 1 \le k \le n \}$ can be expressed linearly by $\{P_{k}^{*}, 1 \le k \le n \}$, it follows that

i.e.,

Notice that $(\Lambda\{e^{\boldsymbol{\theta_k} {\bf X}}\}-(G\cup Q)) \cap \Lambda\{G_i\} = \emptyset$; it is easy to see that

By (4.1), we have

So, $G_i, 1\leq i\leq m$ vanishes at $\boldsymbol{\theta_k}, 1\leq k \leq n$. It follows that $G_i, 1\leq i\leq m$ lies in $I(\Delta)$. This completes the proof. □

Line 30 in Algorithm 2 shows that the "reverse" reduced team provides all the information needed to construct the reduced Gröbner basis. Since we use the same skill as the MMM algorithm, Algorithm 2 also has a polynomial time complexity.

Example 11. (Lagrange interpolation) Given the monomial order $\mathrm{grlex}(y \prec x)$, consider the bivariate Lagrange interpolation with the interpolation conditions

By Algorithm 2, we get

and

A "reverse" reduced team of $\{P_1, P_2, P_3\}$ can be computed, i.e.,

Finally, the reduced Gröbner basis for $I(\Delta)$

is read from the "reverse" reduced team $\{P_{1}^{*}, P_{2}^{*}, P_{3}^{*}\}$ by Line 30 in Algorithm 2.

For general ideal interpolation, we can convert it to single-point ideal interpolation. For example, given ideal interpolation conditions

with distinct points $\boldsymbol{\theta_i} \in \mathbb{F}^d, i = 1, 2, \dots, k$ and $s_1+s_2+\dots +s_k = n.$ By (4.2), we have

where $P_1 = e^{\boldsymbol{\theta_1} {\bf X}}P_{11}$, $P_2 = e^{\boldsymbol{\theta_1} {\bf X}}P_{12}, \dots$, $P_{s_1} = e^{\boldsymbol{\theta_1} {\bf X}}P_{1s_1}$, $P_{s_1+1} = e^{\boldsymbol{\theta_2} {\bf X}}P_{21}, \dots$, $P_n = e^{\boldsymbol{\theta_k} {\bf X}}P_{ks_k}.$

The main cost of Algorithm 2 is calculating the rank of the matrix to obtain the monomial basis of the quotient ring. In the case of single-point ideal interpolation, if the polynomials in interpolation conditions constitute a "reverse" reduced team, then we can obtain the monomial basis of the quotient ring without calculation by Theorem 7. Therefore, we get a faster algorithm for computing the reduced Gröbner basis. We have the following algorithm (Algorithm 3) for single-point ideal interpolation.

6.   A special example for ideal interpolation

For general ideal interpolation, first we convert it to single-point ideal interpolation by (4.2) and get the "reverse" reduced team by Algorithm 1, then we compute the reduced Gröbner basis by Algorithm 3. The amount of calculation is almost the same as the MMM algorithm. However, in some special cases, we can first compute the Gröbner basis of a single point ideal interpolation by Algorithm 3, which needs little calculation, and then the original Gröbner basis is constructed. The scale of the problem decreases in this case, thus the computational efficiency has improved. A relevant example is given below.

Example 12. (ideal interpolation) Given the monomial order $\mathrm{lex}\; (y \prec x)$ and ideal interpolation conditions

We split the original problem into two subproblems, $\Delta_A$ and $\Delta_B$.

Since $\{1, x, \dfrac{1}{2}x^2+y\}$ is a "reverse" reduced team, $Q_A: = \{1, x, y\}$ is the monomial basis of the quotient ring $\mathbb{F}[{\bf X}]/ I(\Delta_A),$ $G_A: = \{y^2, xy, x^2\}$ is the set of the leading monomials of the reduced Gröbner basis for $I(\Delta_A)$. By Line 21 in Algorithm 3, we get

$\{G_{A1}, G_{A2}, G_{A3}\} = \{ y^2, xy, x^2-y\}$ is the reduced Gröbner basis for $I(\Delta_A)$.

With the same procedure, we can get

$\{G_{B1}, G_{B2}\} = \{ y-2, x^2-2x+1\}$ is the reduced Gröbner basis for $I(\Delta_B)$.

Notice that the polynomials $G_{A1} = y^2$ and $G_{B1} = y-2$ are coprime; there exist polynomials $u = \dfrac{1}{4},$ $v = -\dfrac{1}{4}(y+2)$ such that

Let

Since $G_1, G_2, {\tilde G}_3$ all lie in $I(\Delta_A \cup \Delta_B) = I(\Delta)$, the linear combination ${\tilde G}_3-cG_1-eG_2$ lies in $I(\Delta)$, where $c = \dfrac{1}{4}$ is the coefficient of $y^3$ in ${\tilde G}_3$ and $e = -\dfrac{1}{2}$ is the coefficient of $xy^2$ in ${\tilde G}_3$. Let

Notice that the leading term of $G_i$ in particular divides none of the nonleading terms of $G_j$, for $i, j \in \{1, 2, 3\}$, whereas the dimension of $\mathbb{F}[{\bf X}]/\langle G_1, G_2, G_3\rangle$ is 5. Therefore, $\{G_1, G_2, G_3\}$ is the reduced Gröbner basis for $I(\Delta)$.

Author contributions

Xue Jiang: conceptualization, investigation, writing-original draft, writing-review and editing; Yihe Gong: conceptualization, validation, writing-original draft, writing-review and editing. All authors have read and approved the final version of the manuscript for publication.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors would like to thank the anonymous referees and the editor. This work was supported by the Fundamental Scientific Research of the Educational Department of Liaoning Province (No. LJKQZ20222461), China.

Conflict of interest

The authors declare no conflicts of interest.