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.

The following is the list of the available commands.

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

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

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

$p≔962592769\;$$\mathrm{vars}≔\left[\mathrm{x1}\,\mathrm{x2}\,\mathrm{x3}\,\mathrm{x4}\right]\:$$R≔\mathrm{PolynomialRing}\left(\mathrm{vars}\,p\right)\:$

$p≔962592769$

$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)\mathbf{mod}p\right)\mathbf{mod}p\:$$\mathrm{tc}≔\mathrm{RandomRegularChainDim0}\left(\mathrm{vars}\,\mathrm{degs}\,p\right)\:$$\mathrm{Equations}\left(\mathrm{tc}\,R\right)\:$

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

$\mathrm{r1}≔446889812$

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

$\mathrm{r2}≔446889812$

$\mathrm{Expand}\left(\mathrm{r1}-\mathrm{r2}\right)\mathbf{mod}p$

$0$

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

$R≔\mathrm{PolynomialRing}\left(\mathrm{vars}\,p\right)\:$

$\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)\mathbf{mod}p\right)\mathbf{mod}p\:$

$\mathrm{q2}≔\mathrm{randpoly}\left(\mathrm{vars}\,\mathrm{dense}\,\mathrm{degree}=\mathrm{dg}\right)+\left(\mathrm{rand}\left(\right)\mathbf{mod}p\right)\mathbf{mod}p\:$

$\mathrm{q3}≔\mathrm{randpoly}\left(\mathrm{vars}\,\mathrm{dense}\,\mathrm{degree}=\mathrm{dg}\right)+\left(\mathrm{rand}\left(\right)\mathbf{mod}p\right)\mathbf{mod}p\:$

$r≔\mathrm{randpoly}\left(\mathrm{vars}\,\mathrm{dense}\,\mathrm{degree}=\mathrm{dg}\right)+\left(\mathrm{rand}\left(\right)\mathbf{mod}p\right)\mathbf{mod}p\:$

$f≔\mathrm{q1}\mathrm{c1}+\mathrm{q2}\mathrm{c2}+\mathrm{q3}\mathrm{c3}+r\:$

$\mathrm{nf1}≔\mathrm{NormalFormDim0}\left(f\,\mathrm{tc}\,R\right)$

$\mathrm{nf1}≔328601399xyz+201896638xy+156935587xz+566967624yz+648149447x+308862802y+921920449z+743421169$

$\mathrm{nf2}≔\mathrm{NormalForm}\left(f\,\mathrm{tc}\,R\right)$

$\mathrm{nf2}≔328601399xyz+201896638xy+156935587xz+566967624yz+648149447x+308862802y+921920449z+743421169$

$\mathrm{nf1}-\mathrm{nf2}\mathbf{mod}p$

$0$

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.