RegularGcdBySpecializationCube - Maple Help

# Online Help

###### All Products    Maple    MapleSim

RegularChains[FastArithmeticTools]

 RegularGcdBySpecializationCube
 regular GCD of two polynomials modulo a regular chain

 Calling Sequence RegularGcdBySpecializationCube(f1, f2, rc, SCube, R)

Parameters

 R - polynomial ring f1 - polynomial of R f2 - polynomial of R rc - regular chain SCube - subresultant chain specialization cube

Description

 • The command RegularGcdBySpecializationCube returns a list of pairs ${g}_{i},{\mathrm{rc}}_{i}$ where ${p}_{i}$ is a polynomial and ${\mathrm{rc}}_{i}$ is a regular chain such that the regular chains ${\mathrm{rc}}_{i}$ all together form a triangular decomposition of rc in the sense of Lazard, and each polynomial ${g}_{i}$ is a GCD of f1 and f2 modulo rc_i, for all $i$. See the command RegularGcd for details on this notion of polynomial GCD modulo the saturated ideal of a regular chain.
 • f1 and f2 must have the same main variable v, with $\mathrm{degree}\left(\mathrm{f2},v\right)\le \mathrm{degree}\left(\mathrm{f1},v\right)$ and $\mathrm{init}\left(\mathrm{f1}\right)$, $\mathrm{init}\left(\mathrm{f2}\right)$ both regular w.r.t the saturated ideal of rc.
 • The resultant of f1 and f2 w.r.t. v must be null modulo the saturated ideal of rc.
 • R must have a prime characteristic $p$ such that FFT-based polynomial arithmetic can be used for this actual computation. The higher the degrees of f1 and f2 are, the larger $e$ must be such that ${2}^{e}$ divides $p-1$.  If the degree of f1 or f2 is too large, then an error is raised.
 • The algorithm implemented by the command RegularGcd is more general and does not require the latter two assumptions. However, when both commands can be used the command RegularGcdBySpecializationCube is very likely to outperform RegularGcd, since it relies on modular techniques and asymptotically fast polynomial arithmetic.

Examples

 > $\mathrm{with}\left(\mathrm{RegularChains}\right):$
 > $\mathrm{with}\left(\mathrm{FastArithmeticTools}\right):$
 > $\mathrm{with}\left(\mathrm{ChainTools}\right):$

Define a ring of polynomials.

 > $p≔962592769;$$\mathrm{vars}≔\left[x,a,b,c,d\right];$$R≔\mathrm{PolynomialRing}\left(\mathrm{vars},p\right)$
 ${p}{≔}{962592769}$
 ${\mathrm{vars}}{≔}\left[{x}{,}{a}{,}{b}{,}{c}{,}{d}\right]$
 ${R}{≔}{\mathrm{polynomial_ring}}$ (1)

