The Representation of D-Invariant Polynomial Subspaces Based on Symmetric Cartesian Tensors

Multivariate polynomial interpolation is widely used in many application domains, such as image processing, electronic communication, control theory, etc. The theory of multivariate polynomial interpolation is far from perfect since the interpolation conditions are too complicated, and the multiplicity structure of each interpolation site has many different expressions. Note that most related practical problems can be converted to ideal interpolation problems, whose interpolation conditions is determined by a $D-$invariant polynomial subspace. Throughout the paper, $\mathbb{F}\left[X\right]:=\mathbb{F}[x_1,\cdots ,x_d]$ denotes the polynomial ring in d variables over $\mathbb{F}$. For simplicity, we will work with the ground field $\mathbb{F}=\mathbb{R}$ or $\mathbb{C}$. Ideal interpolation, a special class of polynomial interpolation problems, can be defined by a linear projector (idempotent operator) of finite rank on $\mathbb{F}\left[X\right]$. The kernel of the projector forms a polynomial ideal. Carl de Boor has conducted a great deal of important work for ideal interpolation [1].

The interpolation conditions of an ideal interpolant correspond to a D-invariant subspace [1,2]. Lagrange interpolation is a standard example of which the interpolation conditions consist of only evaluation functionals. In the one variable case, every ideal projector is the pointwise limit of Lagrange projectors when $\mathbb{F}=\mathbb{C}$. However, this is not true in the multivariate case [3,4]. Thus, it is natural to ask what kind of ideal interpolation problem can be written as a limit of Lagrange interpolation problems; we call this the discrete approximation problem for ideal interpolation [5]. This is equal to considering how to discretize the differential operators in the D-invariant subspace of each interpolation site. In [5], by analyzing the structure of the second-order D-invariant subspaces, we give a sufficient condition to solve the discrete approximation problem for this case. This indicates that analyzing the structure of the D-invariant subspaces will help us know more about multivariate polynomial interpolation.

In polynomial system solving, the multiplicity structure at an isolated zero $\widehat{X}$ is identified with the dual space consisting of all linear functionals supported at $\widehat{X}$ that vanish on the entire polynomial ideal generated by the given polynomial system [2]. Here, all the functionals correspond to a vector space, which is D-invariant (some references would use the term “closed”). Dayton and Zeng used the dual space theory to derive special-case polynomial system solving algorithms in 2005 [6]. After that, Zeng presented a new algorithm that substantially reduces the calculation by means of the closedness subspace strategy in his paper [7]. In [8], Li and Zhi demonstrated the explicit structure of the D-invariant subspace in the case of breadth one, which helps to compute the multiplicity structure of an isolated singular solution more efficiently.

We have seen that analyzing the structure of the D-invariant subspaces helps us to study a class of interpolation problems and to improve computational efficiency in polynomial system solving. It is the aim of this paper to describe the structure of the D-invariant subspaces by Cartesian tensors.

In this section, we will recall some basic definitions in symbolic computation [9] and the concept of tensors in multilinear algebra [10].

A monomial order on $\mathbb{F}\left[X\right]$ is any relation ≻ on ${\mathbb{Z}}_{\ge 0}^d$ satisfying the following:

(i) ≻ is a total (or linear) order on ${\mathbb{Z}}_{\ge 0}^d$.

(ii) If $\alpha \succ \beta$ and $\gamma \in {\mathbb{Z}}_{\ge 0}^d$, then $\alpha +\gamma \succ \beta +\gamma$.

(iii) ≻ is a well-order on ${\mathbb{Z}}_{\ge 0}^d$.

Let $f={\sum }_{\alpha }{a}_{\alpha }{X}^{\alpha }\in \mathbb{F}\left[X\right]$ be a nonzero polynomial and ≻ be a monomial order. The multidegree of f is the following:

The leading monomial of f is the following:

The total degree of f, denoted by $\mathrm{deg}\left(f\right)$, is the maximum $\left|\alpha \right|$ such that the coefficient $a_{\alpha }$ is nonzero.

In this paper, we denote by $P_n,n\ge 1,$ a D-invariant polynomial subspace of degree n, i.e., $P_n$ satisfies the following:

