RegularChains[FastArithmeticTools] - Maple Programming Help

Home : Support : Online Help : Mathematics : Factorization and Solving Equations : RegularChains : FastArithmeticTools Subpackage : RegularChains/FastArithmeticTools/SubresultantChainSpecializationCube

RegularChains[FastArithmeticTools]

 SubresultantChainSpecializationCube
 evaluation of the subresultant chain of two polynomials

 Calling Sequence SubresultantChainSpecializationCube(f1, f2, v, R, theoption)

Parameters

 R - polynomial ring f1 - polynomial of R f2 - polynomial of R v - variable of R theoption - integer, choice of two strategies

Description

 • The call SubresultantChainSpecializationCube(f1, f2, v, R, theoption) returns a data-structure which stores images of the subresultant chain of f1 and f2 specialized at enough good values in order to interpolate the subresultants of f1 and f2.
 • f1 and f2 must have main variable v and  $\mathrm{degree}\left(\mathrm{f2},v\right)\le \mathrm{degree}\left(\mathrm{f1},v\right)$ must hold.
 • Moreover 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 must be $e$ such that ${2}^{e}$ divides $p-1$.  If the degree of  f1 or f2 is too large, then an error is raised.
 • This data-structure can be used to compute the resultant of f1 and f2 with respect to v, by means of the command  ResultantBySpecializationCube.
 • This data-structure can also be used to compute a GCD of f1 and f2 modulo the saturated ideal of a regular chain, by means of the command RegularGcdBySpecializationCube.
 • If theoption is $0$ then fast interpolation based on subproduct tree is used. Otherwise a multi-dimensional-FFT-based approach is tried, since it is generally faster and uses less memory. If this latter failed then finally, the subproduct tree technique is used.
 • By good specialization value, one means here a point at which the initials of f1 and f2 do not vanish.
 • The reason why the multi-dimensional-FFT-based specialization scheme can fail is because it is hard in general to find good specialization values that are powers of primitive roots of unity. In some exceptional cases, the subproduct tree approach can also fail finding good specialization values; if this happens an error is raised.

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.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{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.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{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 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}}{+}{{b}}^{{3}}{}{{c}}^{{2}}{}{{d}}^{{2}}{+}{962592768}{}{{b}}^{{2}}{}{{c}}^{{2}}{}{{d}}^{{3}}{+}{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}{}{b}{}{{c}}^{{3}}{}{{d}}^{{2}}{+}{{c}}^{{3}}{}{{d}}^{{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 squarefree.

 > $\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}{+}{{b}}^{{2}}{}{c}{}{d}{+}{962592768}{}{{b}}^{{2}}{}{c}{}{x}{+}{962592768}{}{b}{}{c}{}{{d}}^{{2}}{+}{c}{}{{d}}^{{2}}{}{x}{+}{962592768}{}{{a}}^{{2}}{}{b}{+}{{a}}^{{2}}{}{x}{+}{a}{}{b}{}{c}{+}{a}{}{c}{}{d}{+}{962592767}{}{a}{}{c}{}{x}{+}{962592768}{}{{c}}^{{2}}{}{d}{+}{{c}}^{{2}}{}{x}{,}{\mathrm{regular_chain}}\right]{,}\left[{b}{}{{x}}^{{2}}{+}{962592768}{}{d}{}{{x}}^{{2}}{+}{962592768}{}{a}{}{b}{+}{a}{}{x}{+}{c}{}{d}{+}{962592768}{}{c}{}{x}{,}{\mathrm{regular_chain}}\right]{,}\left[{b}{}{{x}}^{{2}}{+}{962592768}{}{d}{}{{x}}^{{2}}{+}{962592768}{}{a}{}{b}{+}{a}{}{x}{+}{c}{}{d}{+}{962592768}{}{c}{}{x}{,}{\mathrm{regular_chain}}\right]\right]$ (7)