|
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
|
|
|
>
|
|
|
![[IsZeroMatrix, JacobianMatrix, LowerEchelonForm, MatrixInverse, MatrixMultiply, MatrixOverChain]](/support/helpjp/helpview.aspx?si=4965/file02688/math109.png)
| (1) |
Consider the following polynomial ring.
|
>
|
![R := PolynomialRing([x, y, z], 101)](/support/helpjp/helpview.aspx?si=4965/file02688/math115.png)
|
|
| (2) |
Define a regular chain T with a saturated ideal that is clearly non-prime.
|
>
|
|
|
>
|
![T := Chain([(z+1)*(z+2), y^2+z, (x-z)*(x-y)], E, R)](/support/helpjp/helpview.aspx?si=4965/file02688/math130.png)
|
|
| (3) |
|
>
|
|
|
![[x^2+(100*y+100*z)*x+z*y, y^2+z, z^2+3*z+2]](/support/helpjp/helpview.aspx?si=4965/file02688/math140.png)
| (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.
|
>
|
![split := ListConstruct([(z+1)*(z+2), y^2+z, (x-z)*(x-y)], E, R)](/support/helpjp/helpview.aspx?si=4965/file02688/math170.png)
|
|
![split := [regular_chain, regular_chain, regular_chain, regular_chain]](/support/helpjp/helpview.aspx?si=4965/file02688/math173.png)
| (5) |
|
>
|
|
|
![[[x+1, y+1, z+1], [x+1, y+100, z+1], [x+100, y+100, z+1], [x^2+(100*y+2)*x+99*y, y^2+99, z+2]]](/support/helpjp/helpview.aspx?si=4965/file02688/math180.png)
| (6) |
Now construct a random matrix with coefficients in R.
|
>
|
![m := Matrix([[87*z^2-56*z, -73-62*z^2+97*z, -10-4*z^2-83*z, 80+62*z^2-82*z], [-44*z+71, -17*z-75, -10*z-7, -40*z+42], [-92-50*z^3+23*z^2+75*z, 37+6*z^3+74*z^2+72*z, 29-23*z^3+87*z^2+44*z, -61+98*z^3-23*z^2+10*z], [11-8*z^3-29*z^2+95*z, -81-49*z^3-47*z^2+40*z, 31+91*z^3+68*z^2-10*z, 1-51*z^3+77*z^2+95*z]])](/support/helpjp/helpview.aspx?si=4965/file02688/math188.png)
|
|
![m := Matrix([[87*z^2-56*z, -73-62*z^2+97*z, -10-4*z^2-83*z, 80+62*z^2-82*z], [-44*z+71, -17*z-75, -10*z-7, -40*z+42], [-92-50*z^3+23*z^2+75*z, 37+6*z^3+74*z^2+72*z, 29-23*z^3+87*z^2+44*z, -61+98*z^3-23*z^2+10*z], [11-8*z^3-29*z^2+95*z, -81-49*z^3-47*z^2+40*z, 31+91*z^3+68*z^2-10*z, 1-51*z^3+77*z^2+95*z]])](/support/helpjp/helpview.aspx?si=4965/file02688/math191.png)
| (7) |
|
>
|
|
|
| (8) |
First, compute the inverse of this determinant modulo T.
|
>
|
|
|
![inv := [[[89*z+55, 1, regular_chain], [89*z+55, 1, regular_chain], [89*z+55, 1, regular_chain], [89*z+55, 1, regular_chain]], []]](/support/helpjp/helpview.aspx?si=4965/file02688/math209.png)
| (9) |
|
>
|
![seq(Equations(inv[1][i][3], R), i = 1 .. nops(inv[1]))](/support/helpjp/helpview.aspx?si=4965/file02688/math213.png)
|
|
![[x+1, y+1, z+1], [x+1, y+100, z+1], [x+100, y+100, z+1], [x^2+(100*y+2)*x+99*y, y^2+99, z+2]](/support/helpjp/helpview.aspx?si=4965/file02688/math216.png)
| (10) |
You can also reduce the matrix m in the first place.
|
>
|
|
|
![[Matrix([[87*z+28, 51+81*z, 99+30*z, 57+35*z], [57*z+71, 84*z+26, 91*z+94, 61*z+42], [67+60*z, 26+94*z, 20+26*z, 68+58*z], [21+25*z, 22+40*z, 37+19*z, 46+12*z]]), regular_chain]](/support/helpjp/helpview.aspx?si=4965/file02688/math227.png)
| (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.
|
>
|
|
|
![invm := [[[Matrix([[87, 82, 90, 70], [11, 13, 63, 44], [34, 44, 63, 91], [4, 17, 70, 22]]), regular_chain], [Matrix([[87, 82, 90, 70], [11, 13, 63, 44], [34, 44, 63, 91], [4, 17, 70, 22]]), regular_chain], [Matrix([[87, 82, 90, 70], [11, 13, 63, 44], [34, 44, 63, 91], [4, 17, 70, 22]]), regular_chain], [Matrix([[39, 47, 34, 34], [46, 86, 32, 70], [81, 75, 84, 31], [57, 35, 32, 38]]), regular_chain]], []]](/support/helpjp/helpview.aspx?si=4965/file02688/math238.png)
| (12) |
|
>
|
![seq(Equations(invm[1][i][2], R), i = 1 .. nops(inm[1]))](/support/helpjp/helpview.aspx?si=4965/file02688/math242.png)
|
|
![[x+1, y+1, z+1]](/support/helpjp/helpview.aspx?si=4965/file02688/math245.png)
| (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): 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).
|
|
|
