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

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

Overview of the RegularChains[MatrixTools] Subpackage

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

Description

 • The RegularChains[MatrixTools] subpackage is a collection of commands to manipulate matrices of polynomials modulo regular chains.
 • The commands of the RegularChains[MatrixTools] subpackage are quite standard in terms of their goals: multiplication of matrices, computation of inverse, or lower echelon of a matrix. However, these commands are considered here in a non-standard context. Indeed, the coefficients of these matrices are polynomials and the computations are performed modulo (the saturated ideal of) a regular chain.
 • The saturated ideal of a regular chain is not necessarily prime and working modulo such ideals may involve zero-divisors. However, computing with these zero-divisors is possible following the celebrated D5 Principle, after J. Della Dora, C. Discrescenzo, and D. Duval. The idea is the following. When a zero-divisor is encountered during a computation modulo a regular chain, you can split the computations into several cases (or branches) such that in each case this zero-divisor becomes either zero or a regular element (that is, an element that is not a zero-divisor). Therefore, this zero-divisor is not an obstacle for the computations in any of these branches.
 • The main purpose of the commands of the RegularChains[MatrixTools] subpackage is to compute the inverse of the Jacobian matrix of a polynomial systems modulo (the saturated ideal of) a regular chain. This question arises, for example, in Hensel lifting techniques for triangular sets. See the paper Degree bounds and lifting techniques for triangular sets by E. Schost.

List of RegularChains[MatrixTools] Subpackage Commands

 The following is a list of available commands.

Examples

 > $\mathrm{with}\left(\mathrm{RegularChains}\right):$
 > $\mathrm{with}\left(\mathrm{LinearAlgebra}\right):$$\mathrm{with}\left(\mathrm{MatrixTools}\right);$$\mathrm{with}\left(\mathrm{ChainTools}\right):$
 $\left[{\mathrm{IsZeroMatrix}}{,}{\mathrm{JacobianMatrix}}{,}{\mathrm{LowerEchelonForm}}{,}{\mathrm{MatrixInverse}}{,}{\mathrm{MatrixMultiply}}{,}{\mathrm{MatrixOverChain}}\right]$ (1)

Consider the following polynomial ring.

 > $R≔\mathrm{PolynomialRing}\left(\left[x,y,z\right],101\right)$
 ${R}{:=}{\mathrm{polynomial_ring}}$ (2)

Define a regular chain T with a saturated ideal that is clearly non-prime.

 > $E≔\mathrm{Empty}\left(R\right):$
 > $T≔\mathrm{Chain}\left(\left[\left(z+1\right)\left(z+2\right),{y}^{2}+z,\left(x-z\right)\left(x-y\right)\right],E,R\right)$
 ${T}{:=}{\mathrm{regular_chain}}$ (3)
 > $\mathrm{Equations}\left(T,R\right)$
 $\left[{{x}}^{{2}}{+}\left({100}{}{y}{+}{100}{}{z}\right){}{x}{+}{z}{}{y}{,}{{y}}^{{2}}{+}{z}{,}{{z}}^{{2}}{+}{3}{}{z}{+}{2}\right]$ (4)

Since T possesses as many variables as polynomials, the saturated ideal of T is the ideal generated by T. Clearly, the following numbers are zero-divisors modulo this ideal: z+1, z+2, x-z, x-y, and also y-1 and y+1. Observe that if the command ListConstruct is used instead of Chain, then this ideal splits into four.

 > $\mathrm{split}≔\mathrm{ListConstruct}\left(\left[\left(z+1\right)\left(z+2\right),{y}^{2}+z,\left(x-z\right)\left(x-y\right)\right],E,R\right)$
 ${\mathrm{split}}{:=}\left[{\mathrm{regular_chain}}{,}{\mathrm{regular_chain}}{,}{\mathrm{regular_chain}}{,}{\mathrm{regular_chain}}\right]$ (5)
 > $\mathrm{map}\left(\mathrm{Equations},\mathrm{split},R\right)$
 $\left[\left[{x}{+}{1}{,}{y}{+}{1}{,}{z}{+}{1}\right]{,}\left[{x}{+}{1}{,}{y}{+}{100}{,}{z}{+}{1}\right]{,}\left[{x}{+}{100}{,}{y}{+}{100}{,}{z}{+}{1}\right]{,}\left[{{x}}^{{2}}{+}\left({100}{}{y}{+}{2}\right){}{x}{+}{99}{}{y}{,}{{y}}^{{2}}{+}{99}{,}{z}{+}{2}\right]\right]$ (6)

