 Overview of the RegularChains[FastArithmeticTools] Subpackage of RegularChains - Maple Programming Help

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

Overview of the RegularChains[FastArithmeticTools] Subpackage of RegularChains

 Calling Sequence RegularChains[FastArithmeticTools][command](arguments) command(arguments)

Description

 • The RegularChains[FastArithmeticTools] subpackage contains a collection of commands for computing with regular chains in prime characteristic using asymptotically fast algorithms.
 • Most of the commands of this package implements core operations on regular chains such as regularity test and polynomial GCD modulo a regular chain. However, these commands have several constraints. On top of the characteristic issue (mentioned above) the current regular chain must have dimension zero or one. There is only one exception: the command RegularGcdBySpecializationCube which makes no assumption on dimension.
 • In order to call one of the commands of this subpackage the characteristic of the polynomial ring must be a prime number p satisfying the following properties. First, it should not be greater than 962592769. Secondly, the number p-1 should be divisible by a sufficiently large power of 2. 2^20 is often sufficient. The best prime number p under these constraints is $469762049$ for which p-1 writes 2^26 * 7.  If this power of 2 is not large enough, then a clean error is returned.
 • The commands IteratedResultantDim0 and IteratedResultantDim1 compute the iterated resultant of a polynomial w.r.t. a regular chain of dimension 0 and 1, respectively.
 • The commands NormalFormDim0 and ReduceCoefficientsDim0 compute the normal form of a polynomial w.r.t. a zero-dimensional regular chain.
 • The commands NormalizePolynomialDim0 and NormalizeRegularChainDim0 normalize a polynomial (w.r.t. a zero-dimensional regular chain) and a regular chain (w.r.t. itself).
 • The commands RandomRegularChainDim0 and RandomRegularChainDim1 compute random regular chains of given degrees.
 • The command RegularizeDim0 tests whether a polynomial is invertible modulo a zero-dimensional regular chain.
 • The commands RegularGcdBySpecializationCube, ResultantBySpecializationCube and SubresultantChainSpecializationCube compute resultants and polynomial GCDs modulo a regular chain using fast evaluation and interpolation.

List of RegularChains[FastArithmeticTools] Subpackage Commands

 The following is the list of the available commands.

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[\mathrm{x1},\mathrm{x2},\mathrm{x3},\mathrm{x4}\right]:$$R≔\mathrm{PolynomialRing}\left(\mathrm{vars},p\right):$
 ${p}{≔}{962592769}$ (1)