(i) $P_n\subset \{f\in \mathbb{F}\left[X\right]:\mathrm{deg}\left(f\right)\le n\}$.

(ii) There exists at least one polynomial of total degree n in $P_n$.

(iii) $\forall p\in P_n$, $D_{j}p\in P_n,\forall j=1,\cdots ,d$.

For any given subspace $P_n$, we also define $P_{<n}:=\{f\in P_n:\mathrm{deg}\left(f\right)<n\}.$

Since $P_n$ is a linear space, we only need to study a special basis of $P_n$ by doing the following: to fix a term order (for example, graded reverse lexicographic order, $1\prec x_d\prec x_{d-1}\prec \cdots \prec x_1\prec x_d^2\prec x_d{x}_{d-1}\prec \cdots$), we first write the polynomials in a given basis of $P_n$ in matrix form, where the columns are indexed by the monomials in increasing order and the rows are indexed by the basis of $P_n$; then, with Gauss–Jordan elimination, we can obtain the reduced row echelon form of this matrix, which gives another basis for $P_n$. We call this new basis the “reduced basis” of $P_n$. In the discussion that follows, by a basis of some subspace, we always mean the reduced basis.

Einstein Convention. Einstein introduced a convention whereby if a particular subscript (e.g., i) appears twice in a single term of an expression, then it is implicitly summed, and i is called a dummy index. For example, in traditional notation, we have the following: and using summation convention, we can simply write the following:

Let ${\mathbf{e}}_i={(0,\cdots ,0,1,0,\cdots ,0)}^{\mathrm{T}}$. Recall that a tensor of real numbers is simply an element in the tensor product of the vector spaces ${\mathbb{R}}^{k_1}\otimes {\mathbb{R}}^{k_2}\otimes \cdots \otimes {\mathbb{R}}^{k_n}$ [11]. Let be the standard basis of ${\mathbb{R}}^{k_1}\otimes {\mathbb{R}}^{k_2}\otimes \cdots \otimes {\mathbb{R}}^{k_n}$, where $\{{\mathbf{e}}_1^{\left(l\right)},{\mathbf{e}}_2^{\left(l\right)},\cdots ,{\mathbf{e}}_{k_l}^{\left(l\right)}\}$ forms a standard basis for ${\mathbb{R}}^{k_l},l=1,\cdots ,n.$ Note that ${\mathbf{e}}_i^{\left(l\right)}·{\mathbf{e}}_j^{\left(l\right)}={\delta }_{ij}$, with $\delta$, the Kronecker delta.

We denote by an nth order Cartesian tensor. Here, the sum over $i_1,i_2,\cdots ,i_n$ is implicit, and $T_{i_1{i}_2\cdots i_n}\in \mathbb{R}$ denotes the weight for ${\mathbf{e}}_{i_1}^{\left(1\right)}\otimes {\mathbf{e}}_{i_2}^{\left(2\right)}\otimes \cdots \otimes {\mathbf{e}}_{i_n}^{\left(n\right)}$ in the sum. Throughout the paper, d denotes the number of indeterminates, so if there is no confusion, we will simply write ${\mathbf{e}}_i$ (i is a subscript) if ${\mathbf{e}}_i^{\left(l\right)}$ is in the standard basis of ${\mathbb{R}}^d$, and write ${\mathbf{e}}^i$ (i is a superscript) if ${\mathbf{e}}_i^{\left(l\right)}$ is in the standard basis of ${\mathbb{R}}^q$, where q need not be equal to d. Particularly, for a second order tensor $T=T_{ij}{\mathbf{e}}_i\otimes {\mathbf{e}}_j$ on ${\mathbb{R}}^d$, $d=3$, representing each basis tensor as a matrix: then T can be written in the form of a square matrix, i.e., $T={\left(T_{ij}\right)}_{3\times 3}$.

The space of symmetric tensors of order n on ${\mathbb{R}}^d$ is naturally isomorphic to the space of homogeneous polynomials of total degree n in d variables [11]. We will use this fact to represent a homogeneous polynomial in $\mathbb{R}\left[X\right]$.

For example, if A and B are matrices, we obtain the following matrix multiplication: etc. The critical request here is that the vectors in the inner product must be of the same dimension.

