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
|
% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\SquareFreeRegularTriangularSetXmpTitle}{SquareFreeRegularTriangularSet}
\newcommand{\SquareFreeRegularTriangularSetXmpNumber}{9.75}
%
% =====================================================================
\begin{page}{SquareFreeRegularTriangularSetXmpPage}{9.75 SquareFreeRegularTriangularSet}
% =====================================================================
\beginscroll
The \spadtype{SquareFreeRegularTriangularSet} domain constructor implements
square-free regular triangular sets.
See the \spadtype{RegularTriangularSet} domain constructor
for general regular triangular sets.
Let {\em T} be a regular triangular set consisting of polynomials
{\em t1, ..., tm} ordered by increasing main variables.
The regular triangular set {\em T} is square-free if {\em T}
is empty or if {\em t1, ..., tm-1} is square-free and if
the polynomial {\em tm} is square-free as
a univariate polynomial with coefficients in the tower
of simple extensions associated with {\em t1, ..., tm-1}.
The main interest of square-free regular triangular sets
is that their associated towers of simple extensions
are product of fields.
Consequently, the saturated ideal of a square-free regular triangular set
is radical.
This property simplifies some of the operations related
to regular triangular sets.
However, building square-free regular triangular sets
is generally more expensive than building
general regular triangular sets.
As the \spadtype{RegularTriangularSet} domain constructor,
the \spadtype{SquareFreeRegularTriangularSet} domain constructor also implements
a method for solving polynomial systems by means of regular triangular sets.
This is in fact the same method with some adaptations to take into
account the fact that the computed regular chains are square-free.
Note that it is also possible to pass from a decomposition
into general regular triangular sets to a decomposition into
square-free regular triangular sets.
This conversion is used internally by the
\spadtype{LazardSetSolvingPackage} package constructor.
{\bf N.B.} When solving polynomial systems with the
\spadtype{SquareFreeRegularTriangularSet} domain constructor
or the \spadtype{LazardSetSolvingPackage} package constructor,
decompositions have no redundant components.
See also \spadtype{LexTriangularPackage} and \spadtype{ZeroDimensionalSolvePackage} for the case of
algebraic systems with a finite number of (complex) solutions.
We shall explain now how to use the constructor \spadtype{SquareFreeRegularTriangularSet}.
This constructor takes four arguments.
The first one, {\bf R}, is the coefficient ring of the polynomials;
it must belong to the category \spadtype{GcdDomain}.
The second one, {\bf E}, is the exponent monoid of the polynomials;
it must belong to the category \spadtype{OrderedAbelianMonoidSup}.
the third one, {\bf V}, is the ordered set of variables;
it must belong to the category \spadtype{OrderedSet}.
The last one is the polynomial ring;
it must belong to the category \spadtype{RecursivePolynomialCategory(R,E,V)}.
The abbreviation for \spadtype{SquareFreeRegularTriangularSet} is
\spadtype{SREGSET}.
Note that the way of understanding triangular decompositions
is detailed in the example of the \spadtype{RegularTriangularSet}
constructor.
\xtc{
Let us illustrate the use of this constructor with one example (Donati-Traverso).
Define the coefficient ring.
}{
\spadpaste{R := Integer \bound{R}}
}
\xtc{
Define the list of variables,
}{
\spadpaste{ls : List Symbol := [x,y,z,t] \bound{ls}}
}
\xtc{
and make it an ordered set;
}{
\spadpaste{V := OVAR(ls) \free{ls} \bound{V}}
}
\xtc{
then define the exponent monoid.
}{
\spadpaste{E := IndexedExponents V \free{V} \bound{E}}
}
\xtc{
Define the polynomial ring.
}{
\spadpaste{P := NSMP(R, V) \free{R} \free{V} \bound{P}}
}
\xtc{
Let the variables be polynomial.
}{
\spadpaste{x: P := 'x \free{P} \bound{x}}
}
\xtc{
}{
\spadpaste{y: P := 'y \free{P} \bound{y}}
}
\xtc{
}{
\spadpaste{z: P := 'z \free{P} \bound{z}}
}
\xtc{
}{
\spadpaste{t: P := 't \free{P} \bound{t}}
}
\xtc{
Now call the \spadtype{SquareFreeRegularTriangularSet} domain constructor.
}{
\spadpaste{ST := SREGSET(R,E,V,P) \free{R} \free{E} \free{V} \free{P} \bound{ST} }
}
\xtc{
Define a polynomial system.
}{
\spadpaste{p1 := x ** 31 - x ** 6 - x - y \free{x} \free{y} \bound{p1}}
}
\xtc{
}{
\spadpaste{p2 := x ** 8 - z \free{x} \free{z} \bound{p2}}
}
\xtc{
}{
\spadpaste{p3 := x ** 10 - t \free{x} \free{t} \bound{p3}}
}
\xtc{
}{
\spadpaste{lp := [p1, p2, p3] \free{p1} \free{p2} \free{p3} \bound{lp}}
}
\xtc{
First of all, let us solve this system in the sense of Kalkbrener.
}{
\spadpaste{zeroSetSplit(lp)$ST \free{lp} \free{ST}}
}
\xtc{
And now in the sense of Lazard (or Wu and other authors).
}{
\spadpaste{zeroSetSplit(lp,false)$ST \free{lp} \free{ST} \bound{lts}}
}
Now to see the difference with the \spadtype{RegularTriangularSet} domain constructor,
\xtc{
we define:
}{
\spadpaste{T := REGSET(R,E,V,P) \free{R} \free{E} \free{V} \free{P} \bound{T} }
}
\xtc{
and compute:
}{
\spadpaste{lts := zeroSetSplit(lp,false)$T \free{lp} \free{T} \bound{lts}}
}
If you look at the second set in both decompositions in the sense of Lazard,
you will see that the polynomial with main variable {\bf y} is not the same.
Let us understand what has happened.
\xtc{
We define:
}{
\spadpaste{ts := lts.2 \free{lts} \bound{ts}}
}
\xtc{
}{
\spadpaste{pol := select(ts,'y)$T \free{ts} \free{y} \free{T} \bound{pol}}
}
\xtc{
}{
\spadpaste{tower := collectUnder(ts,'y)$T \free{ts} \free{y} \free{T} \bound{tower}}
}
\xtc{
}{
\spadpaste{pack := RegularTriangularSetGcdPackage(R,E,V,P,T) \free{R} \free{E} \free{V} \free{P} \free{T} \bound{pack}}
}
\xtc{
Then we compute:
}{
\spadpaste{toseSquareFreePart(pol,tower)$pack \free{pol} \free{tower} \free{pack}}
}
\endscroll
\autobuttons
\end{page}
%
|