Now construct a random matrix with coefficients in R.

 > $m≔\mathrm{Matrix}\left(\left[\left[87{z}^{2}-56z,-73-62{z}^{2}+97z,-10-4{z}^{2}-83z,80+62{z}^{2}-82z\right],\left[-44z+71,-17z-75,-10z-7,-40z+42\right],\left[-92-50{z}^{3}+23{z}^{2}+75z,37+6{z}^{3}+74{z}^{2}+72z,29-23{z}^{3}+87{z}^{2}+44z,-61+98{z}^{3}-23{z}^{2}+10z\right],\left[11-8{z}^{3}-29{z}^{2}+95z,-81-49{z}^{3}-47{z}^{2}+40z,31+91{z}^{3}+68{z}^{2}-10z,1-51{z}^{3}+77{z}^{2}+95z\right]\right]\right)$
 ${m}{:=}\left[\begin{array}{cccc}{87}{}{{z}}^{{2}}{-}{56}{}{z}& {-}{62}{}{{z}}^{{2}}{+}{97}{}{z}{-}{73}& {-}{4}{}{{z}}^{{2}}{-}{83}{}{z}{-}{10}& {62}{}{{z}}^{{2}}{-}{82}{}{z}{+}{80}\\ {-}{44}{}{z}{+}{71}& {-}{17}{}{z}{-}{75}& {-}{10}{}{z}{-}{7}& {-}{40}{}{z}{+}{42}\\ {-}{50}{}{{z}}^{{3}}{+}{23}{}{{z}}^{{2}}{+}{75}{}{z}{-}{92}& {6}{}{{z}}^{{3}}{+}{74}{}{{z}}^{{2}}{+}{72}{}{z}{+}{37}& {-}{23}{}{{z}}^{{3}}{+}{87}{}{{z}}^{{2}}{+}{44}{}{z}{+}{29}& {98}{}{{z}}^{{3}}{-}{23}{}{{z}}^{{2}}{+}{10}{}{z}{-}{61}\\ {-}{8}{}{{z}}^{{3}}{-}{29}{}{{z}}^{{2}}{+}{95}{}{z}{+}{11}& {-}{49}{}{{z}}^{{3}}{-}{47}{}{{z}}^{{2}}{+}{40}{}{z}{-}{81}& {91}{}{{z}}^{{3}}{+}{68}{}{{z}}^{{2}}{-}{10}{}{z}{+}{31}& {-}{51}{}{{z}}^{{3}}{+}{77}{}{{z}}^{{2}}{+}{95}{}{z}{+}{1}\end{array}\right]$ (7)
 > $d≔\mathrm{Determinant}\left(m\right)$
 ${d}{:=}{58241707}{}{{z}}^{{9}}{+}{19263260}{}{{z}}^{{8}}{-}{145068342}{}{{z}}^{{7}}{+}{169363187}{}{{z}}^{{6}}{+}{98898633}{}{{z}}^{{5}}{-}{333772968}{}{{z}}^{{4}}{+}{57745075}{}{{z}}^{{3}}{+}{54218412}{}{{z}}^{{2}}{+}{4321491}{}{z}{+}{3727553}$ (8)

First, compute the inverse of this determinant modulo T.

 > $\mathrm{inv}≔\mathrm{Inverse}\left(d,T,R\right)$
 ${\mathrm{inv}}{:=}\left[\left[\left[{89}{}{z}{+}{55}{,}{1}{,}{\mathrm{regular_chain}}\right]{,}\left[{89}{}{z}{+}{55}{,}{1}{,}{\mathrm{regular_chain}}\right]{,}\left[{89}{}{z}{+}{55}{,}{1}{,}{\mathrm{regular_chain}}\right]{,}\left[{89}{}{z}{+}{55}{,}{1}{,}{\mathrm{regular_chain}}\right]\right]{,}\left[{}\right]\right]$ (9)
 > $\mathrm{seq}\left(\mathrm{Equations}\left({{{\mathrm{inv}}_{1}}_{i}}_{3},R\right),i=1..\mathrm{nops}\left({\mathrm{inv}}_{1}\right)\right)$
 $\left[{x}{+}{1}{,}{y}{+}{1}{,}{z}{+}{1}\right]{,}\left[{x}{+}{1}{,}{y}{+}{100}{,}{z}{+}{1}\right]{,}\left[{x}{+}{100}{,}{y}{+}{100}{,}{z}{+}{1}\right]{,}\left[{{x}}^{{2}}{+}\left({100}{}{y}{+}{2}\right){}{x}{+}{99}{}{y}{,}{{y}}^{{2}}{+}{99}{,}{z}{+}{2}\right]$ (10)

