The PolynomialIdeals Package
This worksheet demonstrates some features of the PolynomialIdeals package and their use in solving large polynomial systems.
Warning: Some examples may require a powerful computer.
>
|
|
|
Introduction
|
|
We begin by examining a cyclic-5 system. A good first step for working with any system is to compute the Hilbert dimension. If the dimension is zero, then the system has a finite number of solutions.
>
|
|
| (1.1) |
>
|
|
| (1.2) |
An ideal is radical if it has no repeated solutions. It is primary if it does not split into two or more components. An ideal is maximal if it is not contained in any larger (proper) ideal. We can test all of the following using the commands below.
>
|
|
| (1.3) |
>
|
|
| (1.4) |
>
|
|
| (1.5) |
To do these computations, PolynomialIdeals uses Groebner bases. We can see which ones were computed using the IdealInfo[KnownGroebnerBases] command. Once computed, Groebner bases are remembered by the system and used again whenever possible.
>
|
|
| (1.6) |
All of the major algorithms make use of lexicographic Groebner bases. Below we will factor the polynomial system into its prime components. Because the ideal is zero-dimensional, each component corresponds to a finite set of points in affine space.
>
|
|
>
|
|
| (1.7) |
A lexicographic basis is known for every component in the decomposition. The Simplify command replaces the ideal generators by the Groebner basis.
>
|
|
| (1.8) |
The form below is particularly useful.
>
|
|
[1+3*u+u^2, 3+u+t, -1+x, -1+y, z-1]
[-1+u, 1+3*t+t^2, -1+x, -1+y, t+3+z]
[-1+u, -1+t, 1+3*x+x^2, 3+x+y, z-1]
[-1+u, -1+t, -1+x, 1+3*y+y^2, 3+z+y]
[1+3*u+u^2, -1+t, 3+x+u, -1+y, z-1]
[1+u+u^2+u^3+u^4, -u+t, -1+u-u^2+x, 1+2*u+u^2+y, z-u]
[1+u+u^2+u^3+u^4, -1+u-u^2+t, -u+x, -u+y, 1+2*u+u^2+z]
[1+u+u^2+u^3+u^4, -u+t, -u+x, 1+2*u+u^2+y, -1+u-u^2+z]
[1+u+u^2+u^3+u^4, -u+t, 1+2*u+u^2+x, -1+u-u^2+y, z-u]
[1+u+u^2+u^3+u^4, 1+2*u+u^2+t, -u+x, -u+y, -1+u-u^2+z]
[1+u+u^2+u^3+u^4, -u+t, -u+x, -1+u-u^2+y, 1+2*u+u^2+z]
[-1+u, 1+t^2+t+t^3+t^4, 1+t^2+t+t^3+x, -t^3+y, -t^2+z]
[1+u+u^2+u^3+u^4, -1+t, -u^2+x, -u^3+y, 1+u+u^2+u^3+z]
[1+u+u^2+u^3+u^4, -u^3+t, 1+u+u^2+u^3+x, -u^2+y, z-1]
[1+u+u^2+u^3+u^4, -u^2+t, -1+x, u^3+1+u+u^2+y, -u^3+z]
[1+u+u^2+u^3+u^4, 1+u+u^2+u^3+t, -u^3+x, -1+y, -u^2+z]
[1-4*u+6*u^2+u^3+u^4, -3-64*u-15*u^2-9*u^3+11*t, 1+25*u+5*u^2+3*u^3+11*x, 1+25*u+5*u^2+3*u^3+11*y, 1+25*u+5*u^2+3*u^3+11*z]
[1-4*u+6*u^2+u^3+u^4, 1+25*u+5*u^2+3*u^3+11*t, -3-64*u-15*u^2-9*u^3+11*x, 1+25*u+5*u^2+3*u^3+11*y, 1+25*u+5*u^2+3*u^3+11*z]
[1+u+6*u^2-4*u^3+u^4, 6-67*u+39*u^2-9*u^3+11*t, -2+26*u-13*u^2+3*u^3+11*x, -2+26*u-13*u^2+3*u^3+11*y, -2+26*u-13*u^2+3*u^3+11*z]
[1+u+6*u^2-4*u^3+u^4, -2+26*u-13*u^2+3*u^3+11*t, 6-67*u+39*u^2-9*u^3+11*x, -2+26*u-13*u^2+3*u^3+11*y, -2+26*u-13*u^2+3*u^3+11*z]
| |
| (1.9) |
|
|
Separating Solutions
|
|
In the example above, several solutions - corresponding to distinct points on the affine variety - share the same value of u. For example, there are 4 different solutions with u=1. For some applications, it may be desirable to separate all of the solutions, so that they differ in at least one single coordinate.
One way to do this is to introduce a new variable equal to a "random" linear combination of the original variables. In almost all cases, the solutions will have distinct values in the new variable.
>
|
|
| (2.1) |
>
|
|
>
|
|
| (2.2) |
One difficulty with this method is that as soon as the new polynomial is added to the ideal all of our Groebner bases are lost. However, note that if G is a Groebner basis for the original ideal, then [G, f] is a Groebner basis for the new ideal under an appropriate product order.
>
|
|
| (2.3) |
>
|
|
| (2.4) |
>
|
|
Now that a Groebner basis is known, we can compute the univariate polynomial with respect to the new variable using only linear algebra.
>
|
|
| (2.5) |
>
|
|
| (2.6) |
>
|
|
| (2.7) |
Each factor above corresponds to a prime component of the original ideal. There are 70 distinct solutions of this system in C[x,y,z,t,u]. To verify that the solutions are completely separated, we check that a Groebner basis with W << {x, y, z, t, u} is linear in {x, y, z, t, u}. Again, since a Groebner basis is known this will be computed with only linear algebra.
>
|
|
| (2.8) |
|
|
Infolevel[GroebnerBasis]
|
|
The Groebner basis command can output various amounts of information about its progress, as specified by infolevel[GroebnerBasis]. This is especially useful on large systems.
>
|
|
| (3.1) |
Infolevel 2 times the various algorithms and indicates their execution.
>
|
|
>
|
|
-> FGb
total time: 0.031 sec
-> FGLM algorithm
total monomials : 16
total time (sec) 0.15e-1
| |
Infolevel 3 outputs more comprehensive statistics about algorithm performance.
>
|
|
>
|
|
-> FGLM algorithm
rational coefficients
total monomials : 16
normalforms (sec) 0.15e-1
linearsolve (sec) 0.
total time (sec) 0.15e-1
-----------------------------
| |
Infolevel 4 prints intermediate information in a compact form. This is useful for monitoring large computations.
>
|
|
>
|
|
-> FGLM algorithm
rational coefficients
current monomial 1
current monomial z
current monomial z^2
current monomial z^3
current monomial z^4
current monomial z^5
current monomial z^6
current monomial z^7
current monomial z^8
current monomial z^9
current monomial z^10
current monomial w
current monomial t
current monomial s
current monomial p
current monomial b
total monomials : 16
normalforms (sec) 0.94e-1
linearsolve (sec) 0.16e-1
total time (sec) .110
-----------------------------
| |
Infolevel 5 prints detailed information about individual steps of the algorithms. This is useful for checking for the point where a computation fails.
>
|
|
>
|
|
-> FGb
domain: rat_int_cof
Lin Bk ignored [NEW lib]/S:0 -> 8/
[1](2x6)100/
[2](10x18)100/
[3](14x25)100/
[3](20x30)100/
[4](41x43)100/
[4](30x34)50.0/100/
Mingbasis2
(13x23)100/restore Z1 Copy 18.25 for 23/126 exposants
{92.31 per completed}
SWAP Z1/2 Memory usage (estimate): 0.000
/S:1 -> 16/
Mingbasis2
restore Z1 Compute_upper bound 5
{done}
SWAP Z1/2 Memory usage (estimate): 0.000
13 polynomials, 126 terms
total time: 0.156 sec
------------------------------
| |
You can also assign the infolevel of individual algorithms separately using infolevel[buchberger], infolevel[fglm], and infolevel[walk]. A higher value of infolevel[GroebnerBasis] will take precedence over these values.
>
|
|
|
|
Positive-Dimensional Systems
|
|
It is sometimes possible to simplify non zero-dimensional ideals by removing solutions. In the example below, we would like to compute the smallest positive value of m. If we remove the solutions corresponding to m=0, we get an ideal which is zero-dimensional.
>
|
|
| (4.1) |
>
|
|
| (4.2) |
>
|
|
| (4.3) |
>
|
|
| (4.4) |
>
|
|
| (4.5) |
For more general systems we can use the ZeroDimensionalDecomposition command. This command factors the system into a sequence of zero-dimensional ideals. In the process, variables are placed into the coefficient ring to make the resulting ideals zero-dimensional. To recover the original system, we must contract each ideal back to the original ring before computing its intersection. This technique allows us to run zero-dimensional algorithms on ideals of positive dimension, provided they interact nicely with the extension/contraction process.
>
|
|
| (4.6) |
>
|
|
| (4.7) |
>
|
|
| (4.8) |
>
|
|
| (4.9) |
We know immediately that the ideal is not prime because it has factored.
>
|
|
| (4.10) |
>
|
|
| (4.11) |
| (4.12) |
The first ideal lies in the original polynomial ring, so we can factor it directly.
>
|
|
| (4.13) |
In the second ideal, the variable z has been made into a parameter. We verify that this ideal in Q(z)[x, y] is prime.
>
|
|
| (4.14) |
>
|
|
| (4.15) |
>
|
|
| (4.16) |
G[1] is irreducible, and G[2] is linear so it is irreducible mod G[1]. Therefore, this ideal is prime and if we contract, we will recover a prime component of the cyclohexane system.
>
|
|
| (4.17) |
>
|
|
| (4.18) |
We check using the PrimeDecomposition command:
>
|
|
| (4.19) |
|
|
Advanced Example: Computing the radical
|
|
In this section we will write our own command to compute the radical of an ideal. We begin by writing a program for zero-dimensional ideals. For the zero-dimensional case, for each variable we can compute a univariate polynomial in our ideal. We make all those univariate polynomials square-free and add them as generators. This is demonstrated below.
>
|
|
| (5.1) |
>
|
|
| (5.2) |
>
|
|
| (5.3) |
Our first program, a subroutine, will take polynomials and make them square-free.
>
|
|
>
|
|
| (5.4) |
Now our radical program just has to do this for the univariate polynomial in each variable.
>
|
|
>
|
|
| (5.5) |
>
|
|
| (5.6) |
>
|
|
| (5.7) |
Now we need to make it work on non zero-dimensional ideals. As in the previous section, we will use the ZeroDimensionalDecomposition command to reduce the problem to the zero-dimensional case. The ideal below is not radical. We will demonstrate the technique before writing the program.
>
|
|
| (5.8) |
First we decompose the system into a sequence of zero-dimensional ideals, some of which live in an extension ring where some of the the variables are considered to be part of the coefficient field.
>
|
|
| (5.9) |
>
|
|
| (5.10) |
>
|
|
| (5.11) |
Now we can use our radical program above to make each component radical.
>
|
|
| (5.12) |
>
|
|
| (5.13) |
Finally we contract these components back to the original ring and intersect them. The result is the radical of the original ideal.
>
|
|
| (5.14) |
>
|
|
| (5.15) |
>
|
|
| (5.16) |
Here is the program. Notice that we have stored the zero-dimensional decomposition as a list, in case there is only one ideal.
>
|
|
>
|
|
| (5.17) |
We will try it on a more difficult example. This system arises from trying to compute the singular locus of the discriminant of a generic monic polynomial of degree four.
>
|
|
| (5.18) |
The singular locus of f is the set of points where f and its partial derivatives vanish.
>
|
|
| (5.19) |
The system is not zero-dimensional. The singular locus is two-dimensional surface in the four-dimensional parameter space.
>
|
|
| (5.20) |
Our radical program is powerful enough to remove the multiple solutions from this system. The resulting system will be easier to work with and solve.
>
|
|
| (5.21) |
>
|
|
| (5.22) |
It looks like there are two distinct pieces. We can verify this by factoring the system.
>
|
|
| (5.23) |
>
|
|
| (5.24) |
So the locus splits into two irreducible surfaces.
|
|
One Last Example
|
|
PolynomialIdeals can factor and solve large systems. The system below has 96 prime components.
It will take about two and a half minutes to run on a 700 MHz Pentium III.
>
|
|
| (6.1) |
>
|
|
>
|
|
| |
-> FGb
domain: rat_int_cof
Lin Bk ignored [NEW lib]/S:0 -> 8/
[3](68x159)25.0/100/
[4](247x377)100/
[5](485x606)1.6/53.2/100/
[6](729x819)3.3/38.5/73.6/100/
[7](723x800)8.2/40.8/73.5/100/
[8](593x709)8.6/54.3/100/
[9](391x580)0.0/100/
[10](146x302)100/
Mingbasis2
(126x380)6.3/57.1/100/restore Z1 Copy 21.62 for 380/1758 exposants
{done}
SWAP Z1/2 Memory usage (estimate): 0.000
126 polynomials, 1758 terms
total time: 0.281 sec
------------------------------
-> FGLM algorithm
rational coefficients
current monomial 1
current monomial x3
current monomial x3^2
current monomial x3^3
current monomial x3^4
current monomial x3^5
current monomial x3^6
current monomial x3^7
current monomial x3^8
current monomial x3^9
current monomial x3^10
current monomial x3^11
current monomial x3^12
current monomial x3^13
current monomial x3^14
current monomial x3^15
current monomial x3^16
current monomial x3^17
current monomial x3^18
current monomial x3^19
current monomial x3^20
current monomial x3^21
current monomial x3^22
current monomial x3^23
current monomial x3^24
current monomial x3^25
current monomial x6
current monomial x6*x3
current monomial x6*x3^2
current monomial x6*x3^3
current monomial x6*x3^4
current monomial x6*x3^5
current monomial x6*x3^6
current monomial x6*x3^7
current monomial x6*x3^8
current monomial x6*x3^9
current monomial x6*x3^10
current monomial x6*x3^11
current monomial x6*x3^12
current monomial x6*x3^13
current monomial x6*x3^14
current monomial x6*x3^15
current monomial x6*x3^16
current monomial x6*x3^17
current monomial x6*x3^18
current monomial x6*x3^19
current monomial x6*x3^20
current monomial x6*x3^21
current monomial x6^2
current monomial x6^2*x3
current monomial x6^2*x3^2
current monomial x6^2*x3^3
current monomial x6^2*x3^4
current monomial x6^2*x3^5
current monomial x6^2*x3^6
current monomial x6^2*x3^7
current monomial x6^2*x3^8
current monomial x6^2*x3^9
current monomial x6^2*x3^10
current monomial x6^2*x3^11
current monomial x6^2*x3^12
current monomial x6^2*x3^13
current monomial x6^2*x3^14
current monomial x6^2*x3^15
current monomial x6^2*x3^16
current monomial x6^2*x3^17
current monomial x6^2*x3^18
current monomial x6^2*x3^19
current monomial x6^2*x3^20
current monomial x6^3
current monomial x6^3*x3
current monomial x6^3*x3^2
current monomial x6^3*x3^3
current monomial x6^3*x3^4
current monomial x6^3*x3^5
current monomial x6^3*x3^6
current monomial x6^3*x3^7
current monomial x6^3*x3^8
current monomial x6^3*x3^9
current monomial x6^3*x3^10
current monomial x6^3*x3^11
current monomial x6^3*x3^12
current monomial x6^3*x3^13
current monomial x6^3*x3^14
current monomial x6^3*x3^15
current monomial x6^3*x3^16
current monomial x6^3*x3^17
current monomial x6^3*x3^18
current monomial x6^3*x3^19
current monomial x6^3*x3^20
current monomial x6^4
current monomial x6^4*x3
current monomial x6^4*x3^2
current monomial x6^4*x3^3
current monomial x6^4*x3^4
current monomial x6^4*x3^5
current monomial x6^4*x3^6
current monomial x6^4*x3^7
current monomial x6^4*x3^8
current monomial x6^4*x3^9
current monomial x6^4*x3^10
current monomial x6^4*x3^11
current monomial x6^4*x3^12
current monomial x6^4*x3^13
current monomial x6^5
current monomial x6^5*x3
current monomial x6^5*x3^2
current monomial x6^5*x3^3
current monomial x6^5*x3^4
current monomial x6^5*x3^5
current monomial x6^5*x3^6
current monomial x6^5*x3^7
current monomial x6^5*x3^8
current monomial x6^5*x3^9
current monomial x6^6
current monomial x6^6*x3
current monomial x6^6*x3^2
current monomial x6^6*x3^3
current monomial x6^6*x3^4
current monomial x6^6*x3^5
current monomial x6^6*x3^6
current monomial x6^6*x3^7
current monomial x6^6*x3^8
current monomial x6^7
current monomial x6^7*x3
current monomial x6^7*x3^2
current monomial x6^7*x3^3
current monomial x6^7*x3^4
current monomial x6^7*x3^5
current monomial x6^7*x3^6
current monomial x6^7*x3^7
current monomial x6^7*x3^8
current monomial x6^8
current monomial x6^8*x3
current monomial x6^8*x3^2
current monomial x6^8*x3^3
current monomial x6^8*x3^4
current monomial x6^8*x3^5
current monomial x6^8*x3^6
current monomial x6^8*x3^7
current monomial x6^8*x3^8
current monomial x6^9
current monomial x6^9*x3
current monomial x6^9*x3^2
current monomial x6^9*x3^3
current monomial x6^9*x3^4
current monomial x6^9*x3^5
current monomial x6^9*x3^6
current monomial x6^9*x3^7
current monomial x6^9*x3^8
current monomial x6^10
current monomial x6^10*x3
current monomial x6^10*x3^2
current monomial x6^10*x3^3
current monomial x6^10*x3^4
current monomial x6^10*x3^5
current monomial x6^10*x3^6
current monomial x6^10*x3^7
current monomial x6^10*x3^8
current monomial x6^11
current monomial x6^11*x3
current monomial x6^11*x3^2
current monomial x6^11*x3^3
current monomial x6^11*x3^4
current monomial x6^11*x3^5
current monomial x6^11*x3^6
current monomial x6^11*x3^7
current monomial x6^11*x3^8
current monomial x6^12
current monomial x6^12*x3
current monomial x6^12*x3^2
current monomial x6^12*x3^3
current monomial x6^12*x3^4
current monomial x6^12*x3^5
current monomial x6^12*x3^6
current monomial x6^12*x3^7
current monomial x6^12*x3^8
current monomial x6^13
current monomial x6^13*x3
current monomial x6^13*x3^2
current monomial x6^13*x3^3
current monomial x6^13*x3^4
current monomial x6^13*x3^5
current monomial x6^13*x3^6
current monomial x6^13*x3^7
current monomial x6^13*x3^8
current monomial x6^14
current monomial x6^14*x3
current monomial x6^14*x3^2
current monomial x6^14*x3^3
current monomial x6^14*x3^4
current monomial x6^14*x3^5
current monomial x6^14*x3^6
current monomial x6^14*x3^7
current monomial x6^14*x3^8
current monomial x6^15
current monomial x6^15*x3
current monomial x6^15*x3^2
current monomial x6^15*x3^3
current monomial x6^15*x3^4
current monomial x6^15*x3^5
current monomial x6^15*x3^6
current monomial x6^15*x3^7
current monomial x6^15*x3^8
current monomial x6^16
current monomial x6^16*x3
current monomial x6^16*x3^2
current monomial x6^16*x3^3
current monomial x6^16*x3^4
current monomial x6^16*x3^5
current monomial x6^17
current monomial x6^17*x3
current monomial x6^17*x3^2
current monomial x6^17*x3^3
current monomial x6^17*x3^4
current monomial x6^18
current monomial x6^18*x3
current monomial x6^18*x3^2
current monomial x6^18*x3^3
current monomial x6^18*x3^4
current monomial x6^19
current monomial x6^19*x3
current monomial x6^19*x3^2
current monomial x6^19*x3^3
current monomial x6^19*x3^4
current monomial x6^20
current monomial x6^20*x3
current monomial x6^21
current monomial x6^22
current monomial x6^23
current monomial x6^24
current monomial x6^25
current monomial x4
current monomial x8
current monomial x5
current monomial x3*x5
current monomial x5*x3^2
current monomial x5*x3^3
current monomial x5*x3^4
current monomial x5*x3^5
current monomial x5*x3^6
current monomial x5*x3^7
current monomial x5*x3^8
current monomial x5*x3^9
current monomial x5*x6
current monomial x5*x6*x3
current monomial x5*x6*x3^2
current monomial x5*x6*x3^3
current monomial x5*x6*x3^4
current monomial x5*x6*x3^5
current monomial x5*x6^2
current monomial x5*x6^2*x3
current monomial x5*x6^2*x3^2
current monomial x5*x6^2*x3^3
current monomial x5*x6^2*x3^4
current monomial x5*x6^3
current monomial x5*x6^3*x3
current monomial x5*x6^3*x3^2
current monomial x5*x6^3*x3^3
current monomial x5*x6^3*x3^4
current monomial x5*x6^4
current monomial x5*x6^4*x3
current monomial x5*x6^5
current monomial x5*x6^6
current monomial x5*x6^7
current monomial x5*x6^8
current monomial x5*x6^9
current monomial x5^2
current monomial x5^2*x3
current monomial x5^2*x6
current monomial x5^3
current monomial x7
current monomial x2
current monomial x1
current monomial x1*x3
current monomial x1*x6
current monomial x1*x5
current monomial x1^2
total monomials : 278
normalforms (sec) 1.00
linearsolve (sec) .575
total time (sec) 1.64
-----------------------------
| |
| (6.2) |
>
|
|
>
|
|
>
|
|
| (6.3) |
>
|
|
| (6.4) |
|
Return to Index for Example Worksheets
|