1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
|
/* -*- Mode: Maxima -*- */
/*
**
** $Id: grobner.demo,v 1.2 2003-05-03 11:40:00 starseeker Exp $
** Copyright (C) 1999, 2002 Marek Rychlik <rychlik@u.arizona.edu>
**
** This program is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 2 of the License, or
** (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU General Public License for more details.
**
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**
*/
showtime:true;
/* POLY_MONOMIAL_ORDER switch represents the monomial order that will globally be in effect
for the succeeding operations. */
poly_monomial_order:'lex;
/* POLY_EXPAND parses polynomials to internal form and back. It can be used to test
whether an expression correctly parses to the internal representation.
The following examples illustrate that indexed and transcendental function variables
are allowed. */
poly_expand(x,[x,y]);
poly_expand(x+y,[x,y]);
poly_expand(x-y,[x,y]);
poly_expand((x-y)*(x+y),[x,y]);
poly_expand((x+y)^2,[x,y]);
poly_expand((x+y)^5,[x,y]);
poly_expand(x/y-1,[x]);
poly_expand(x^2/sqrt(y)-x*exp(y)-1,[x]);
poly_expand(sin(x)-sin(x)^2-1,[sin(x)]);
poly_expand((x[2]/sin(y[3])-1)^5,[x[2]]),poly_return_term_list:true;
/* POLY_ADD, POLY_SUBTRACT, POLY_MULTIPLY and POLY_EXPT are the arithmetical operations on polynomials.
These are performed using the internal representation, but the results are converted back to the
Maxima general form */
poly_add(x^2*y+z,x-z,[x,y,z]);
poly_subtract(x^2*y+z,x-z,[x,y,z]);
poly_multiply(x^2*y+z,x-z,[x,y,z]) - (x^2*y+z)*(x-z), expand;
poly_expt(x-y, 3, [x,y]) - (x-y)^3, expand;
/* POLY_CONTENT extracts the GCD of its coefficients */
poly_content(21*x+35*y,[x,y]);
/* POLY_PRIMITIVE_PART divides a polynomial by the GCD of its coefficients */
poly_primitive_part(21*x+35*y,[x,y]);
/* POLY_S_POLYNOMIAL computest the syzygy polynomial (S-polynomial) of two polynomials */
poly_s_polynomial(x+y,x-y,[x,y]);
/* POLY_NORMAL_FORM finds the normal form of a polynomial with respect to a set of polynomials. */
poly_normal_form(x^2+y^2,[x-y,x+y],[x,y]);
poly_pseudo_divide(2*x^2+3*y^2,[7*x-y^2,11*x+y],[x,y]);
poly_exact_divide((x+y)^2,x+y,[x,y]);
/* POLY_BUCHBERGER performs the Buchberger algorithm on a list of polynomials and returns
the resulting Grobner basis */
poly_buchberger([x^2-y*x,x^2+y+x*y^2],[x,y]);
/* POLY_REDUCTION reduces a set of polynomials, so that
each polynomial is fully reduced with respect to the other polynomials */
poly_reduction([x^2-x*y,x*y^2+y+x^2,x*y^2+x*y+y,x*y-y^2,y^3+y^2+y],[x,y]);
/* POLY_MINIMIZATION selects a subset of a set of polynomials, so that no leading monomial is divisible by
another leading monomial */
poly_minimization([x^2-x*y,x*y^2+y+x^2,x*y^2+x*y+y,x*y-y^2,y^3+y^2+y],[x,y]);
/* POLY_REDUCED_GROBNER returns a reduced Grobner basis */
poly_reduced_grobner([x^2-y*x,x^2+y+x*y^2],[x,y]);
/* POLY_NORMALIZE divides a polynomial by its leading coefficient */
poly_normalize(2*x+y,[x,y]);
/* POLY_NORMALIZE_LIST applies POLY_NORMALIZE to each polynomial in the list */
poly_normalize_list([2*x+y,3*x^2+7],[x,y]);
/* POLY_DEPENDS_P tests whether a polynomial depends on a variable */
poly_depends_p(x^2+y,x,[x,y,z]);
poly_depends_p(x^2+y,z,[x,y,z]);
/* POLY_ELIMINATION_IDEAL returns the grobner basis of the K-th elimination ideal of an
ideal specified as a list of generating polynomials (not necessarily Grobner basis */
poly_elimination_ideal([x+y,x-y],0,[x,y]);
poly_elimination_ideal([x+y,x-y],1,[x,y]);
poly_elimination_ideal([x+y,x-y],2,[x,y]);
/* POLY_IDEAL_INTERSECTION returns the intersection of two ideals */
poly_ideal_intersection([x^2+y,x^2-y],[x,y^2],[x,y]);
/* POLY_LCM and POLY_GCD are the Grobner versions of LCM and GCD */
poly_lcm(x*y^2-x,x^2*y+x,[x,y]);
poly_gcd(x*y^2-x,x^2*y+x,[x,y]);
/* POLY_GROBNER_MEMBER tests whether a polynomial belongs to an ideal generated by a list of polynomials,
which is assumed to be a Grobner basis. Equivalent to NORMAL_FORM being 0. */
poly_grobner_member(x+y,[x,y],[x,y]);
/* POLY_GROBNER_EQUAL tests whether two Grobner bases generate the same ideal.
This is equivalent to checking that every polynomial of the first basis reduces to 0
modulo the second basis and vice versa. Note that in the example below the
first list is not a Grobner basis, and thus the result is FALSE. */
poly_grobner_equal([x+y,x-y],[x,y],[x,y]);
/* POLY_GROBNER_SUBSETP tests whether an ideal generated by the first list of polynomials
is contained in the ideal generated by the second list. For this test to always succeed,
the second list must be a Grobner basis */
poly_grobner_subsetp([x+y,x-y],[x,y],[x,y]);
/* POLY_POLYSATURATION_EXTENSION implements the famous Rabinowitz trick. */
poly_polysaturation_extension([x,y],[x^2,y^3],[x,y],[u,v]);
poly_saturation_extension([x,y],[x^2,y^3],[x,y],[u,v]);
/* POLY_IDEAL_POLYSATURATION1 for a given ideal I and polynomials f, g, ..., finds
the colon ideal I : f^inf : g^inf : ... */
poly_ideal_polysaturation1([x,y],[x^2,y^3],[x,y]);
/* POLY_IDEAL_SATURATION for given ideals I and J computes the ideal I : J^inf. */
poly_ideal_saturation([x,y],[x^2,y^3],[x,y]);
/* POLY_IDEAL_POLYSATURATION for a given ideal I and a sequence of ideals J1, J2, J3, ...,
finds the ideal I : J1^inf : J2^inf : J3^inf : ... */
poly_ideal_polysaturation([x,y],[[x^2],[y^3]],[x,y]);
poly_ideal_polysaturation([x^4-y^4], [[x-y],[x^2+y^2, x+y]],[x,y]);
/* POLY_COLON_IDEAL finds the reduced Grobner basis of the colon ideal I:J, i.e. the set of polynomials h
such that there is a polynomial F in J for which H*F is in I */
poly_colon_ideal([x^2*y],[y],[x,y]);
/* POLY_BUCHBERGER_CRITERION verifies whether a given set of polynomials is a Grobner basis with respect
to the current term order */
poly_buchberger_criterion([x,y],[x,y]);
poly_buchberger_criterion([x-y,x+y],[x,y]);
/* Grobner basis associated with Enneper minimal surface */
poly_grobner([x-3*u-3*u*v^2+u^3,y-3*v-3*u^2*v+v^3,z-3*u^2+3*v^2],[u,v,x,y,z]);
poly_reduced_grobner([x-3*u-3*u*v^2+u^3,y-3*v-3*u^2*v+v^3,z-3*u^2+3*v^2],[u,v,x,y,z]);
/* Cyclic roots of degree 5 */
poly_reduced_grobner([x+y+z+u+v,x*y+y*z+z*u+u*v+v*x,x*y*z+y*z*u+z*u*v+u*v*x+v*x*y,x*y*z*u+y*z*u*v+z*u*v*x+u*v*x*y+v*x*y*z,x*y*z*u*v-1],[u,v,x,y,z]);
/* The next example demonstrates the use of the switch
POLY_RETURN_TERM_LIST, which, if set to TRUE, makes the results to
appear as lists of terms listed in the current monomial order rather
than a general form expression */
block([orders:[lex,grlex,grevlex,invlex]],
for i:1 thru length(orders) do (
print(ev([orders[i], poly_expand((x^2+x+y)^3,[x,y])], poly_monomial_order=orders[i]))
)
), poly_return_term_list=true;
/* Grobner bases can be computed over coefficient ring of maxima general expressions */
poly_grobner([x*y-1,x+y],[x]);
/* A tough example learned from Cox */
poly_grobner([x^5+y^4+z^3-1,x^3+y^3+z^2-1], [x,y,z]);
/* An even tougher example of Cox */
poly_grobner([x^5+y^4+z^3-1,x^3+y^3+z^2-1], [x,y,z]);
/* We can also perform Grobner basis calculations modulo prime */
poly_grobner([x^5+y^4+z^3-1,x^3+y^3+z^2-1], [x,y,z]), modulus=3;
/* We can also explicitly ask for the Grobner basis to be calculated using only
integer coefficients. An error will result if this assertion is not satisfied. */
poly_grobner([x^5+y^4+z^3-1,x^3+y^3+z^2-1], [x,y,z]), poly_coefficient_ring='ring_of_integers;
/* The following several tests demonstrate the use of jet variables useful in processing differential equations */
/* Clear some variables */
kill(ode,t,x,y,u,v,r);
/* Set up dependencies */
depends([x,y,u,v,r],t);
/* These are equations representing mathematical pendulum */
ode:[x^2+y^2-c,'diff(x,t)-u,'diff(y,t)-v,'diff(u,t)+r*x,'diff(v,t)+r*y+1];
jet_vars(k):=apply(append,reverse(makelist(['diff(x,t,j),'diff(y,t,j),'diff(u,t,j),'diff(v,t,j),'diff(r,t,j)],j,0,k+1)));
/* Define k-fold prolongation */
prolongate(k):=apply(append,makelist(diff(ode,t,j),j,0,k));
/* Define Grobner basis of k-fold prolongation */
gb(k):=poly_reduced_grobner(prolongate(k),jet_vars(k));
/* Define the l-th projection of the k-th prolongation */
projection(l, k):=poly_elimination_ideal(prolongate(k),5*l,jet_vars(k));
/* Compute some projections */
projection(0, 0);
projection(1, 1);
|
