RegularChains[FastArithmeticTools] - Maple Help

Online Help

All Products    Maple    MapleSim


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

RegularChains[FastArithmeticTools]

  

RegularGcdBySpecializationCube

  

regular GCD of two polynomials modulo a regular chain

 

Calling Sequence

Parameters

Description

Examples

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 gi,rci where pi is a polynomial and rci is a regular chain such that the regular chains rci all together form a triangular decomposition of rc in the sense of Lazard, and each polynomial gi 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 degreef2,vdegreef1,v and initf1, initf2 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 2e divides p1.  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

withRegularChains:

withFastArithmeticTools:

withChainTools:

Define a ring of polynomials.

p962592769;varsx,a,b,c,d;RPolynomialRingvars,p

p:=962592769

vars:=x,a,b,c,d

R:=polynomial_ring

(1)

Define two polynomials of R.

f1x2axbmodp

f1:=x2+962592768ax+962592768b

(2)

f2x2cxdmodp

f2:=x2+962592768cx+962592768d

(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

SCubeSubresultantChainSpecializationCubef1,f2,x,R,1

SCube:=subresultant_chain_specialization_cube

(4)

Interpolate the resultant from the SCube

r2ResultantBySpecializationCubef1,f2,x,SCube,R

r2:=a2b3d2+962592768a2b2d3+962592767ab3cd2+2ab2cd3+b3c2d2+962592768b2c2d3+962592768a3b3+a3b2d+2a2b3c+962592767a2b2cd+962592768a2bcd2+a2cd3+962592768ab3c2+ab2c2d+2abc2d2+962592767ac2d3+962592768bc3d2+c3d3+a3bc+962592768a3cd+962592767a2bc2+2a2c2d+abc3+962592768ac3d

(5)

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

rcChainr2,EmptyR,R

rc:=regular_chain

(6)

Compute a regular GCD of f1 and f2 modulo rc

g2RegularGcdBySpecializationCubef1,f2,rc,SCube,R

g2:=962592768ab2d+ab2x+abd2+962592768ad2x+b2cd+962592768b2cx+962592768bcd2+cd2x+962592768a2b+a2x+abc+acd+962592767acx+962592768c2d+c2x,regular_chain,bx2+962592768dx2+962592768ab+ax+cd+962592768cx,regular_chain,bx2+962592768dx2+962592768ab+ax+cd+962592768cx,regular_chain

(7)

See Also

RegularChains

RegularGcd

ResultantBySpecializationCube

SubresultantChainSpecializationCube

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam