Returns a list of pairs $f_i,{\mathrm{rc}}_i$ where $f_i$ is a polynomial and ${\mathrm{rc}}_i$ is a regular chain such that the regular chains ${\mathrm{rc}}_i$ form a triangular decomposition of rc in the sense of Kalkbrener, each polynomial $f_i$ is equal to f modulo the saturated ideal of ${\mathrm{rc}}_i$, for all $i$, and  each  polynomial $f_i$ is either zero or invertible modulo the saturated ideal of ${\mathrm{rc}}_i$, for all $i$.

The above specification is similar to that of the command Regularize. However the algorithm of the command RegularizeDim0 makes use of modular techniques and asymptotically fast polynomial arithmetic. Consequently, when both commands apply, the latter one often outperforms the former.

The function call RegularizeDim0(p, rc, R) makes two other assumptions. First rc must be a zero-dimensional regular chain. See the RegularChains package and its subpackage ChainTools for these notions.

Secondly, R must have a prime characteristic $p$ such that FFT-based polynomial arithmetic can be used for this computation. The higher the degrees of f and rc are, the larger $e$ must be, such that $2^e$ divides $p-1$.  If the degree of  f or rc is too large, then an error is raised.

If isSquareFree is true then assume that rc is a square-free regular chain, that is, its saturated ideal is radical.

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

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

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

$p≔962592769\:$

$\mathrm{vars}≔\left[\mathrm{x1}\,\mathrm{x2}\,\mathrm{x3}\,\mathrm{x4}\right]\:$

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

$N≔\mathrm{nops}\left(\mathrm{vars}\right)\:$

$d≔5\:$

$\mathrm{degrees}≔\left[3\,4\,5\,8\right]\:$

$\mathrm{rc}≔\mathrm{RandomRegularChainDim0}\left(\mathrm{vars}\,\mathrm{degrees}\,p\right)\:$

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

$t≔\mathrm{time}\left(\right)\:$

$\mathrm{res1}≔\mathrm{RegularizeDim0}\left(p\,\mathrm{rc}\,R\right)$

