For univariate polynomials, the approximate GCD can be obtained by computing the null space of the subresultant matrix of given polynomials. In this study, for multivariate polynomials, we propose a method for computing null space of the subresultant matrix within polynomials stably and eficiently, which is based on the SVD (singular value decomposition) and lifting techniques. Therefore, we show the multivariate approximate GCD can be also computed by using subresultant matrix. In addition, we describe an ill-conditioned case (initial factors have approximate common factor) and solve them.
Let (, ) and (, ) be multivariate polynomials in F[, 1, . . . , ℓ] = F[, ] ( is the main variable and = (1, . . . , ℓ) are sub-variables), and be expressed as (, ) (, ) = = ˜ (, )(, ) + ∆ = () + . . . + 0(), ˜(, )(, ) + ∆ = () + . . . + 0().
Here, ˜ , ˜, , ∆ , ∆ are polynomials in F[, ], and when ||∆ || ≪ || || and ||∆ || ≪ || ||, is called an approximate factor of and . In particular, the approximate factor of maximum degree is called approximate GCD, which is denoted by gcd(, ).
Various algorithm exist for the approximate GCD of univariate polynomials. However, there are few stable all-purpose methods for a large number of variables in a multivariate case. Numericalbased methods are stable but significantly less eficient, so we have tried to improve eficiency by combining lifting methods [4]. In this study, we challenge the stable computation of the null space of the subresultant within polynomial entries.
First, we review the method for the subresultant matrix for multivariate polynomials. For the resultant within polynomials, we propose a QRGCD-like method over truncated power-series polynomials, it is eficient [ 5]. For the null space of the subresultant matrix, Gao et al. and Zeng-Dayton proposed SVD-based methods for numeric matrices at the same conference [2, 7], where the SVD is the singular value decomposition for matrix. These matrices are sparse and the size are also huge extremely although the degree of given polynomial is not large. Lifting techniques is known for solving of equation modulo an ideal and lifting them to solution modulo 2, 3, . . . in order to get the ideal adic completion. Here is an ideal as = ⟨1 − 1, . . . , ℓ − ℓ⟩ with (1, . . . , ℓ) ∈ Fℓ (in this paper, (1, . . . , ℓ) is the origin). For multivariate GCD computation, the EZ-GCD method is well-known lifting method based on Hensel’s lemma, however, its approximate computation will be unstable when initial factors have an approximate common factor [8].
In this paper, we propose a stable multivariate approximate GCD computation, which is based on the SVD and lifting techniques. It is able to compute the approximate GCD even though initial factors have approximate common factors.
(0)() + · (
In non-singular case, the following two conditions exist: deg(gcd(, )) ≤ deg(gcd( (0), (0))) and gcd(, )|gcd( (0), (0)). In such situations, lifting algorithms can be applied. The proposed algorithm is discussed in the next section. 2.1. Computing cofactors of and via lifting method be represented as Let (, ) = ∈ F[, ](+− 2)× (+− 2) be an th-subresultant matrix of and w.r.t. , and = = ⎛ . .
. ⎜ ⎜ ⎜⎜ − − ⎜⎜⎝ ... (0) + · (1) + . . . + · () + . . . , where (0) = (0) ∈ F(+− 2)× (+− 2) and () ∈ F[](+− 2)× (+− 2) for ≥ 1.
When = deg(gcd(, )) = deg(gcd( (0), (0))), it is well-known as the null space of − 1 corresponds to ˜ and ˜ , and rank(− 1) = − 1 where = − ( − 1) + − ( − 1). computation of cofactors for univariate part: SVD Cofactors of (0) and (0) can be obtained from the null space of (0−)1. In this paper, we compute the null space of (0−)1 using the SVD [1]. Using the SVD of (0−)1, we obtain the following decomposition: (0) − 1 = Σ = (︀ 1 · · · )︀ ⎜ ⎝ ⎛ 1 . . .
⎞ ⎛ 1 ⎞ ⎠⎟ ⎝⎜ ...
⎟ , ⎠ with 1 ≥ 2 ≥ . . . ≥ − 1 ≫ ≥
(0 = 0 is = (0) = ; solutions of − 1 where = − ( − 1) + − ( − 1), and are orthogonal matrices, and are singular vectors (0) ), and it is one of the 0, respectively. Then, ∈ Ker(− 1 ⎛
(0) ˜−
⎞ ˜(0) − 0 = ⎜⎜⎜⎜⎜ ˜˜(0(00)) ⎟⎟⎟⎟⎟ , with || ||2 = 1.
⎜⎜ − − ⎟⎟ ⎜⎝ ⎟⎠ Computation of cofactors for multivariate part: lifting method Suppose we have () = (− 1) + (). Here, () is a vector generated by homogenious polynomials with total-degree w.r.t. . Then, (+1) is generated as follows. Note that the following consists. − 1(+1) ≡ (0) (+1) = − − 1 0 (mod +2) +1 ∑︁ =1
() (− ) = (). − 1 Now, (+1) and (+1) are transformed bases from 1, . . . , to 1, . . . , and 1, . . . , , respectively, as follows: () = ⎜⎝ ⎛ 1() ⎞
... ⎟ = ˆ(1)1 + . . . + ˆ() , () = ⎜⎝ () ⎠ ⎛ (1) ⎞ . .
. () ⎠ ⎟ = ˆ1 () ()1 + . . . + ˆ .
Then, we obtain ˆ (+1)/ ( = 1, . . . , − 1). Therefore, (+1) is constructed, as (+1) = ˆ follows.
(
() = + ∑︁ ˆ1
()/ 11 + . . . + ∑︁ ˆ(−) 1/ − 1− 1 + F[, ][1,] · ,
=1 =1
where F[, ][1,] = ∪=1F[, ]. To compute the approximate GCD of and , we need to determine
() = (
()() = + ∑︁ ˆ1
()/ 11 + . . . + ∑︁ ˆ(−) 1/ − 1− 1 + () · , =1 =1
To determine the approximate GCD, we must determine (). The following example shows one approach to determining each undetermined element () for 1 ≤ ≤ ..
Example1 Polynomials (, 1, 2) and (, 1, 2) having an approximate GCD (, 1, 2) = 3 + (1 + 2 − 21 + 12) + 3 are expressed as (, 1, 2) = (3 + (22 + 1 + 1 − 2)2 − 1) × (, 1, 2) + , (, 1, 2) = (3 + (222 − 1 + 3)2 − 1) × (, 1, 2) + , where is the machine epsilon.
In this example, = 2 is already known ( = 8). Then, one solution of 1(0) = 0 is = (0) = 8; ⎛ − 0.242535625036333 ⎞ ⎜ − 0.727606875108999 ⎜ − 2.24840273230668 × 10− 15 ⎟⎟ (0) = 8 = ⎜⎜⎜⎜ 0.242535625036333 ⎟⎟⎟⎟ .
⎜⎜⎜⎜ − 00.2.44825503751622550003762363635 ⎟⎟⎟
⎝ − 1.32375311946987 × 10− 15 ⎟⎠
− 0.242535625036333
⎛ ˜(1−) ⎞
⎛ 0.0713340073 · · · 1 + 0.0285336029 · · · 2 ⎞ (
However, assuming that cofactors are also not dense or the approximate GCD is monic,
several coeficients will be zero. In this example, assume the 1st element is zero, (
If the coeficients are dense, lc(lc( ), lc()) or lc(lc(gcd(, ))) should be calculated in advance so that the elements can be determined uniquely. 2.2. Computing approximate GCD After obtaining cofactors, the approximate GCD is computed by solving and (, − 1, . . . , 0) ∈ F[]+1. = ⎛ ˜ − ⎜⎜ ... ⎜⎜ ˜ 0 ⎜ ⎜ ⎝ This linear equation is solve as following step.
(0) 1. Solve +1,+1(˜ ) · (0) = (0). Actually, we utilize the SVD as in the former case. 2. Lifting step: solve (0+)1,+1(˜ ) · () = () − ∑︀ ()+1,+1(˜ ) × (− ). This step can also be solved using SVD. 3. Return + · · · + 0 as an approximate GCD. 3. Solve in ill-conditioned cases In this section, we demonstrate that our method is stable for ill-conditioned cases [8, 5]. On the other word, we deals with cases where the initial factor is an approximate common factor. In this case, the EZ-GCD method is unstable since large cancellation errors occur [6].
Example 2 (initial factors have approximate common factor) Compute the approximate GCD of and , where both polynomials are monic.
(, 1, 2) = (3 + (22 + 1 + 2 − 2)2 − 1)( − 1.0003 + 22 − 12) + , (, 1, 2) = (3 + (222 − 1 + 3)2 − 1)( − 1.0005 + 1 + 2 + 12) + , (, 1, 2) = 3 + (1 + 2 − 21 + 12) + 3.
Initial factors (0) and (0) have an approximate common factor ( − 1.0002) with tolerance (10− 5). Sigular values of 3(0)(, ) are 19.8 > 18.3 > 14.5 > 12.8 > 8.2 > 4.4 > 1.1 > 0.6 ≫ 1.5× 10− 5 ≫ 1.1× 10− 16. Because give polynomials are monic, the leading coeficient of cofactors and the approximate GCD are also monic, respectively.
When = 1, Adjusting the 1st element of (
The perturbation is ||˜ (
− 0.198809763320995761 + 0.033230024235167582
When = 2, by lifting step and adjusting the 1st element of (
The SVD is stable even if the matrix is irregular. Thus, the SVD of (0) is also stable even if initial factors have an approximate common factor. On the other hand, a lifting method using the Bezout matrix is unstable since initial matrix is assumed to be regular [4]. Hence, our method is more stable and eficient than existing methods.