Define two polynomials of R.

 > $\mathrm{f1}≔\left({x}^{2}-a\right)\left(x-b\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p$
 ${\mathrm{f1}}{≔}\left({{x}}^{{2}}{+}{962592768}{}{a}\right){}\left({x}{+}{962592768}{}{b}\right)$ (2)
 > $\mathrm{f2}≔\left({x}^{2}-c\right)\left(x-d\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p$
 ${\mathrm{f2}}{≔}\left({{x}}^{{2}}{+}{962592768}{}{c}\right){}\left({x}{+}{962592768}{}{d}\right)$ (3)

Compute images of the subresultant chain of sufficiently many points in order to interpolate. Multi-dimensional TFT (Truncated Fourier Transform) is used to evaluate and interpolate since 1 is passed as fifth argument

 > $\mathrm{SCube}≔\mathrm{SubresultantChainSpecializationCube}\left(\mathrm{f1},\mathrm{f2},x,R,1\right)$
 ${\mathrm{SCube}}{≔}{\mathrm{subresultant_chain_specialization_cube}}$ (4)

Interpolate the resultant from the SCube

 > $\mathrm{r2}≔\mathrm{ResultantBySpecializationCube}\left(\mathrm{f1},\mathrm{f2},x,\mathrm{SCube},R\right)$
 ${\mathrm{r2}}{≔}{{a}}^{{2}}{}{{b}}^{{3}}{}{{d}}^{{2}}{+}{962592768}{}{{a}}^{{2}}{}{{b}}^{{2}}{}{{d}}^{{3}}{+}{962592767}{}{a}{}{{b}}^{{3}}{}{c}{}{{d}}^{{2}}{+}{2}{}{a}{}{{b}}^{{2}}{}{c}{}{{d}}^{{3}}{+}{{d}}^{{2}}{}{{c}}^{{2}}{}{{b}}^{{3}}{+}{962592768}{}{{d}}^{{3}}{}{{c}}^{{2}}{}{{b}}^{{2}}{+}{962592768}{}{{a}}^{{3}}{}{{b}}^{{3}}{+}{{a}}^{{3}}{}{{b}}^{{2}}{}{d}{+}{2}{}{{a}}^{{2}}{}{{b}}^{{3}}{}{c}{+}{962592767}{}{{a}}^{{2}}{}{{b}}^{{2}}{}{c}{}{d}{+}{962592768}{}{{a}}^{{2}}{}{b}{}{c}{}{{d}}^{{2}}{+}{{a}}^{{2}}{}{c}{}{{d}}^{{3}}{+}{962592768}{}{a}{}{{b}}^{{3}}{}{{c}}^{{2}}{+}{a}{}{{b}}^{{2}}{}{{c}}^{{2}}{}{d}{+}{2}{}{a}{}{b}{}{{c}}^{{2}}{}{{d}}^{{2}}{+}{962592767}{}{a}{}{{c}}^{{2}}{}{{d}}^{{3}}{+}{962592768}{}{{d}}^{{2}}{}{{c}}^{{3}}{}{b}{+}{{d}}^{{3}}{}{{c}}^{{3}}{+}{{a}}^{{3}}{}{b}{}{c}{+}{962592768}{}{{a}}^{{3}}{}{c}{}{d}{+}{962592767}{}{{a}}^{{2}}{}{b}{}{{c}}^{{2}}{+}{2}{}{{a}}^{{2}}{}{{c}}^{{2}}{}{d}{+}{a}{}{b}{}{{c}}^{{3}}{+}{962592768}{}{a}{}{{c}}^{{3}}{}{d}$ (5)

Define a regular chain with r2. Note that r2 is not required to be square free.

 > $\mathrm{rc}≔\mathrm{Chain}\left(\left[\mathrm{r2}\right],\mathrm{Empty}\left(R\right),R\right)$
 ${\mathrm{rc}}{≔}{\mathrm{regular_chain}}$ (6)

Compute a regular GCD of f1 and f2 modulo rc

 > $\mathrm{g2}≔\mathrm{RegularGcdBySpecializationCube}\left(\mathrm{f1},\mathrm{f2},\mathrm{rc},\mathrm{SCube},R\right)$
 ${\mathrm{g2}}{≔}\left[\left[{962592768}{}{a}{}{{b}}^{{2}}{}{d}{+}{a}{}{{b}}^{{2}}{}{x}{+}{a}{}{b}{}{{d}}^{{2}}{+}{962592768}{}{a}{}{{d}}^{{2}}{}{x}{+}{c}{}{d}{}{{b}}^{{2}}{+}{962592768}{}{{b}}^{{2}}{}{c}{}{x}{+}{962592768}{}{{d}}^{{2}}{}{c}{}{b}{+}{c}{}{{d}}^{{2}}{}{x}{+}{962592768}{}{b}{}{{a}}^{{2}}{+}{{a}}^{{2}}{}{x}{+}{a}{}{b}{}{c}{+}{a}{}{c}{}{d}{+}{962592767}{}{a}{}{c}{}{x}{+}{962592768}{}{d}{}{{c}}^{{2}}{+}{{c}}^{{2}}{}{x}{,}{\mathrm{regular_chain}}\right]{,}\left[{{x}}^{{2}}{}{b}{+}{962592768}{}{{x}}^{{2}}{}{d}{+}{962592768}{}{a}{}{b}{+}{x}{}{a}{+}{c}{}{d}{+}{962592768}{}{x}{}{c}{,}{\mathrm{regular_chain}}\right]{,}\left[{{x}}^{{2}}{}{b}{+}{962592768}{}{{x}}^{{2}}{}{d}{+}{962592768}{}{a}{}{b}{+}{x}{}{a}{+}{c}{}{d}{+}{962592768}{}{x}{}{c}{,}{\mathrm{regular_chain}}\right]\right]$ (7)

 See Also