The structure of $P_2$ was discussed in our paper [5]; we list the results in this section for completeness.

We first consider a special second-degree D-invariant subspace as follows: in which $m_1\le d$ and the superscript indicate the total degree of the polynomial. Without loss of generality, the polynomials of total degree one can be rewritten as the following:

With all $p_i^{\left(1\right)}$, $i=1,\cdots ,m_1,$ given, we have the following result.

Note that E has ${\displaystyle \frac{1}{2}}{m}_1(m_1+1)$ free parameters, and L has $d-m_1$ free parameters. The proof of Theorem 1 also establishes the following result.

We first assume that there is only 1 polynomial of total degree n in $P_n$. In the general case, since we are considering reduced bases, then all polynomials of total degree n in the basis have this form.

Consider the following D-invariant subspace: in which $m_k\le \left(\genfrac{}{}{0pt}{}{d+k-1}{k}\right)$ for $k=1,\cdots ,n-1$. We will discuss the special case where all polynomials in the reduced basis of $P_n$ are restricted to be homogeneous. Let with $b_{t{i}_{\sigma \left(1\right)}{i}_{\sigma \left(2\right)}\cdots i_{\sigma \left(s\right)}}=b_{t{i}_1{i}_2\cdots i_s}$, $m_n=1$.

Similar to the case when $n=3$, let $B_t^{\left(s\right)}=b_{t{i}_1{i}_2\cdots i_s}{\mathbf{e}}_{i_1}\otimes {\mathbf{e}}_{i_2}\otimes \cdots \otimes {\mathbf{e}}_{i_s}$, the following can be verified:

Note that if $s=1$, $B_t^{\left(1\right)}$ is a first order tensor which can be written as a vector as in Section 3; if $s=2$, $B_t^{\left(2\right)}$ is a second order tensor which we write as a matrix in (3). Namely, $p_t^{\left(2\right)}$ has two equivalent forms:

Finally, assuming that $P_{<n}$ is given, we set forth a general form of Theorem 2.

Unlike general linear polynomial subspaces, due to the “closed” property, the relation between the polynomial of higher degree (i.e., $p_t^{\left(s\right)}$) and all linear polynomials in $P_n$ can be observed by the above formula. For the proof of this theorem, we need the following lemmas.

In Theorem 2, we have actually proved the following:

This can be easily generalized to an arbitrary $n,n>3$, as follows.

Li and Zhi demonstrated the structure of the breadth-one D-invariant polynomial subspace in [8]. We analyzed the structure of a second-degree D-invariant polynomial subspace $P_2$ in our previous work [5]. As an application for ideal interpolation, we solved the discrete approximation problem for ${\delta }_{\mathbf{z}}{P}_2\left(D\right)$ under certain conditions. In this work, we discuss the structure of $P_n$ for a special case, where all polynomials in the reduced basis of $P_n$ are restricted to be homogeneous. In the future, we will consider a more general case of $P_n$. For any fixed s and t, we can decompose $p_t^{\left(s\right)}$ into its homogeneous components, and write the following: with $B_{t,j}^{\left(s\right)}$, a jth order symmetric Cartesian tensor for $j=2,\cdots ,s$. Since 1 is always in $P_n$, this means that the constant term in $p_t^{\left(s\right)}$ can be omitted with reduction. We can now analyze the structure of the following: with $P_{<n}$ given. In view of the D-invariance of $P_n$, $B_{1,n}^{\left(n\right)}$ only relates to the highest homogeneous components of all $p_j^{(n-1)},j=1,\cdots ,m_{n-1}$, i.e., $B_{j,n-1}^{(n-1)}$. In addition, note that each $B_{j,n-1}^{(n-1)}$ can be expressed in the same way; hence, $B_{1,n}^{\left(n\right)}$ has the form (17). $B_{1,j}^{\left(n\right)},j=2,\cdots ,n-1$ relates to all the homogeneous complements, which have total degree $j-1$ of polynomials in $P_{<n}$. With linear reduction, $B_{1,1}^{\left(n\right)}$ can be written in the form $B_{1,1}^{\left(n\right)}=(0,\dots ,0,l_{m_1+1}^{\left(n\right)},\cdots ,l_d^{\left(n\right)})$.