$\mathrm{res1}≔\left[\left[71{\mathrm{x1}}^2{\mathrm{x2}}^3+16{\mathrm{x1}}^2{\mathrm{x2}}^2\mathrm{x3}+83{\mathrm{x1}}^2{\mathrm{x2}}^2\mathrm{x4}+962592709{\mathrm{x1}}^2\mathrm{x2}{\mathrm{x3}}^2+962592686{\mathrm{x1}}^2\mathrm{x2}\mathrm{x3}\mathrm{x4}+962592721{\mathrm{x1}}^2\mathrm{x2}{\mathrm{x4}}^2+37{\mathrm{x1}}^2{\mathrm{x3}}^3+5{\mathrm{x1}}^2{\mathrm{x3}}^2\mathrm{x4}+962592752{\mathrm{x1}}^2\mathrm{x3}{\mathrm{x4}}^2+962592709\mathrm{x1}{\mathrm{x2}}^3\mathrm{x3}+962592735\mathrm{x1}{\mathrm{x2}}^3\mathrm{x4}+44\mathrm{x1}{\mathrm{x2}}^2{\mathrm{x3}}^2+962592767\mathrm{x1}{\mathrm{x2}}^2\mathrm{x3}\mathrm{x4}+962592722\mathrm{x1}{\mathrm{x2}}^2{\mathrm{x4}}^2+962592697\mathrm{x1}\mathrm{x2}{\mathrm{x3}}^3+962592672\mathrm{x1}\mathrm{x2}{\mathrm{x3}}^2\mathrm{x4}+10\mathrm{x1}\mathrm{x2}\mathrm{x3}{\mathrm{x4}}^2+65\mathrm{x1}\mathrm{x2}{\mathrm{x4}}^3+50\mathrm{x1}{\mathrm{x3}}^4+962592709\mathrm{x1}{\mathrm{x3}}^3\mathrm{x4}+7\mathrm{x1}{\mathrm{x3}}^2{\mathrm{x4}}^2+34\mathrm{x1}\mathrm{x3}{\mathrm{x4}}^3+52\mathrm{x1}{\mathrm{x4}}^4+962592736{\mathrm{x2}}^3{\mathrm{x3}}^2+21{\mathrm{x2}}^3\mathrm{x3}\mathrm{x4}+97{\mathrm{x2}}^3{\mathrm{x4}}^2+89{\mathrm{x2}}^2{\mathrm{x3}}^3+962592753{\mathrm{x2}}^2{\mathrm{x3}}^2\mathrm{x4}+962592700{\mathrm{x2}}^2\mathrm{x3}{\mathrm{x4}}^2+87{\mathrm{x2}}^2{\mathrm{x4}}^3+\mathrm{x2}{\mathrm{x3}}^4+962592759\mathrm{x2}{\mathrm{x3}}^3\mathrm{x4}+962592684\mathrm{x2}{\mathrm{x3}}^2{\mathrm{x4}}^2+18\mathrm{x2}\mathrm{x3}{\mathrm{x4}}^3+962592747\mathrm{x2}{\mathrm{x4}}^4+962592722{\mathrm{x3}}^4\mathrm{x4}+962592767{\mathrm{x3}}^3{\mathrm{x4}}^2+31{\mathrm{x3}}^2{\mathrm{x4}}^3+10\mathrm{x3}{\mathrm{x4}}^4+962592720{\mathrm{x4}}^5+962578812{\mathrm{x1}}^2{\mathrm{x2}}^2+9381{\mathrm{x1}}^2\mathrm{x2}\mathrm{x3}+556{\mathrm{x1}}^2\mathrm{x2}\mathrm{x4}+962589820{\mathrm{x1}}^2{\mathrm{x3}}^2+5964{\mathrm{x1}}^2\mathrm{x3}\mathrm{x4}+962589337{\mathrm{x1}}^2{\mathrm{x4}}^2+892\mathrm{x1}{\mathrm{x2}}^3+962585240\mathrm{x1}{\mathrm{x2}}^2\mathrm{x3}+19070\mathrm{x1}{\mathrm{x2}}^2\mathrm{x4}+4231\mathrm{x1}\mathrm{x2}{\mathrm{x3}}^2+962589948\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}+962590124\mathrm{x1}\mathrm{x2}{\mathrm{x4}}^2+962590330\mathrm{x1}{\mathrm{x3}}^3+1110\mathrm{x1}{\mathrm{x3}}^2\mathrm{x4}+90\mathrm{x1}\mathrm{x3}{\mathrm{x4}}^2+962591972\mathrm{x1}{\mathrm{x4}}^3+15464{\mathrm{x2}}^3\mathrm{x3}+5768{\mathrm{x2}}^3\mathrm{x4}+962587427{\mathrm{x2}}^2{\mathrm{x3}}^2+962589589{\mathrm{x2}}^2\mathrm{x3}\mathrm{x4}+962588964{\mathrm{x2}}^2{\mathrm{x4}}^2+962588730\mathrm{x2}{\mathrm{x3}}^3+962591904\mathrm{x2}{\mathrm{x3}}^2\mathrm{x4}+962589463\mathrm{x2}\mathrm{x3}{\mathrm{x4}}^2+962588440\mathrm{x2}{\mathrm{x4}}^3+2863{\mathrm{x3}}^4+962583397{\mathrm{x3}}^3\mathrm{x4}+8218{\mathrm{x3}}^2{\mathrm{x4}}^2+962587139\mathrm{x3}{\mathrm{x4}}^3+962591933{\mathrm{x4}}^4+962099056{\mathrm{x1}}^2\mathrm{x2}+513519{\mathrm{x1}}^2\mathrm{x3}+961688036{\mathrm{x1}}^2\mathrm{x4}+531043\mathrm{x1}{\mathrm{x2}}^2+962353937\mathrm{x1}\mathrm{x2}\mathrm{x3}+451667\mathrm{x1}\mathrm{x2}\mathrm{x4}+21178\mathrm{x1}{\mathrm{x3}}^2+962093493\mathrm{x1}\mathrm{x3}\mathrm{x4}+361086\mathrm{x1}{\mathrm{x4}}^2+961732889{\mathrm{x2}}^3+513650{\mathrm{x2}}^2\mathrm{x3}+961839250{\mathrm{x2}}^2\mathrm{x4}+277009\mathrm{x2}{\mathrm{x3}}^2+962427116\mathrm{x2}\mathrm{x3}\mathrm{x4}+275697\mathrm{x2}{\mathrm{x4}}^2+962387348{\mathrm{x3}}^3+383270{\mathrm{x3}}^2\mathrm{x4}+962280827\mathrm{x3}{\mathrm{x4}}^2+291891{\mathrm{x4}}^3+871332243{\mathrm{x1}}^2+929352501\mathrm{x1}\mathrm{x2}+707150581\mathrm{x1}\mathrm{x3}+343331851\mathrm{x1}\mathrm{x4}+40519050{\mathrm{x2}}^2+128018783\mathrm{x2}\mathrm{x3}+726074106\mathrm{x2}\mathrm{x4}+960581285{\mathrm{x3}}^2+181853712\mathrm{x3}\mathrm{x4}+678057550{\mathrm{x4}}^2+267999103\mathrm{x1}+261080429\mathrm{x2}+747627767\mathrm{x3}+576065319\mathrm{x4}+549411107\,\mathrm{regular\_chain}\right]\right]$

$\mathrm{time}\left(\right)-t$

$0.760$

$t≔\mathrm{time}\left(\right)\:$

$\mathrm{res2}≔\mathrm{Regularize}\left(p\,\mathrm{rc}\,R\right)$

$\mathrm{res2}≔\left[\left[\mathrm{rc}\right]\,\left[\right]\right]$

$\mathrm{time}\left(\right)-t$

$20.997$

$\mathrm{EqualSaturatedIdeals}\left(\mathrm{res1}\left[1\right]\left[2\right]\,\mathrm{res2}\left[1\right]\left[1\right]\,R\right)$

$\mathrm{true}$

$\mathrm{NormalForm}\left(\mathrm{res1}\left[1\right]\left[1\right]-p\,\mathrm{res2}\left[1\right]\left[1\right]\,R\right)$

$0$

$\mathrm{NormalFormDim0}\left(\mathrm{res1}\left[1\right]\left[1\right]-p\,\mathrm{res2}\left[1\right]\left[1\right]\,R\right)$

$0$