An Approximate Decomposition of a Multivariate Polynomial and Its Application
- Open Access
- 01.12.2026
- Research
Erschienen in:
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by (Link öffnet in neuem Fenster)
Abstract
1 Introduction
The polynomial decomposition problem is that given a polynomial f, determine whether there exist polynomials g and h with \(1<\deg g,\deg h <\deg f\) such that \(f=g\circ h,\) and in the affirmative case, compute them. This is a fundamental problem in computer algebra. The univariate case is well studied [1‐6] and the multivariate case is considered under several restrictions [7‐10]. The problem of approximate polynomial decomposition with regard to a given norm is also studied [11‐13]. For example, see [11] for the 2-norm.
If f is decomposable, we may evaluate it efficiently. For example, \(f=x^{10}+8 x^9+18 x^8+14 x^7+29 x^6+33 x^5+57 x^4+23 x^3+37 x^2+22 x+30\) has a decomposition \(f=g\circ h,\) where \(g=x^2 + 3 x + 2\) and \(h=x^5 + 4 x^4 + x^3 + 3 x^2 + 2 x + 4.\) If evaluating f directly by using Horner’s scheme, we need 9 multiplications. On the other hand, by using the representation \(f=g\circ h,\) we need only 5 multiplications. However, the decomposable polynomials are in the minority [14, 15]. An approximate decomposition of f may also reduce the number of multiplications. For example, \(f=x^{10}+2x^8+x^6+5x^5+5x^3+x^2+8x+4\) has an approximate decomposition \(f=g\circ h+\delta ,\) where \(g=x^2+3x, h=x^5+x^3+1\) and \(\delta =x^2+8x.\) If evaluating f directly, we need 9 multiplications. We can easily evaluate \(g\circ h\) and \(\delta ,\) respectively, thus we need only 6 multiplications. Although the cost of computing such an approximate decomposition of f is needed, the total evaluation cost of f by using an approximate decomposition may be smaller than that of f by using Horner’s scheme directly when we evaluate f at many points.
Anzeige
Sekigawa proposed an algorithm for computing an approximate decomposition of a univariate polynomial in the Hamming distance [13]. In this paper, by using a generalization of Dickerson’s result [7], we construct an algorithm for computing an approximate decomposition of a multivariate polynomial in the Hamming distance and introduce its application to multivariate Horner’s scheme [16] when we evaluate f at many points.
This paper is organized as follows. In Sect. 2, we prepare some notations and introduce a problem. In Sect. 3, we prove the main theorem for the construction of an algorithm. Then we propose an approximation algorithm for the problem and demonstrate its application for multivariate Horner’s scheme. Finally, in Sect. 4, we describe conclusions of this paper and future work.
2 Preliminary
We give some definitions and introduce a problem. In this paper, let K be a field, and fix a monomial order on monomials in \(x_1,\ldots ,x_d\) (for example, graded lexicographic order).
Definition 1
Let \(f,g\in K[x_1,\ldots ,x_d]\) and \(x^\alpha \) be a monomial in \(x_1,\ldots ,x_d.\)
-
We define \({\textrm{coeff}}(f,x^\alpha )\) as the coefficient of \(x^\alpha \) in f.
-
A polynomial f is said to be a polynomial of degree \(n_1\times \cdots \times n_d\) if \(\deg f=n_1+\cdots +n_d\) and \(\deg _{x_i}f=n_i\) for each \(1\le i\le d.\)
-
We define d(f, g) as the Hamming distance between the vector of coefficients of f and that of g, after padding zero coefficients if necessary.
-
A polynomial f is said to be normal if f is monic and \(f(0,\ldots ,0)=0.\)
Anzeige
Definition 2
Given a polynomial \(f\in K[x_1,\ldots ,x_d]\) of degree \(n_1\times \cdots \times n_d\) and integers \(r\in {\mathbb {N}}_{\ge 2}\) and \(s_1,\ldots ,s_d\in {\mathbb {N}}\) with \(n_i=rs_i\) for \(1\le i\le d,\) we call \(\tilde{f}\) the nearest decomposable polynomial to f if \(\tilde{f}\) satisfies the following conditions:
-
\(\tilde{f}=g\circ h,\) where g and h are polynomials of degree r and \(s_1\times \cdots \times s_d,\) respectively.
-
The distance \(d(f,\tilde{f})\) is minimal.
We consider the following problem:
Problem 1
Given a polynomial \(f\in K[x_1,\ldots ,x_d]\) of degree \(n_1\times \cdots \times n_d\) with \(\gcd (n_1,\ldots ,n_d)>1\) and \(r\in {\mathbb {N}}_{\ge 2}, s_1,\ldots ,s_d\in {\mathbb {N}}\) with \(n_i=rs_i\) for \(1\le i\le d,\) compute the nearest decomposable polynomial to f and its decomposition.
Remark 2
The condition \(\gcd (n_1,\ldots ,n_d)>1\) is needed to obtain a nontrivial decomposition since the degree of f in each variable is multiplicative with respect to a composition; \(\deg _{x_i}f=\deg g \cdot \deg _{x_i}h\) holds for \(1\le i\le d\) if f is represented as a composition \(f=g\circ h.\)
Let a be the leading coefficient of f and \(b=f(0,\ldots ,0),\) then \(f=g\circ h+\delta \) if and only if \(a^{-1}(f-b)=(a^{-1}(g-b))\circ h+a^{-1}\delta .\) It is clear that \(d(f,g\circ h)=d(a^{-1}(f-b),(a^{-1}(g-b))\circ h)\) and \(a^{-1}(f-b)\) is normal. Thus, it is sufficient to consider normal polynomials f in Problem 1.
Remark 3
Ensuring the minimality of the Hamming distance in Problem 1 is a difficult problem. To our knowledge, there is no efficient algorithm for solving Problem 1 even in the case where the characteristic of K is zero. However, in evaluating a polynomial, it is not necessary to obtain the true solution to Problem 1; an approximate nearest decomposable polynomial \(\tilde{f}\) to f, that is, \(\tilde{f}\) represented as a composition \(g\circ h\) without the condition that \(d(f,\tilde{f})\) is minimal, can be useful. Hence, we consider an approximation algorithm for Problem 1. Note that this definition includes trivial solutions such as \(f=g\circ 0+f,\) but our algorithm always computes a nontrivial approximate nearest decomposable polynomial.
3 Main Results
3.1 Main Theorem
In this section, we prove a generalization of Dickerson’s result [7] for construction of an algorithm. First we prepare some notations for the proof. The following definition is motivated by Definition 2.3 in [7]:
Definition 3
Let \(\vec {j}_d=(j_1,\ldots ,j_d), \vec {s}_d=(s_1,\ldots ,s_d)\) and \(\vec {e}_k\in {\mathbb {N}}^d\) be the k-th standard basis vector. Let \(Z_{k,\vec {j}_d}\) and \(Y_{\vec {j}_d}\) be as follows:where c’s are indeterminates and \(Z_{k,\vec {j}_d}=0\) when \(\vec {j}_d\) has a negative entry. By the definition the following equalities hold.
$$\begin{aligned} Z_{k,\vec {j}_d}= & \sum _{i_1=0}^{j_1}\cdots \sum _{i_k=0}^{j_k} c_{s_1-i_1,\ldots ,s_k-i_{k},s_{k+1}-j_{k+1},\ldots ,s_d-j_d}x_1^{s_1-i_1}\cdots x_k^{s_k-i_k}x_{k+1}^{s_{k+1}-j_{k+1}}\cdots x_d^{s_d-j_d},\\ Y_{\vec {j}_d}= & \sum _{k=1}^{d-1}Z_{k,\vec {j}_d-\vec {e}_k}, \end{aligned}$$
$$\begin{aligned} Z_{d,\vec {j}_d}= & Z_{d,\vec {j}_d-\vec {e}_d}+Z_{d-1,\vec {j}_d},\end{aligned}$$
(1)
$$\begin{aligned} Z_{d,\vec {j}_d}= & Z_{d,\vec {j}_d-\vec {e}_d}+Y_{\vec {j}_d}+c_{\vec {s}_d-\vec {j}_d}x^{\vec {s}_d-\vec {j}_d}. \end{aligned}$$
(2)
Hereafter, we assume that the characteristic of K does not divide r. The following is the main theorem.
Theorem 4
Let f be a normal polynomial of degree \(n_1\times \cdots \times n_d\) with \(\gcd (n_1,\ldots ,n_d)>1\) and \(r\in {\mathbb {N}}_{\ge 2},\vec {s}_d\in {\mathbb {N}}^d\) with \(n_i=rs_i\) for \(1\le i\le d.\) Then there uniquely exists a normal polynomial h of degree \(s_1\times \cdots \times s_d\) such that the equalities \({\textrm{coeff}}(f,x^{\vec {n}_d-\vec {i}_d})= {\textrm{coeff}}(h^r,x^{\vec {n}_d-\vec {i}_d})\) hold for \(0\le i_l\le s_l, 1\le l\le d\) except for \(\vec {i}_d= \vec {s}_d.\)
This theorem is a generalization of the following Dickerson’s result, which is the case \(j_1=\cdots =j_d=s\) of Lemma 2.7 in [7]:
Proposition 5
Let f be a normal polynomial of degree \(n\times \cdots \times n\) such that \(f=g\circ h,\) where g and h are normal polynomials of degree r and \(s\times \cdots \times s,\) respectively. Let \(\vec {n}=(n,\ldots ,n), \vec {s}=(s,\ldots ,s)\in {\mathbb {N}}^d.\) Then the equalities \({\textrm{coeff}}(f,x^{\vec {n}-\vec {i}_d})={\textrm{coeff}}(h^r,x^{\vec {n}-\vec {i}_d})\) hold for \(0\le i_l\le s, 1\le l\le d\) except for \(\vec {i}_d=\vec {s}.\)
In other words, Proposition 5 implies that Theorem 4 holds for decomposable polynomials of the same degree \(n\times \cdots \times n.\) Theorem 4 is a generalization of Proposition 5 for polynomials of degree \(n_1\times \cdots \times n_d,\) which include indecomposable polynomials as well as decomposable polynomials.
To prove Theorem 4, we need a lemma and a proposition. We can easily prove the following lemma.
Lemma 6
Let \(I=\{\vec {i}_d \mid 0\le i_k\le j_k-1 {\text { for some }} k, 0\le i_m\le j_m {\text { for }} m\ne k\}.\) Then we can write \(I=I_1\cup I_2,\) where \(I_1\) and \(I_2\) as follows :
$$\begin{aligned} I_1= & \{\vec {i}_d \mid 0\le i_l\le j_l {\text { for }} l\ne d {\text { and }} 0\le i_d\le j_d-1\},\\ I_2= & \bigcup _{1\le k\le d-1}\{\vec {i}_d\mid 0\le i_l\le j_l {\text { for }} l\ne k, d, 0\le i_k\le j_k-1 {\text { and }} i_d=j_d\}. \end{aligned}$$
The following proposition is important to construct h in Theorem 4.
Proposition 7
Let \(\vec {j}_d\ne \vec {s}_d\) with \(0\le j_l \le s_l,\) \(1\le l\le d\) and f be as in Theorem 4. Then by setting suitable coefficients of \(Z_{d,\vec {j}_d},\) \(Z_{d,\vec {j}_d}\) satisfies the equalities \({\textrm{coeff}}(Z_{d,\vec {j}_d}^r,x^{\vec {n}_d-\vec {i}_d})={\textrm{coeff}}(f,x^{\vec {n}_d-\vec {i}_d})\) for \(0\le i_l\le j_l, 1\le l\le d.\)
Proof
Set \(Z_{d,\vec {0}}=x^{\vec {s}_d}\) then Proposition 7 holds for \(Z_{d,\vec {0}}\) because f and \(Z_{d,\vec {0}}^r\) are monic. Then all \(Z_{d,\vec {j}_d}\) are monic from the definition of \(Z_{d,{\vec {j}_d}}\) and (1). We assume that \(Z_{d,\vec {l}_d}\) satisfies the equalities in Proposition 7 for \(\vec {l}_d\) such that \(0\le l_k\le j_k, 1\le k\le d\) and \(\sum l_k\le \sum j_k-1.\) We show that \(Z_{d,\vec {j}_d}\) also satisfies them by setting the suitable coefficient \(c_{\vec {s}_d-\vec {j}_d}.\)
Take the r-th power of both sides in (2),where \(w_1\) is a polynomial with \(\deg _{x_d}w_1\le s_d(r-2)+2(s_d-j_d)=n_d-2j_d<n_d-j_d.\) Since \(w_1\) does not affect the coefficient of \(x^{\vec {n}_d-\vec {j}_d}\) thenThus set \(c_{\vec {s}_d-\vec {j}_d}\) as follows then \({\textrm{coeff}}(f,x^{\vec {n}_d-\vec {j}_d})={\textrm{coeff}}(Z_{d,\vec {j}_d}^r,x^{\vec {n}_d-\vec {j}_d}).\)Let \(I=\{\vec {i}_d \mid 0\le i_k\le j_k-1 {\text { for some }} k, 0\le i_m\le j_m {\text { for }} m\ne k\}.\) Next we show that \(Z_{d,\vec {j}_d}\) satisfies the equalities \({\textrm{coeff}}(Z_{d,\vec {j}_d}^r,x^{\vec {n}_d-\vec {i}_d})={\textrm{coeff}}(f,x^{\vec {n}_d-\vec {i}_d})\) for \(\vec {i}_d\in I.\) From Lemma 6, it suffices that we show the above properties for \(\vec {i}_d\in I_1\) and \(\vec {i}_d\in I_2.\)
$$\begin{aligned} Z_{d,\vec {j}_d}^r=Z_{d,\vec {j}_d-\vec {e}_d}^r+r Z_{d,\vec {j}_d-\vec {e}_d}^{r-1}Y_{\vec {j}_d}+rc_{\vec {s}_d-\vec {j}_d}Z_{d,\vec {j}_d-\vec {e}_d}^{r-1}x^{\vec {s}_d-\vec {j}_d}+w_1(x), \end{aligned}$$
(3)
$$\begin{aligned} {\textrm{coeff}}(Z_{d,\vec {j}_d}^r,x^{\vec {n}_d-\vec {j}_d})={\textrm{coeff}}(Z_{d,\vec {j}_d-\vec {e}_d}^r,x^{\vec {n}_d-\vec {j}_d})+{\textrm{coeff}}(r Z_{d,\vec {j}_d-\vec {e}_d}^{r-1}Y_{\vec {j}_d},x^{\vec {n}_d-\vec {j}_d})+rc_{\vec {s}_d-\vec {j}_d}. \end{aligned}$$
$$\begin{aligned} c_{\vec {s}_d-\vec {j}_d}=\frac{{\textrm{coeff}}(f,x^{\vec {n}_d-\vec {j}_d})-{\textrm{coeff}}(Z_{d,\vec {j}_d-\vec {e}_d}^r,x^{\vec {n}_d-\vec {j}_d})-{\textrm{coeff}}(r Z_{d,\vec {j}_d-\vec {e}_d}^{r-1}Y_{\vec {j}_d},x^{\vec {n}_d-\vec {j}_d})}{r}. \end{aligned}$$
(4)
Let \(\vec {i}_d\in I_1.\) Take the r-th power of both sides in (2),where \(w_2\) is a polynomial with \(\deg _{x_d}w_2\le (r-2)s_d+2(s_d-j_d)=n_d-2j_d<n_d-j_d<n_d-(j_d-1)\le n_d-i_d.\) Moreover, \(\deg _{x_d}Z_{d,\vec {j}_d-\vec {e}_d}^{r-1}Z_{d-1,\vec {j}_d}\le (r-1)s_d+s_d-j_d=n_d-j_d<n_d-i_d\) hence the polynomials \(Z_{d,\vec {j}_d-\vec {e}_d}^{r-1}Z_{d-1,\vec {j}_d}\) and \(w_2(x)\) do not affect the coefficient of \(x^{\vec {n}_d-\vec {i}_d}.\) Thenbecause \(Z_{d,\vec {j}_d-\vec {e}_d}\) satisfies the equalities in Proposition 7.
$$\begin{aligned} Z_{d,\vec {j}_d}^r=Z_{d,\vec {j}_d-\vec {e}_d}^r+r Z_{d,\vec {j}_d-\vec {e}_d}^{r-1}Z_{d-1,\vec {j}_d}+w_2(x), \end{aligned}$$
$$\begin{aligned} {\textrm{coeff}}(Z_{d,\vec {j}_d}^r,x^{\vec {n}_d-\vec {i}_d})={\textrm{coeff}}(Z_{d,\vec {j}_d-\vec {e}_d}^r,x^{\vec {n}_d-\vec {j}_d})={\textrm{coeff}}(f,x^{\vec {n}_d-\vec {i}_d}) \end{aligned}$$
Let \(\vec {i}_d\in I_2.\) Then there exists k such that \(0\le i_l\le j_l\) for \(l\ne k,\) \(0\le i_k\le j_k-1\) and \(i_d=j_d.\) In (3), \(\deg _{x_d}w_1<n_d-j_d=n_d-i_d\) and \(\deg _{x_k}Z_{d,\vec {j}_d-\vec {e}_d}^{r-1}x^{\vec {s}_d-\vec {j}_d}\le (r-1)s_k+s_k-j_k=n_k-j_k<n_k-(j_k-1)\le n_k-i_k.\) Thus, the polynomials \(w_1\) and \(Z_{d,\vec {j}_d-\vec {e}_d}^{r-1}x^{\vec {s}_d-\vec {j}_d}\) do not affect the coefficient of \(x^{\vec {n}_d-\vec {i}_d}.\) Moreover, \(c_{\vec {s}_d-\vec {i}_d}\) is represented as (4) thenwhere \(S_1\) and \(S_2\) are as follows:In order to show \({\textrm{coeff}}(Z_{d,\vec {j}_d}^r,x^{\vec {n}_d-\vec {i}_d})={\textrm{coeff}}(f,x^{\vec {n}_d-\vec {i}_d}),\) we show \(S_1\) and \(S_2\) are zero.
$$\begin{aligned} {\textrm{coeff}} & \!\!(Z_{d,\vec {j}_d}^r,x^{\vec {n}_d-\vec {i}_d})\\ & ={\textrm{coeff}}(Z_{d,\vec {j}_d-\vec {e}_d}^r,x^{\vec {n}_d-\vec {i}_d})+{\textrm{coeff}}(r Z_{d,\vec {j}_d-\vec {e}_d}^{r-1}Y_{\vec {j}_d},x^{\vec {n}_d-\vec {i}_d})+rc_{\vec {s}_d-\vec {i}_d}-rc_{\vec {s}_d-\vec {i}_d}\\ & ={\textrm{coeff}}(f,x^{\vec {n}_d-\vec {i}_d})+({\textrm{coeff}}(Z_{d,\vec {j}_d-\vec {e}_d}^r,x^{\vec {n}_d-\vec {i}_d})-{\textrm{coeff}}(Z_{d,\vec {i}_d-\vec {e}_d}^r,x^{\vec {n}_d-\vec {i}_d}))\\ & \quad +r({\textrm{coeff}}(Z_{d,\vec {j}_d-\vec {e}_d}^{r-1}Y_{\vec {j}_d},x^{\vec {n}_d-\vec {i}_d})-{\textrm{coeff}}(Z_{d,\vec {i}_d-\vec {e}_d}^{r-1}Y_{\vec {i}_d},x^{\vec {n}_d-\vec {i}_d})-c_{\vec {s}_d-\vec {i}_d})\\ & ={\textrm{coeff}}(f,x^{\vec {n}_d-\vec {i}_d})+S_1+S_2, \end{aligned}$$
$$\begin{aligned} S_1= & {\textrm{coeff}}(Z_{d,\vec {j}_d-\vec {e}_d}^r,x^{\vec {n}_d-\vec {i}_d})-{\textrm{coeff}}(Z_{d,\vec {i}_d-\vec {e}_d}^r,x^{\vec {n}_d-\vec {i}_d}),\\ S_2= & r({\textrm{coeff}}(Z_{d,\vec {j}_d-\vec {e}_d}^{r-1}Y_{\vec {j}_d},x^{\vec {n}_d-\vec {i}_d})-{\textrm{coeff}}(Z_{d,\vec {i}_d-\vec {e}_d}^{r-1}Y_{\vec {i}_d},x^{\vec {n}_d-\vec {i}_d})-c_{\vec {s}_d-\vec {i}_d}). \end{aligned}$$
First we show \(S_1=0.\) The polynomial \(Z_{d,\vec {j}_d-\vec {e}_d}-Z_{d,\vec {i}_d-\vec {e}_d}\) can be written as follows.whereFor \(\vec {l}_d\in L_1\backslash L_2,\) there exists m such that \(1\le m\le d-1\) and \(i_m<l_m\le j_m.\) Thus, we havewhere \(p_1\) is a polynomial whose every term t satisfies \(\deg _{x_m}t\le (r-1)s_m+(s_m-l_m)=n_m-l_m<n_m-i_m\) for some \(1\le m\le d-1.\) Thus, \(p_1\) does not affect the coefficient of \(x^{\vec {n}_d-\vec {i}_d}\) thenthat is, \(S_1=0.\)
$$\begin{aligned} Z_{d,\vec {j}_d-\vec {e}_d}-Z_{d,\vec {i}_d-\vec {e}_d}=\sum _{\vec {l}_d\in L_1\backslash L_2}c_{\vec {s}_d-\vec {l}_d}x^{\vec {s}_d-\vec {l}_d}, \end{aligned}$$
$$\begin{aligned} L_1= & \{\vec {l}_d \mid 0\le l_m\le j_m, 1\le m\le d-1, 0\le l_d\le j_d-1\},\\ L_2= & \{\vec {l}_d \mid 0\le l_m\le i_m, 1\le m\le d-1, 0\le l_d\le j_d-1\}. \end{aligned}$$
$$\begin{aligned} Z_{d,\vec {j}_d-\vec {e}_d}^r=Z_{d,\vec {i}_d-\vec {e}_d}^r+p_1, \end{aligned}$$
$$\begin{aligned} {\textrm{coeff}}(Z_{d,\vec {j}_d-\vec {e}_d}^r,x^{\vec {n}_d-\vec {i}_d})={\textrm{coeff}}(Z_{d,\vec {i}_d-\vec {e}_d}^r,x^{\vec {n}_d-\vec {i}_d}), \end{aligned}$$
Secondly we show \(S_2=0.\) Since \(c_{\vec {s}_d-\vec {i}_d}\) can be written as in (4) and Proposition 7 holds for \(Z_{d,\vec {i}_d},\)We can easily check \({\textrm{coeff}}(Z_{d,\vec {i}_d}^r,x^{\vec {n}_d-\vec {i}_d})={\textrm{coeff}}(Z_{d,\vec {j}_d}^r,x^{\vec {n}_d-\vec {i}_d})\) similarly to the proof of \(S_1=0.\) Hence, we have \(S_2=0.\) Therefore the equalities \({\textrm{coeff}}(Z_{d,\vec {j}_d}^r,x^{\vec {n}_d-\vec {i}_d})={\textrm{coeff}}(f,x^{\vec {n}_d-\vec {i}_d})\) hold for \(\vec {i}_d\in I\) and \(\vec {i}_d=\vec {j}_d,\) that is, Proposition 7 holds for \(Z_{d,\vec {j}_d}.\) \(\square \)
$$\begin{aligned} & rc_{\vec {s}_d-\vec {i}_d}+r{\textrm{coeff}}(Z_{d,\vec {i}_d-\vec {e}_d}^{r-1}Y_{\vec {i}_d},x^{\vec {n}_d-\vec {i}_d})\\ & \quad ={\textrm{coeff}}(Z_{d,\vec {i}_d}^r,x^{\vec {n}_d-\vec {i}_d})-{\textrm{coeff}}(Z_{d,\vec {j}_d}^r,x^{\vec {n}_d-\vec {i}_d})+r{\textrm{coeff}}(Z_{d,\vec {j}_d-\vec {e}_d}^{r-1}Y_{\vec {j}_d},x^{\vec {n}_d-\vec {i}_d}). \end{aligned}$$
Proof of Theorem 4
Take \(Z_{d,\vec {s}_d-\vec {e}_1},\ldots ,Z_{d,\vec {s}_d-\vec {e}_d}\) which satisfy the equalities in Proposition 7. Set \(h=Z_{d,\vec {s}_d-\vec {e}_d}+Y_{\vec {s}_d},\) then it follows that h is as in Theorem 4 from the same discussions in Proposition 7.
If \(h_1\) and \(h_2\) satisfy the conditions of Theorem 4, then \({\textrm{coeff}}(h_1^r,x^{\vec {n}_d-\vec {i}_d})={\textrm{coeff}}(h_2^r,x^{\vec {n}_d-\vec {i}_d})\) hold for \(0\le i_l\le s_l, 1\le l\le d\) except for \(\vec {i}_d= \vec {s}_d.\) By determining their coefficients from high order terms with the use of these equalities, we can easily show the equalities \({\textrm{coeff}}(h_1,x^{\vec {s}_d-\vec {i}_d})={\textrm{coeff}}(h_2,x^{\vec {s}_d-\vec {i}_d})\) hold except for \(\vec {i}_d=\vec {s}_d,\) that is, the polynomials \(h_1\) and \(h_2\) agree on their coefficients except for the constant term. Since \(h_1\) and \(h_2\) are normal, we have \(h_1=h_2.\) \(\square \)
Remark 8
If f has a decomposition \(f=g^\prime \circ h^\prime ,\) where \(g^\prime \) and \(h^\prime \) are normal polynomials of degree r and \(s_1\times \cdots \times s_d,\) respectively, then \(h^\prime =h.\) Indeed, f can be written aswhere \(g^\prime =x^r+b_{r-1}x^{r-1}+\cdots +b_1x.\) Let \(\vec {i}_d\) with \(0\le i_l\le s_l, 1\le l\le d\) and \(\vec {i}_d\ne \vec {s}_d\) then \(\deg _{x_d}h^{r-j}\le (r-j)s_d<n_d-i_d\) for \(2\le j\le d.\) Thus, we haveSince \(\vec {i}_d\ne \vec {s}\) there exists m such that \(i_m<s_m\) then \(\deg _{x_m}h^{r-1}\le (r-1)s_m=n_m-s_m<n_m-i_m.\) Hence, the following equality holds.From the uniqueness of h in Theorem 4, we have \(h^\prime =h.\)
$$\begin{aligned} f={h^\prime }^r+b_{r-1}{h^\prime }^{r-1}+\cdots +b_1h^\prime , \end{aligned}$$
$$\begin{aligned} {\textrm{coeff}}(f,x^{\vec {n}_d-\vec {i}_d})={\textrm{coeff}}({h^\prime }^r,x^{\vec {n}_d-\vec {i}_d})+b_{r-1}{\textrm{coeff}}({h^\prime }^{r-1},x^{\vec {n}_d-\vec {i}_d}). \end{aligned}$$
$$\begin{aligned} {\textrm{coeff}}(f,x^{\vec {n}_d-\vec {i}_d})={\textrm{coeff}}({h^\prime }^r,x^{\vec {n}_d-\vec {i}_d}). \end{aligned}$$
3.2 Algorithm and Its Application
We proved Theorem 4 constructively, thus we can compute h by the following algorithm.
Algorithm 1
Computation of h
Remark 9
Computing coefficients \(c_{\vec {s}_d-\vec {j}_d}\) can be executed in polynomial time, hence this is a polynomial time algorithm. Moreover, the computations in Step 4 can be parallelized because for \(\vec {j}_d\in L_i,\) \(c_{\vec {s}_d-\vec {j}_d}\) depends only on \(c_{\vec {s}_d-\vec {l}_d}\) with \(\vec {l}_d\in \bigcup _{0\le k\le i-1}L_k,\) which have been computed before.
The following is an approximation algorithm for computing the nearest decomposable polynomial to f and its decomposition, which is an extended version of the algorithm in [13] for the multivariate case. In the algorithm, \(N_i(\delta )\) means the number of zero coefficients from \(x^{\vec {n}_d-i\vec {s}_d}\) to \(x^{\vec {n}_d-(i-1)\vec {s}_d}.\)
Algorithm 2
ApproximateDecomp
Remark 10
In Algorithm 2, Inequality (5) means that we update \(\delta \) for its zero coefficients to increase for each \(1\le i\le r-1.\) Indeed, \({\textrm{coeff}}(\delta -ah^i,x^{i\vec {s}_d})=0\) due to the choice of a thus we can increase at least 1 zero coefficients of \(\delta \) in Step 4.
The dominant part of Algorithm 2 is Step 1; thus from Remark 9, this is a polynomial time algorithm.
Algorithm 2 always computes \((g,h,\delta )\) with \(\deg g=r\) and \(\deg h=s_1\times \cdots \times s_d\) from the constructions of g and h, thus we obtain a nontrivial approximate nearest decomposable polynomial.
Example 11
Let \(f=x^4 y^4+6 x^3 y^4+9 x^2 y^4+6 x^2 y^3+4 x^2+18 x y^3+9 y^2+5 y\) be a polynomial of degree \(4\times 4, r=2\) and \(\vec {s}_2=(2,2).\) By using Algorithm 1, we have \(h=x^2 y^2+3 x y^2+3 y.\) Executing between Steps 3 and 5 in Algorithm 2, we obtain \(g=x^2\) and \(\delta =4x^2+5y.\) Then we have an approximate decomposition of \(f=g\circ h+\delta =x^2\circ (x^2y^2+3x y^2+3y)+4x^2+5y\) with \(d(f,g\circ h)=2.\)
We analyze the output of Algorithm 2.
Proposition 12
Let \((g,h,\delta )\) be the output of Algorithm 2 for an input \((f,r,\vec {s}_d).\)
(i)
If f has a decomposition \(f=g^\prime \circ h^\prime ,\) where \(g^\prime \) and \(h^\prime \) are normal polynomials of degree r and \(s_1\times \cdots \times s_d,\) respectively, then \((g,h,\delta )=(g^\prime ,h^\prime ,0),\) that is, Algorithm 2 computes a decomposition of f.
(ii)
The following inequality holds :
$$\begin{aligned} \deg \delta \le \sum _{1\le l\le d}n_l-\min \{s_1,\ldots ,s_d\}-1. \end{aligned}$$
(iii)
The following inequality holds :
$$\begin{aligned} d(f,g\circ h)\le \prod _{1\le l\le d}(n_l+1)-\prod _{1\le l\le d}(s_l+1)-r+1. \end{aligned}$$
Proof
(i)
From Remark 8, we have \(h=h^\prime .\) Let \(g^\prime =x^r+b_{r-1}x^{r-1}+\cdots +b_1x\) then \(f=h^r+b_{r-1}h^{r-1}+\cdots +b_1h.\) In Step 2, set \(\delta =b_{r-1}h^{r-1}+\cdots +b_1h, g=x^r\) and \(i=r-1.\) Since \(\deg _{x_d}h^{r-j}\le (r-j)s_d<n_d-s_d\) for \(2\le j\le d\) and \({\textrm{coeff}}(h^{r-1},x^{i\vec {s}_d})=1\) then we have Then Inequality (5) holds and we update \(\delta \) and g as follows: Similarly, for each iteration, Inequality (5) always holds and \(a=b_{r-j}\) when \(i=r-j.\) Finally, set \(\delta =0\) and \(g=x^r+b_{r-1}x^{r-1}+\cdots +b_1x=g^\prime \) when \(i=1.\) Thus, \((g,h,\delta )=(g^\prime ,h^\prime ,0).\)
$$\begin{aligned} a={\textrm{coeff}}(\delta ,x^{i\vec {s}_d})=b_{r-1},\qquad \delta -ah^i=b_{r-2}h^{r-2}+\cdots +b_1h. \end{aligned}$$
$$\begin{aligned} \delta= & b_{r-2}h^{r-2}+\cdots +b_1h,\\ g= & x^r+b_{r-1}x^{r-1}. \end{aligned}$$
(ii)
From Theorem 4, \(\delta \) may have monomials \(x_1^{n_1-s_1-1}\cdots x_d^{n_d},\ldots , x_1^{n_1}\cdots x_d^{n_d-s_d-1}\) and degrees of the other monomials in \(\delta \) are less than that of one of them. Therefore
$$\begin{aligned} \deg \delta\le & \max \{\deg (x_1^{n_1-s_1-1}\cdots x_d^{n_d}),\cdots \deg (x_1^{n_1}\cdots x_d^{n_d-s_d-1})\}\\= & \max \{\sum _{1\le l\le d}n_l-s_1-1,\ldots ,\sum _{1\le l\le d}n_l-s_d-1\}\\= & \sum _{1\le l\le d}n_l-\min \{s_1,\ldots ,s_d\}-1. \end{aligned}$$
(iii)
From Theorem 4, \({\textrm{coeff}}(f,x^{\vec {n}_d-\vec {i}_d})={\textrm{coeff}}(h^r,x^{\vec {n}_d-\vec {i}_d})\) for \(0\le i_l\le s_l, 1\le l\le d\) except for \(\vec {i}_d=\vec {s}_d.\) Moreover, f and \(h^r\) are normal hence we have From Remark 10, the number of zero coefficients of \(\delta \) increases at least 1 per one iteration. Thus the inequality holds. \(\square \)
$$\begin{aligned} d(f,h^r)\le \prod _{1\le l\le d}(n_l+1)-\prod _{1\le l\le d}(s_l+1). \end{aligned}$$
We demonstrate that an approximate decomposition may reduce the number of multiplications in multivariate Horner’s scheme.
Proposition 13
[16, Theorem 3.1] The evaluation of \(f\in K[x_1,\ldots ,x_d]\) of total degree k by multivariate Horner’s scheme requires \(\left( {\begin{array}{c}d+k\\ k\end{array}}\right) -1\) multiplications and the same number of additions, hence \(2\left( {\begin{array}{c}d+k\\ k\end{array}}\right) -2\) operations.
Definition 4
We define \(B_1\) and \(B_2\) as follows:where \(N=\sum _{1\le l \le d}n_l, S=\sum _{1\le l\le d}s_l\) and \(D=\sum _{1\le l\le d}n_l-\min \{s_1,\ldots ,s_d\}-1.\) \(B_1\) is an upper bound of the number of multiplications to evaluate f directly and \(B_2\) is that of the number of multiplications to evaluate g, h and \(\delta .\)
$$\begin{aligned} B_1=\left( {\begin{array}{c}d+N\\ N\end{array}}\right) -1,\qquad B_2=\left( {\begin{array}{c}d+S\\ S\end{array}}\right) +\left( {\begin{array}{c}d+D\\ D\end{array}}\right) +r-2, \end{aligned}$$
Example 14
Let \((g,h,\delta )\) be the output of Algorithm 2 for an input (f, 2, (5, 5, 5)), where \(f\in K[x_1,x_2,x_3]\) is a normal polynomial of degree \(10\times 10 \times 10.\) Then \(B_1=5455\) and \(B_2=3741.\) In this case an approximate decomposition may reduce 1714 multiplications per one evaluation.
4 Conclusion
For a multivariate polynomial of degree \(n_1\times \cdots \times n_d,\) we have constructed an algorithm for computing an approximate decomposition in the Hamming distance and introduce its application to multivariate Horner’s scheme when evaluating f at many points. When an input polynomial is decomposable, Algorithm 2 computes the true solution to Problem 1; however, when it is indecomposable, we cannot determine the extent of the difference between the true solution and the output. Thus for future work, we need to analyze the difference.
Acknowledgements
The authors would like to thank the reviewers for their careful reading of the manuscript and their insightful comments.
Declarations
Conflict of Interest
The authors declare no competing interests.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
