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 nonstandard 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 zerodivisors. However, computing with these zerodivisors is possible following the celebrated D5 Principle, after J. Della Dora, C. Discrescenzo, and D. Duval. The idea is the following. When a zerodivisor 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 zerodivisor becomes either zero or a regular element (that is, an element that is not a zerodivisor). Therefore, this zerodivisor 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


>


 (1) 
Consider the following polynomial ring.
>


 (2) 
Define a regular chain T with a saturated ideal that is clearly nonprime.
>


>


 (3) 
>


 (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 zerodivisors modulo this ideal: z+1, z+2, xz, xy, and also y1 and y+1. Observe that if the command ListConstruct is used instead of Chain, then this ideal splits into four.
>


 (5) 
>


 (6) 
Now construct a random matrix with coefficients in R.
>


 (7) 
>


 (8) 
First, compute the inverse of this determinant modulo T.
>


 (9) 
>


 (10) 
You can also reduce the matrix m in the first place.
>


 (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.
>


 (12) 
>


 (13) 
Finally, compute the low echelon form of m modulo T.
>


 (14) 


References



Aubry, P.; Lazard, D.; and Moreno Maza, M. "On the Theories of Triangular Sets." Journal of Symbolic Computation, (July/August 1999): 105124.


Boulier, F. and Lemaire, F. "Computing Canonical Representatives of Regular Differential Ideals." Proceedings of ISSAC 2000, pp. 3847. 2000.


Dahan, X.; Moreno Maza, M.; Schost, E.; Wu, W.; and Xie, Y. "Equiprojectable Decompositions of ZeroDimensional Varieties." Proceedings of ICPSS 2004, pp. 6971. 2004.


Della Dora, J.; Discrescenzo, C.; and Duval, D. "About a New Method for Computing in Algebraic Number Fields." Proceedings of EUROCAL 1985, pp. 289290. 1985.


Hubert, E. "Notes on Triangular Sets and TriangulationDecomposition 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 zerodimensional algebraic systems" J. Symb. Comp., Vol. 13, (1992): 117133.


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 AAECC11, Lecture Notes in Comput. Sci, Vol. 948, Springer, (1995).