Randomly generating (dense) regular chain and polynomial

 > $N≔\mathrm{nops}\left(\mathrm{vars}\right):$$\mathrm{dg}≔3:$$\mathrm{degs}≔\left[\mathrm{seq}\left(4,i=1..N\right)\right]:$$\mathrm{pol}≔\mathrm{randpoly}\left(\mathrm{vars},\mathrm{dense},\mathrm{degree}=\mathrm{dg}\right)+\left(\mathrm{rand}\left(\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p:$$\mathrm{tc}≔\mathrm{RandomRegularChainDim0}\left(\mathrm{vars},\mathrm{degs},p\right):$$\mathrm{Equations}\left(\mathrm{tc},R\right):$

Compute the iterated resultant of pol w.r.t. tc

 > $\mathrm{r1}≔\mathrm{IteratedResultantDim0}\left(\mathrm{pol},\mathrm{tc},R\right)$
 ${\mathrm{r1}}{≔}{446889812}$ (2)

Compare with the generic algorithm (non-fast and non-modular algorithm) of the command IteratedResultant.

 > $\mathrm{r2}≔\mathrm{IteratedResultant}\left(\mathrm{pol},\mathrm{tc},R\right)$
 ${\mathrm{r2}}{≔}{446889812}$ (3)

The results computed IteratedResultantDim0 and IteratedResultant are equivalent.

 > $\mathrm{Expand}\left(\mathrm{r1}-\mathrm{r2}\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p$
 ${0}$ (4)

Define another ring of polynomials.

 > $p≔962592769:$$\mathrm{vars}≔\left[x,y,z\right]:$$N≔\mathrm{nops}\left(\mathrm{vars}\right):$
 > $R≔\mathrm{PolynomialRing}\left(\mathrm{vars},p\right):$

Generate a regular chain and a random polynomial.

 > $\mathrm{c1}≔{z}^{2}+286748183z+134705551:$
 > $\mathrm{c2}≔{y}^{2}+914706789yz+686506773y+823875308z+417988453:$
 > $\mathrm{c3}≔{x}^{2}+224047618xyz+197329999xy+838274835xz+792563861x+600038529yz+434770098y+251400283z+918968185:$
 > $\mathrm{lf}≔\left[\mathrm{c1},\mathrm{c2},\mathrm{c3}\right]:$
 > $\mathrm{tc}≔\mathrm{Chain}\left(\mathrm{lf},\mathrm{Empty}\left(R\right),R\right):$
 > $\mathrm{lf}≔\left[x+\mathrm{c1}\mathrm{c2}\mathrm{c3},\left(\mathrm{c1}-\mathrm{c2}\right)\left(\mathrm{c1}-\mathrm{c3}\right),1+\mathrm{c1}\left(\mathrm{c2}-\mathrm{c3}\right)\right]:$
 > $\mathrm{dg}≔10:$
 > $\mathrm{q1}≔\mathrm{randpoly}\left(\mathrm{vars},\mathrm{dense},\mathrm{degree}=\mathrm{dg}\right)+\left(\mathrm{rand}\left(\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p:$
 > $\mathrm{q2}≔\mathrm{randpoly}\left(\mathrm{vars},\mathrm{dense},\mathrm{degree}=\mathrm{dg}\right)+\left(\mathrm{rand}\left(\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p:$
 > $\mathrm{q3}≔\mathrm{randpoly}\left(\mathrm{vars},\mathrm{dense},\mathrm{degree}=\mathrm{dg}\right)+\left(\mathrm{rand}\left(\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p:$
 > $r≔\mathrm{randpoly}\left(\mathrm{vars},\mathrm{dense},\mathrm{degree}=\mathrm{dg}\right)+\left(\mathrm{rand}\left(\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p:$
 > $f≔\mathrm{q1}\mathrm{c1}+\mathrm{q2}\mathrm{c2}+\mathrm{q3}\mathrm{c3}+r:$

Compute the normal form of f.

 > $\mathrm{nf1}≔\mathrm{NormalFormDim0}\left(f,\mathrm{tc},R\right)$
 ${\mathrm{nf1}}{≔}{328601399}{}{x}{}{y}{}{z}{+}{201896638}{}{x}{}{y}{+}{156935587}{}{x}{}{z}{+}{566967624}{}{y}{}{z}{+}{648149447}{}{x}{+}{308862802}{}{y}{+}{921920449}{}{z}{+}{743421169}$ (5)

Compare with the generic algorithm (non-fast and non-modular algorithm) of the command NormalForm.

 > $\mathrm{nf2}≔\mathrm{NormalForm}\left(f,\mathrm{tc},R\right)$
 ${\mathrm{nf2}}{≔}{328601399}{}{x}{}{y}{}{z}{+}{201896638}{}{x}{}{y}{+}{156935587}{}{x}{}{z}{+}{566967624}{}{y}{}{z}{+}{648149447}{}{x}{+}{308862802}{}{y}{+}{921920449}{}{z}{+}{743421169}$ (6)

The results computed by NormalFormDim0 and NormalForm are equivalent.

 > $\mathrm{nf1}-\mathrm{nf2}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p$
 ${0}$ (7)

References

 X. Li and M. Moreno Maza. "Efficient implementation of polynomial arithmetic in a multilevel programming environment." Proc. International Congress of Mathematical Software, p.12-23, LNCS Vol.4151, Springer, 2006.
 X. Li, M. Moreno Maza and E. Schost. "Fast arithmetic for triangular sets: from theory to practice." ISSAC'2007, ACM Press. p.269-276, 2007.
 X. Li and M. Moreno Maza. "Multithreaded parallel implementation of arithmetic operations modulo a triangular set." PASCO'2007, ACM Press, p.53-59, 2007.
 A. Filatei, X. Li, M. Moreno Maza and E. Schost. "Implementation techniques for fast polynomial arithmetic in a high-level programming environment." ISSAC'2006, p.93-100, ACM Press, 2006.
 X. Li, M. Moreno Maza, R. Rasheed and E. Schost. "High-Performance Symbolic Computation in a Hybrid Compiled-Interpreted Programming Environment." Proc. 2008 International Conference on Computational Science and Applications, IEEE Computer Society, pp 331--341 2008.
 X. Li, M. Moreno Maza, R. Rasheed and E. Schost. "The Modpn library: Bringing fast polynomial arithmetic into Maple." Proc. 2008 Milestones in Computer Algebra, Stonehaven Bay, Trinidad and Tobago, 2008.
 X. Li, M. Moreno Maza and W. Pan. "Computations modulo regular chains." Technical Report, University of Western Ontario, 2009.