source:git/Singular/LIB/solve.lib@dc3a44

spielwiese
Last change on this file since dc3a44 was dc3a44, checked in by Olaf Bachmann <obachman@…>, 24 years ago
* generation of library docu git-svn-id: file:///usr/local/Singular/svn/trunk@3245 2c84dea3-7e68-4137-9b89-c4e89433aadc
• Property mode set to 100644
File size: 7.3 KB
Line
1///////////////////////////////////////////////////////////////////////////////
2
3version="\$Id: solve.lib,v 1.11 1999-07-07 16:38:28 obachman Exp \$";
4info="
5LIBRARY: solve.lib     PROCEDURES TO SOLVE POLYNOMIAL SYSTEMS
6AUTHOR:  Moritz Wenk,  email: wenk@mathematik.uni-kl.de
7
8PROCEDURES:
9 ures_solve(i,..);      find all roots of 0-dimensional ideal i with resultants
10 mp_res_mat(i,..);      multipolynomial resultant matrix of ideal i
11 laguerre_solve(p,..);  find all roots of univariate polynom p
12 interpolate(i,j,d);    interpolate poly from evaluation points i and results j
13";
14
15///////////////////////////////////////////////////////////////////////////////
16
17proc ures_solve( ideal gls, list # )
18"USAGE:   ures_solve(i[,k,l,m]); i ideal, k,l,m integers
19         k=0: use sparse resultant matrix of Gelfand, Kapranov and Zelevinsky
20         k=1: use resultant matrix of Macaulay (k=0 is default)
21         l>0: defines precision of fractional part if ground field is Q
22         m=0,1,2: number of iterations for approximation of roots (default=2)
23ASSUME:  i is a zerodimensional ideal with
24         nvars(basering) = ncols(i) = number of vars actually occuring in i
25RETURN:  list of all (complex) roots of the polynomial system i = 0,
26         of type number if the ground field is the complex numbers,
27         of type string if the ground field is the rational or real numbers
28EXAMPLE: example ures_solve; shows an example
29"
30{
31  int typ=0;
32  int polish=2;
33  int prec=30;
34
35  if ( size(#) >= 1 )
36  {
37    typ= #[1];
38    if ( typ < 0 || typ > 1 )
39    {
40      ERROR("Valid values for second parameter k are:
41      0: use sparse Resultant (default)
42      1: use Macaulay Resultant");
43    }
44  }
45  if ( size(#) >= 2 )
46  {
47    prec= #[2];
48    if ( prec == 0 ) { prec = 30; }
49    if ( prec < 0 )
50    {
51      ERROR("Third parameter l must be positive!");
52    }
53  }
54  if ( size(#) >= 3 )
55  {
56    polish= #[3];
57    if ( polish < 0 || polish > 2 )
58    {
59      ERROR("Valid values for fourth parameter m are:
60      0,1,2: number of iterations for approximation of roots");
61    }
62  }
63
64  if ( size(#) > 3 )
65  {
66    ERROR("only three parameters allowed!");
67  }
68
69  int digits= system("setFloatDigits",prec);
70
71  return(uressolve(gls,typ,polish));
72
73}
74example
75{
76  "EXAMPLE:";echo=2;
77  // compute the intersection points of two curves
78  ring rsq = 0,(x,y),lp;
79  ideal gls=  x2 + y2 - 10, x2 + xy + 2y2 - 16;
80  ures_solve(gls);
81  // result is a list (x,y)-coordinates as strings
82
83  // now with complex coefficient field, precision is 10 digits
84  ring rsc= (real,10,I),(x,y),lp;
85  ideal i = (2+3*I)*x2 + (0.35+I*45.0e-2)*y2 - 8, x2 + xy + (42.7)*y2;
86  ures_solve(i);
87  // result is a list of (x,y)-coordinates of complex numbers
88}
89///////////////////////////////////////////////////////////////////////////////
90
91proc laguerre_solve( poly f, list # )
92"USAGE:   laguerre_solve( p[,l,m]); f poly, l,m integers
93         l>0: defines precision of fractional part if ground field is Q
94         m=0,1,2: number of iterations for approximation of roots (default=2)
95ASSUME:  p is an univariate polynom
96RETURN:  list of all (complex) roots of the polynomial p;
97         of type number if the ground field is the complex numbers,
98         of type string if the ground field is the rational or real numbers
99EXAMPLE: example laguerre_solve; shows an example
100"
101{
102  int polish=2;
103  int prec=30;
104
105  if ( size(#) >= 1 )
106  {
107    prec= #[1];
108    if ( prec == 0 ) { prec = 30; }
109    if ( prec < 0 )
110    {
111      ERROR("Fisrt parameter must be positive!");
112    }
113  }
114  if ( size(#) >= 2 )
115  {
116    polish= #[2];
117    if ( polish < 0 || polish > 2 )
118    {
119      ERROR("Valid values for third parameter are:
120      0,1,2: number of iterations for approximation of roots");
121    }
122  }
123  if ( size(#) > 2 )
124  {
125    ERROR("only two parameters allowed!");
126  }
127
128  int digits= system("setFloatDigits",prec);
129
130  return(laguerre(f,polish));
131
132}
133example
134{
135  "EXAMPLE:";echo=2;
136  // Find all roots of an univariate polynomial using Laguerre's method:
137  ring rs1= 0,(x,y),lp;
138  poly f = 15x5 + x3 + x2 - 10;
139  laguerre_solve(f);
140
141  // Now with 10 digits precision:
142  laguerre_solve(f,10);
143
144  // Now with complex coefficients, precision is 20 digits:
145  ring rsc= (real,20,I),x,lp;
146  poly f = (15.4+I*5)*x^5 + (25.0e-2+I*2)*x^3 + x2 - 10*I;
147  list l = laguerre_solve(f);
148  l;
149}
150///////////////////////////////////////////////////////////////////////////////
151
152proc mp_res_mat( ideal i, list # )
153"USAGE:   mp_res_mat(i[,k]); i ideal, k integer
154         k=0: sparse resultant matrix of Gelfand, Kapranov and Zelevinsky
155         k=1: resultant matrix of Macaulay (k=0 is default)
156ASSUME:  nvars(basering) = ncols(i)-1 = number of vars actually occuring in i,
157         for k=1 i must be homogeneous
158RETURN:  module representing the multipolynomial resultant matrix
159EXAMPLE: example mp_res_mat; shows an example
160"
161{
162  int typ=2;
163
164  if ( size(#) == 1 )
165  {
166    typ= #[1];
167    if ( typ < 0 || typ > 1 )
168    {
169      ERROR("Valid values for third parameter are:
170      0: sparse resultant (default)
171      1: Macaulay resultant");
172    }
173  }
174  if ( size(#) > 1 )
175  {
176    ERROR("only two parameters allowed!");
177  }
178
179  return(mpresmat(i,typ));
180
181}
182example
183{
184  "EXAMPLE:";echo=2;
185  // compute resultant matrix in ring with parameters (sparse resultant matrix)
186  ring rsq= (0,u0,u1,u2),(x1,x2),lp;
187  ideal i= u0+u1*x1+u2*x2,x1^2 + x2^2 - 10,x1^2 + x1*x2 + 2*x2^2 - 16;
188  module m = mp_res_mat(i);
189  print(m);
190  // computing sparse resultant
191  det(m);
192
193  // compute resultant matrix (Macaulay resultant matrix)
194  ring rdq= (0,u0,u1,u2),(x0,x1,x2),lp;
195  ideal h=  homog(imap(rsq,i),x0);
196  h;
197
198  module m = mp_res_mat(h,1);
199  print(m);
200  // computing Macaulay resultant (should be the same as above!)
201  det(m);
202
203  // compute numerical sparse resultant matrix
204  setring rsq;
205  ideal ir= 15+2*x1+5*x2,x1^2 + x2^2 - 10,x1^2 + x1*x2 + 2*x2^2 - 16;
206  module mn = mp_res_mat(ir);
207  print(mn);
208  // computing sparse resultant
209  det(mn);
210}
211///////////////////////////////////////////////////////////////////////////////
212
213proc interpolate( ideal p, ideal w, int d )
214"USAGE:   interpolate(p,v,d); p,v ideals, d int
215ASSUME:  ground field K is the rational numbers,
216         p and v consist of numbers of the ground filed K, p must have
217         n elements, v must have N=(d+1)^n elements where n=nvars(basering)
218         and d=deg(f) (f is the unknown polynomial in K[x1,...,xn])
219COMPUTE: polynomial f with values given by v at points p1,..,pN derived from p;
220         more precisely: consider p as point in K^n and v as N elements in K,
221         let p1,..,pN be the points in K^n obtained by evaluating all monomials
222         of degree 0,1,...,N at p in lexicographical order,
223         then the procedure computes the polynomial f satisfying f(pi) = v[i]
224RETURN:  polynomial f of degree d
225NOTE:    mainly useful for n=1, with f satisfying f(p^(i-1)) = v[i], i=1..d+1
226EXAMPLE: example interpolate; shows an example
227"
228{
229  return(vandermonde(p,w,d));
230}
231example
232{
233  "EXAMPLE:";  echo=2;
234  ring r1 = 0,(x),lp;
235  // determine f with deg(f) = 4 and
236  // v = values of f at points 3^0, 3^1, 3^2, 3^3, 3^4
237  ideal v=16,0,11376,1046880,85949136;
238  interpolate( 3, v, 4 );
239
240  ring r2 = 0,(x,y),dp;
241  // determine f with deg(f) = 3 and
242  // v = values of f at 16 points (2,3)^0=(1,1),...,(2,3)^15=(2^15,3^15)
243  // valuation point (2,3)
244  ideal p = 2,3;
245  ideal v= 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16;
246  interpolate( p,v,3 );
247}
248///////////////////////////////////////////////////////////////////////////////
Note: See TracBrowser for help on using the repository browser.