RegularChains[FastArithmeticTools] - Maple Programming Help

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

RegularChains[FastArithmeticTools]

 BivariateModularTriangularize
 triangular decomposition of a bivariate square system by a modular method

 Calling Sequence BivariateModularTriangularize(F, R)

Parameters

 R - polynomial ring F - bivariate square system of R

Description

 • The command BivariateModularTriangularize(F, R) returns a triangular decomposition of F in R. See the command Triangularize and the page RegularChains for the concept of a triangular decomposition.
 • F consists of two bivariate polynomials f1 and f2 of R. No other assumptions are required.
 • R must have only two variables and no parameters.
 • Moreover 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 must be $e$ such that ${2}^{e}$ divides $p-1$.  If the degree of  f1 or f2 is too large, then an error is raised.
 • The algorithm is deterministic (i.e. non-probabilistic) and uses modular techniques together with asymptotically fast polynomial arithmetic.
 • When both Triangularize and BivariateModularTriangularize apply, the latter command is very likely to outperform the former one.

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≔469762049;$$\mathrm{vars}≔\left[x,y\right];$$R≔\mathrm{PolynomialRing}\left(\mathrm{vars},p\right)$
 ${p}{≔}{469762049}$
 ${\mathrm{vars}}{≔}\left[{x}{,}{y}\right]$
 ${R}{≔}{\mathrm{polynomial_ring}}$ (1)

Define two polynomials of R.

 > $\mathrm{f1}≔{x}^{49}+y+1$
 ${\mathrm{f1}}{≔}{{x}}^{{49}}{+}{y}{+}{1}$ (2)
 > $\mathrm{f2}≔x+{y}^{41}+1$
 ${\mathrm{f2}}{≔}{{y}}^{{41}}{+}{x}{+}{1}$ (3)

Compute a triangular decomposition of this system

 > $\mathrm{dec}≔\mathrm{BivariateModularTriangularize}\left(\left[\mathrm{f1},\mathrm{f2}\right],R\right)$
 ${\mathrm{dec}}{≔}\left[{\mathrm{regular_chain}}\right]$ (4)
 > $\mathrm{map}\left(\mathrm{Equations},\mathrm{dec},R\right)$
 $\left[\left[{x}{+}{{y}}^{{41}}{+}{1}{,}{{y}}^{{2009}}{+}{49}{}{{y}}^{{1968}}{+}{1176}{}{{y}}^{{1927}}{+}{18424}{}{{y}}^{{1886}}{+}{211876}{}{{y}}^{{1845}}{+}{1906884}{}{{y}}^{{1804}}{+}{13983816}{}{{y}}^{{1763}}{+}{85900584}{}{{y}}^{{1722}}{+}{450978066}{}{{y}}^{{1681}}{+}{175407438}{}{{y}}^{{1640}}{+}{231867703}{}{{y}}^{{1599}}{+}{10669226}{}{{y}}^{{1558}}{+}{190373232}{}{{y}}^{{1517}}{+}{469560422}{}{{y}}^{{1476}}{+}{200808123}{}{{y}}^{{1435}}{+}{468552287}{}{{y}}^{{1394}}{+}{114869768}{}{{y}}^{{1353}}{+}{112450244}{}{{y}}^{{1312}}{+}{460890461}{}{{y}}^{{1271}}{+}{133871214}{}{{y}}^{{1230}}{+}{200806821}{}{{y}}^{{1189}}{+}{8869201}{}{{y}}^{{1148}}{+}{11288074}{}{{y}}^{{1107}}{+}{319617771}{}{{y}}^{{1066}}{+}{228812073}{}{{y}}^{{1025}}{+}{228812073}{}{{y}}^{{984}}{+}{319617771}{}{{y}}^{{943}}{+}{11288074}{}{{y}}^{{902}}{+}{8869201}{}{{y}}^{{861}}{+}{200806821}{}{{y}}^{{820}}{+}{133871214}{}{{y}}^{{779}}{+}{460890461}{}{{y}}^{{738}}{+}{112450244}{}{{y}}^{{697}}{+}{114869768}{}{{y}}^{{656}}{+}{468552287}{}{{y}}^{{615}}{+}{200808123}{}{{y}}^{{574}}{+}{469560422}{}{{y}}^{{533}}{+}{190373232}{}{{y}}^{{492}}{+}{10669226}{}{{y}}^{{451}}{+}{231867703}{}{{y}}^{{410}}{+}{175407438}{}{{y}}^{{369}}{+}{450978066}{}{{y}}^{{328}}{+}{85900584}{}{{y}}^{{287}}{+}{13983816}{}{{y}}^{{246}}{+}{1906884}{}{{y}}^{{205}}{+}{211876}{}{{y}}^{{164}}{+}{18424}{}{{y}}^{{123}}{+}{1176}{}{{y}}^{{82}}{+}{49}{}{{y}}^{{41}}{+}{469762048}{}{y}\right]\right]$ (5)

Check the number of solutions

 > $\mathrm{map}\left(\mathrm{NumberOfSolutions},\mathrm{dec},R\right)$
 $\left[{2009}\right]$ (6)