You can also reduce the matrix m in the first place.

 > $\mathrm{MatrixOverChain}\left(m,T,R\right)$
 $\left[\left[\begin{array}{cccc}{87}{}{z}{+}{28}& {81}{}{z}{+}{51}& {30}{}{z}{+}{99}& {35}{}{z}{+}{57}\\ {57}{}{z}{+}{71}& {84}{}{z}{+}{26}& {91}{}{z}{+}{94}& {61}{}{z}{+}{42}\\ {60}{}{z}{+}{67}& {94}{}{z}{+}{26}& {26}{}{z}{+}{20}& {58}{}{z}{+}{68}\\ {25}{}{z}{+}{21}& {40}{}{z}{+}{22}& {19}{}{z}{+}{37}& {12}{}{z}{+}{46}\end{array}\right]{,}{\mathrm{regular_chain}}\right]$ (11)

Then, compute the inverse of the reduced matrix modulo T. You can see that the computation splits in the same manner as the inverse of the determinant below.

 > $\mathrm{invm}≔\mathrm{MatrixInverse}\left(m,T,R\right)$
 ${\mathrm{invm}}{:=}\left[\left[\left[\left[\begin{array}{rrrr}{87}& {82}& {90}& {70}\\ {11}& {13}& {63}& {44}\\ {34}& {44}& {63}& {91}\\ {4}& {17}& {70}& {22}\end{array}\right]{,}{\mathrm{regular_chain}}\right]{,}\left[\left[\begin{array}{rrrr}{87}& {82}& {90}& {70}\\ {11}& {13}& {63}& {44}\\ {34}& {44}& {63}& {91}\\ {4}& {17}& {70}& {22}\end{array}\right]{,}{\mathrm{regular_chain}}\right]{,}\left[\left[\begin{array}{rrrr}{87}& {82}& {90}& {70}\\ {11}& {13}& {63}& {44}\\ {34}& {44}& {63}& {91}\\ {4}& {17}& {70}& {22}\end{array}\right]{,}{\mathrm{regular_chain}}\right]{,}\left[\left[\begin{array}{rrrr}{39}& {47}& {34}& {34}\\ {46}& {86}& {32}& {70}\\ {81}& {75}& {84}& {31}\\ {57}& {35}& {32}& {38}\end{array}\right]{,}{\mathrm{regular_chain}}\right]\right]{,}\left[{}\right]\right]$ (12)
 > $\mathrm{seq}\left(\mathrm{Equations}\left({{{\mathrm{invm}}_{1}}_{i}}_{2},R\right),i=1..\mathrm{nops}\left({\mathrm{inm}}_{1}\right)\right)$
 $\left[{x}{+}{1}{,}{y}{+}{1}{,}{z}{+}{1}\right]$ (13)

