RegularizeDim0 - Maple Help

# Online Help

###### All Products    Maple    MapleSim

RegularChains[FastArithmeticTools]

 RegularizeDim0
 Test the regularity of a polynomial w.r.t. a 0-dim regular chain

 Calling Sequence RegularizeDim0(f, rc, R) RegularizeDim0(f, rc, R, isSquareFree)

Parameters

 R - a polynomial ring f - a polynomial of R rc - a regular chain of R isSquareFree - boolean value (optional)

Description

 • 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 squarefree regular chain, that is, its saturated ideal is radical.

Examples

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

p is a large prime number

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

Define a random dense regular chain and a polynomial

 > $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)\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:$
 > $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]$ (1)
 > $\mathrm{time}\left(\right)-t$
 ${0.760}$ (2)

We can see that Regularize is slower than RegularizeDim0.

 > $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]$ (3)
 > $\mathrm{time}\left(\right)-t$
 ${20.997}$ (4)

These additional calculations show that the two returned regular chains are equivalent (i.e. they have the same saturated ideals).

 > $\mathrm{EqualSaturatedIdeals}\left(\mathrm{res1}\left[1\right]\left[2\right],\mathrm{res2}\left[1\right]\left[1\right],R\right)$
 ${\mathrm{true}}$ (5)
 > $\mathrm{NormalForm}\left(\mathrm{res1}\left[1\right]\left[1\right]-p,\mathrm{res2}\left[1\right]\left[1\right],R\right)$
 ${0}$ (6)
 > $\mathrm{NormalFormDim0}\left(\mathrm{res1}\left[1\right]\left[1\right]-p,\mathrm{res2}\left[1\right]\left[1\right],R\right)$
 ${0}$ (7)

 See Also