Finally, compute the low echelon form of m modulo T.

 > $\mathrm{lem}≔\mathrm{LowerEchelonForm}\left(m,T,R\right)$
 ${\mathrm{lem}}{:=}\left[\left[\left[\begin{array}{cccc}{98}& {0}& {0}& {0}\\ {33}& {42}& {0}& {0}\\ {76}& {90}& {20}& {0}\\ {-}{8}{}{{z}}^{{3}}{-}{29}{}{{z}}^{{2}}{+}{95}{}{z}{+}{11}& {-}{49}{}{{z}}^{{3}}{-}{47}{}{{z}}^{{2}}{+}{40}{}{z}{-}{81}& {91}{}{{z}}^{{3}}{+}{68}{}{{z}}^{{2}}{-}{10}{}{z}{+}{31}& {-}{51}{}{{z}}^{{3}}{+}{77}{}{{z}}^{{2}}{+}{95}{}{z}{+}{1}\end{array}\right]{,}{\mathrm{regular_chain}}\right]{,}\left[\left[\begin{array}{cccc}{98}& {0}& {0}& {0}\\ {33}& {42}& {0}& {0}\\ {76}& {90}& {20}& {0}\\ {-}{8}{}{{z}}^{{3}}{-}{29}{}{{z}}^{{2}}{+}{95}{}{z}{+}{11}& {-}{49}{}{{z}}^{{3}}{-}{47}{}{{z}}^{{2}}{+}{40}{}{z}{-}{81}& {91}{}{{z}}^{{3}}{+}{68}{}{{z}}^{{2}}{-}{10}{}{z}{+}{31}& {-}{51}{}{{z}}^{{3}}{+}{77}{}{{z}}^{{2}}{+}{95}{}{z}{+}{1}\end{array}\right]{,}{\mathrm{regular_chain}}\right]{,}\left[\left[\begin{array}{cccc}{98}& {0}& {0}& {0}\\ {33}& {42}& {0}& {0}\\ {76}& {90}& {20}& {0}\\ {-}{8}{}{{z}}^{{3}}{-}{29}{}{{z}}^{{2}}{+}{95}{}{z}{+}{11}& {-}{49}{}{{z}}^{{3}}{-}{47}{}{{z}}^{{2}}{+}{40}{}{z}{-}{81}& {91}{}{{z}}^{{3}}{+}{68}{}{{z}}^{{2}}{-}{10}{}{z}{+}{31}& {-}{51}{}{{z}}^{{3}}{+}{77}{}{{z}}^{{2}}{+}{95}{}{z}{+}{1}\end{array}\right]{,}{\mathrm{regular_chain}}\right]{,}\left[\left[\begin{array}{cccc}{78}& {0}& {0}& {0}\\ {48}& {12}& {0}& {0}\\ {68}& {15}& {56}& {0}\\ {-}{8}{}{{z}}^{{3}}{-}{29}{}{{z}}^{{2}}{+}{95}{}{z}{+}{11}& {-}{49}{}{{z}}^{{3}}{-}{47}{}{{z}}^{{2}}{+}{40}{}{z}{-}{81}& {91}{}{{z}}^{{3}}{+}{68}{}{{z}}^{{2}}{-}{10}{}{z}{+}{31}& {-}{51}{}{{z}}^{{3}}{+}{77}{}{{z}}^{{2}}{+}{95}{}{z}{+}{1}\end{array}\right]{,}{\mathrm{regular_chain}}\right]\right]$ (14)

References

 Aubry, P.; Lazard, D.; and Moreno Maza, M. "On the Theories of Triangular Sets." Journal of Symbolic Computation, (July/August 1999): 105-124.
 Boulier, F. and Lemaire, F. "Computing Canonical Representatives of Regular Differential Ideals." Proceedings of ISSAC 2000, pp. 38-47. 2000.
 Dahan, X.; Moreno Maza, M.; Schost, E.; Wu, W.; and Xie, Y. "Equiprojectable Decompositions of Zero-Dimensional Varieties." Proceedings of ICPSS 2004, pp. 69-71. 2004.
 Della Dora, J.; Discrescenzo, C.; and Duval, D. "About a New Method for Computing in Algebraic Number Fields." Proceedings of EUROCAL 1985, pp. 289-290. 1985.
 Hubert, E. "Notes on Triangular Sets and Triangulation-Decomposition Algorithms." Lecture Notes in Computer Science, Vol. 2630, (2003).
 Kalkbrener, M. Three Contributions to Elimination Theory. PhD Thesis, University of Linz, Austria, 1991.
 Lazard, D. "Solving zero-dimensional algebraic systems" J. Symb. Comp., Vol. 13, (1992): 117-133.
 Moreno Maza, M. "On Triangular Decompositions of Algebraic Varieties." Proceedings of MEGA 2000. 2000.
 Moreno Maza, M. and Rioboo, R. "Polynomial GCD computations over towers of algebraic extensions." In proc. of AAECC-11, Lecture Notes in Comput. Sci, Vol. 948, Springer, (1995).