# source:git/Singular/LIB/random.lib@4ff391

spielwiese
Last change on this file since 4ff391 was 4ff391, checked in by Motsak Oleksandr <motsak@…>, 14 years ago
• Property mode set to `100644`
File size: 15.5 KB
Line
2///////////////////////////////////////////////////////////////////////////////
3version="\$Id: random.lib,v 1.18 2009-03-30 18:36:35 motsak Exp \$";
4category="General purpose";
5info="
6LIBRARY:  random.lib    Creating Random and Sparse Matrices, Ideals, Polys
7
8PROCEDURES:
9 genericid(i[,p,b]);     generic sparse linear combinations of generators of i
10 randomid(id,[k,b]);     random linear combinations of generators of id
11 randommat(n,m[,id,b]);  nxm matrix of random linear combinations of id
12 sparseid(k,u[,o,p,b]);  ideal of k random sparse poly's of degree d [u<=d<=o]
13 sparsematrix(n,m,o[,.]);nxm sparse matrix of polynomials of degree<=o
14 sparsemat(n,m[,p,b]);   nxm sparse integer matrix with random coefficients
15 sparsepoly(u[,o,p,b]);  random sparse polynomial with terms of degree in [u,o]
16 sparsetriag(n,m[,.]);   nxm sparse lower-triag intmat with random coefficients
17 sparseHomogIdeal(k,u,[,.]); ideal with k sparse homogeneous generators of degree in [u, o]
18 triagmatrix(n,m,o[,.]); nxm sparse lower-triag matrix of poly's of degree<=o
19 randomLast(b);          random transformation of the last variable
20 randomBinomial(k,u,..); binomial ideal, k random generators of degree >=u
21           (parameters in square brackets [] are optional)
22";
23
24LIB "inout.lib";
25LIB "general.lib";
26LIB "matrix.lib";
27///////////////////////////////////////////////////////////////////////////////
28
29proc genericid (id, list #)
30"USAGE:   genericid(id[,p,b]);  id ideal/module, p,b integers
31RETURN:  system of generators of id which are generic, sparse, triagonal linear
32         combinations of given generators with coefficients in [1,b] and
33         sparsety p percent, bigger p being sparser (default: p=75, b=30000)
34NOTE:    For performance reasons try small bound b in characteristic 0
35EXAMPLE: example genericid; shows an example
36"
37{
38//----------------------------- set defaults ----------------------------------
39   if( size(#)>=2 ) { int p=#[1]; int b=#[2]; }
40   if( size(#)==1 ) { int p=#[1]; int b=30000}
41   if( size(#)==0 ) { int p=75; int b=30000; }
42//---------------- use sparsetriag for creation of genericid ------------------
43   def i = simplify(id,10);
44   i = i*sparsetriag(ncols(i),ncols(i),p,b);
45   return(i);
46}
47example
48{ "EXAMPLE:"; echo = 2;
49   ring r=0,(t,x,y,z),ds;
50   ideal i= x3+y4,z4+yx,t+x+y+z;
51   genericid(i,0,10);
52   module m=[x,0,0,0],[0,y2,0,0],[0,0,z3,0],[0,0,0,t4];
53   print(genericid(m));
54}
55///////////////////////////////////////////////////////////////////////////////
56
57proc randomid (id, list #)
58"USAGE:   randomid(id[,k,b]);  id ideal/module, b,k integers
59RETURN:  ideal/module having k generators which are random linear combinations
60         of generators of id with coefficients in the interval [-b,b]
61         (default: b=30000, k=size(id))
62NOTE:    For performance reasons try small bound b in characteristic 0
63EXAMPLE: example randomid; shows an example
64"
65{
66//----------------------------- set defaults ----------------------------------
67   if( size(#)>=2 ) { int k=#[1]; int b=#[2]; }
68   if( size(#)==1 ) { int k=#[1]; int b=30000; }
69   if( size(#)==0 ) { int k=size(id); int b=30000; }
70//--------------------------- create randomid ---------------------------------
71   def i = id;
72   i = matrix(id)*random(b,ncols(id),k);
73   return(i);
74}
75example
76{ "EXAMPLE:"; echo = 2;
77   ring r=0,(x,y,z),dp;
78   randomid(maxideal(2),2,9);
79   module m=[x,0,1],[0,y2,0],[y,0,z3];
80   show(randomid(m));
81}
82///////////////////////////////////////////////////////////////////////////////
83
84proc randommat (int n, int m, list #)
85"USAGE:   randommat(n,m[,id,b]);  n,m,b integers, id ideal
86RETURN:  nxm matrix, entries are random linear combinations of elements
87         of id and coefficients in [-b,b]
88         [default: (id,b) = (maxideal(1),30000)]
89NOTE:    For performance reasons try small bound b in char 0
90EXAMPLE:  example randommat; shows an example
91"
92{
93//----------------------------- set defaults ----------------------------------
94   if( size(#)>=2 ) { ideal id=#[1]; int b=#[2]; }
95   if( size(#)==1 ) { ideal id=#[1]; int b=30000; }
96   if( size(#)==0 ) { ideal id=maxideal(1); int b=30000; }
97//--------------------------- create randommat --------------------------------
98   id=simplify(id,2);
99   int g=ncols(id);
100   matrix rand[n][m]; matrix ra[1][m];
101   for (int k=1; k<=n; k=k+1)
102   {
103      ra = id*random(b,g,m);
104      rand[k,1..m]=ra[1,1..m];
105   }
106   return(rand);
107}
108example
109{ "EXAMPLE:"; echo = 2;
110   ring r=0,(x,y,z),dp;
111   matrix A=randommat(3,3,maxideal(2),9);
112   print(A);
113   A=randommat(2,3);
114   print(A);
115}
116///////////////////////////////////////////////////////////////////////////////
117
118proc sparseid (int k, int u, list #)
119"USAGE:   sparseid(k,u[,o,p,b]);  k,u,o,p,b integers
120RETURN:  ideal having k generators, each of degree d, u<=d<=o, p percent of
121         terms in degree d are 0, the remaining have random coefficients
122         in the interval [1,b], (default: o=u, p=75, b=30000)
123EXAMPLE: example sparseid; shows an example
124"
125{
126//----------------------------- set defaults ----------------------------------
127   if( size(#)>=3 ) { int o=#[1]; int p=#[2]; int b=#[3]; }
128   if( size(#)==2 ) { int o=#[1]; int p=#[2]; int b=30000; }
129   if( size(#)==1 ) { int o=#[1]; int p=75; int b=30000; }
130   if( size(#)==0 ) { int o=u; int p=75; int b=30000; }
131//------------------ use sparsemat for creation of sparseid -------------------
132   int ii; matrix i[1][k]; intmat m;
133   if( u <=0 )
134   {
135      m = sparsemat(1,k,p,b);
136      i = m;
137      u=1;
138   }
139   for ( ii=u; ii<=o; ii=ii+1)
140   {
141       m = sparsemat(size(maxideal(ii)),k,p,b);
142       i = i+matrix(maxideal(ii))*m;
143   }
144   return(ideal(i));
145}
146example
147{ "EXAMPLE:"; echo = 2;
148   ring r = 0,(a,b,c,d),ds;
149   sparseid(2,3);"";
150   sparseid(3,0,4,90,9);
151}
152
153///////////////////////////////////////////////////////////////////////////////
154proc sparseHomogIdeal (int k, int u, list #)
155"USAGE:   sparseid(k,u[,o,p,b]);  k,u,o,p,b integers
156RETURN:  ideal having k homogeneous generators, each of random degree in the
157         interval [u,o], p percent of terms in degree d are 0, the remaining
158         have random coefficients in the interval [1,b], (default: o=u, p=75,
159         b=30000)
160EXAMPLE: example sparseid; shows an example
161"
162{
163//----------------------------- set defaults ----------------------------------
164   if( size(#)>=3 ) { int o=#[1]; int p=#[2]; int b=#[3]; }
165   if( size(#)==2 ) { int o=#[1]; int p=#[2]; int b=30000; }
166   if( size(#)==1 ) { int o=#[1]; int p=75; int b=30000; }
167   if( size(#)==0 ) { int o=u; int p=75; int b=30000; }
168//------------------ use sparsemat for creation of sparseid -------------------
169   int ii; ideal i; intmat m; ideal id;
170
171   for ( ii=k; ii>0; ii=ii-1)
172   {
173       id = maxideal(random(u, o)); // monomial basis of some degree
174       m = sparsemat(size(id),1,p,b); // random coefficients
175       i[ii] = (matrix(id)*m)[1,1];
176   }
177   return(i);
178}
179example
180{ "EXAMPLE:"; echo = 2;
181   ring r = 0,(a,b,c,d),dp;
182   sparseHomogIdeal(2,3);"";
183   sparseHomogIdeal(3,0,4,90,9);
184}
185
186
187///////////////////////////////////////////////////////////////////////////////
188
189proc sparsemat (int n, int m, list #)
190"USAGE:   sparsemat(n,m[,p,b]);  n,m,p,b integers
191RETURN:  nxm integer matrix, p percent of the entries are 0, the remaining
192         are random coefficients >=1 and <= b; [defaults: (p,b) = (75,1)]
193EXAMPLE: example sparsemat; shows an example
194"
195{
196   int r,h,ii;
197   int t = n*m;
198   intmat v[1][t];
199//----------------------------- set defaults ----------------------------------
200   if( size(#)>=2 ) { int p=#[1]; int b=#[2]; }
201   if( size(#)==1 ) { int p=#[1]; int b=1; }
202   if( size(#)==0 ) { int p=75; int b=1; }
203//------------------------- check trivial cases ------------------------------
204   if( p<0 ) { p = 0; }
205   if(p>100) { p=100; }
206//--------------- this is faster for not very sparse matrices ----------------
207   if( p<40 )
208   {
209      for( ii=1; ii<=t; ii=ii+1 )
210      { r=( random(1,100)>p ); v[1,ii]=r*random(1,b); h=h+r; }
211   }
212  int bb = t*(100-p);
213  if( 100*h > bb )
214  {
215     while( 100*h > bb )
216     { r=random(1,t); h=h-( v[1,r]>0 ); v[1,r]=0; }
217  }
218  else
219  {
220//------------------- this is faster for sparse matrices ---------------------
221     while ( 100*h < bb )
222     { r=random(1,t); h=h+(v[1,r]==0); v[1,r]=random(1,b); }
223  }
224  intmat M[n][m] = v[1,1..t];
225  return(M);
226}
227example
228{ "EXAMPLE:"; echo = 2;
229   sparsemat(5,5);"";
230   sparsemat(5,5,95);"";
231   sparsemat(5,5,5);"";
232   sparsemat(5,5,50,100);
233}
234///////////////////////////////////////////////////////////////////////////////
235proc sparsematrix (int n, int m, int o, list #)
236"USAGE:   sparsematrix(n,m,o[,u,pe,pp,b]);  n,m,o,u,pe,pp,b integers
237RETURN:  nxm matrix, about pe percent of the entries are 0, the remaining
238         are random polynomials of degree d, u<=d<=o, with  pp percent of
239         the terms being 0, the remaining have random coefficients
240         in the interval [1,b] [default: (pe,u,pp,b) = (0,50,75,100)]
241EXAMPLE: example sparsematrix; shows an example
242"
243{
244   int ii,jj;
245   ideal id;
246   matrix M[n][m];
247//----------------------------- set defaults ----------------------------------
248   int pe=50;int u=0;int pp=75;int b=100;
249   if( size(#)==4 ) { u=#[1]; pe=#[2]; pp=#[3]; b=#[4]; }
250   if( size(#)==3 ) { u=#[1]; pe=#[2]; pp=#[3]; }
251   if( size(#)==2 ) { u=#[1]; pe=#[2]; }
252   if( size(#)==1 ) { u=#[1]; }
253//------------------- use sparsemat and sparseid  -----------------------------
254   intmat I = sparsemat(n,m,pe,1);
255   for(ii=1; ii<=n;ii++)
256   {
257     id = sparseid(m,u,o,pp,b);
258     for(jj=1; jj<=m; jj++)
259     {
260        if( I[ii,jj] !=0)
261        {
262          M[ii,jj]=id[jj];
263        }
264     }
265   }
266   return(M);
267}
268example
269{ "EXAMPLE:"; echo = 2;
270   ring r = 0,(a,b,c,d),dp;
271   // sparse matrix of sparse polys of degree <=2:
272   print(sparsematrix(3,4,2));"";
273   // dense matrix of sparse linear forms:
274   print(sparsematrix(3,3,1,1,0,55,9));
275}
276///////////////////////////////////////////////////////////////////////////////
277
278proc sparsepoly (int u, list #)
279"USAGE:   sparsepoly(u[,o,p,b]);  u,o,p,b integers
280RETURN:  poly having only terms in degree d, u<=d<=o, p percent of the terms
281         in degree d are 0, the remaining have random coefficients in [1,b),
282         (defaults: o=u, p=75, b=30000)
283EXAMPLE:  example sparsepoly; shows an example
284"
285{
286//----------------------------- set defaults ----------------------------------
287   if( size(#)>=3 ) { int o=#[1]; int p=#[2]; int b=#[3]; }
288   if( size(#)==2 ) { int o=#[1]; int p=#[2]; int b=30000; }
289   if( size(#)==1 ) { int o=#[1]; int p=75; int b=30000; }
290   if( size(#)==0 ) { int o=u; int p=75; int b=30000; }
291   int ii; poly f;
292//----------------- use sparseid for creation of sparsepoly -------------------
293   for( ii=u; ii<=o; ii=ii+1 ) { f=f+sparseid(1,ii,ii,p,b)[1]; }
294   return(f);
295}
296example
297{ "EXAMPLE:"; echo = 2;
298   ring r=0,(x,y,z),dp;
299   sparsepoly(5);"";
300   sparsepoly(3,5,90,9);
301}
302///////////////////////////////////////////////////////////////////////////////
303
304proc sparsetriag (int n, int m, list #)
305"USAGE:   sparsetriag(n,m[,p,b]);  n,m,p,b integers
306RETURN:  nxm lower triagonal integer matrix, diagonal entries equal to 1, about
307         p percent of lower diagonal entries are 0, the remaining are random
308         integers >=1 and <= b; [defaults: (p,b) = (75,1)]
309EXAMPLE: example sparsetriag; shows an example
310"
311{
312   int ii,min,l,r; intmat M[n][m];
313   int t=(n*(n-1)) div 2;
314//----------------------------- set defaults ----------------------------------
315   if( size(#)>=2 ) { int p=#[1]; int b=#[2]; }
316   if( size(#)==1 ) { int p=#[1]; int b=1; }
317   if( size(#)==0 ) { int p=75; int b=1; }
318//---------------- use sparsemat for creation of sparsetriag ------------------
319   intmat v[1][t]=sparsemat(1,t,p,b);
320   if( n<=m ) { min=n-1; M[n,n]=1; }
321   else { min=m; }
322   for( ii=1; ii<=min; ii=ii+1 )
323   {
324      l=r+1; r=r+n-ii;
325      M[ii..n,ii]=1,v[1,l..r];
326   }
327   return(M);
328}
329example
330{ "EXAMPLE:"; echo = 2;
331   sparsetriag(5,7);"";
332   sparsetriag(7,5,90);"";
333   sparsetriag(5,5,0);"";
334   sparsetriag(5,5,50,100);
335}
336///////////////////////////////////////////////////////////////////////////////
337proc triagmatrix (int n, int m, int o, list #)
338"USAGE:   triagmatrix(n,m,o[,u,pe,pp,b]);  n,m,o,u,pe,pp,b integers
339RETURN:  nxm lower triagonal matrix, diagonal entries equal to 1, about
340         p percent of lower diagonal entries are 0, the remaining
341         are random polynomials of degree d, u<=d<=o, with  pp percent of
342         the terms being 0, the remaining have random coefficients
343         in the interval [1,b] [default: (pe,u,pp,b) = (0,50,75,100)]
344EXAMPLE: example triagmatrix; shows an example
345"
346{
347   int ii,jj;
348   ideal id;
349   matrix M[n][m];
350//----------------------------- set defaults ----------------------------------
351   int pe=50;int u=0;int pp=75;int b=100;
352   if( size(#)==4 ) { u=#[1]; pe=#[2]; pp=#[3]; b=#[4]; }
353   if( size(#)==3 ) { u=#[1]; pe=#[2]; pp=#[3]; }
354   if( size(#)==2 ) { u=#[1]; pe=#[2]; }
355   if( size(#)==1 ) { u=#[1]; }
356//------------------- use sparsemat and sparseid  -----------------------------
357   intmat I = sparsetriag(n,m,pe,1);
358   for(ii=1; ii<=n;ii++)
359   {
360     id = sparseid(m,u,o,pp,b);
361     for(jj=1; jj<ii; jj++)
362     {
363        if( I[ii,jj] !=0)
364        {
365          M[ii,jj]=id[jj];
366        }
367     }
368   }
369   for(ii=1; ii<=n;ii++)
370   {
371      M[ii,ii]=1;
372   }
373   return(M);
374}
375example
376{ "EXAMPLE:"; echo = 2;
377   ring r = 0,(a,b,c,d),dp;
378   // sparse triagonal matrix of sparse polys of degree <=2:
379   print(triagmatrix(3,4,2));"";
380   // dense triagonal matrix of sparse linear forms:
381   print(triagmatrix(3,3,1,1,0,55,9));
382}
383///////////////////////////////////////////////////////////////////////////////
384
385proc randomLast(int b)
386"USAGE:   randomLast(b);  b int
387RETURN:  ideal = maxideal(1), but the last variable is exchanged by a random
388         linear combination of all variables, with coefficients in the
389         interval [-b,b], except for the last variable which always has
390         coefficient 1
391EXAMPLE: example randomLast; shows an example
392"
393{
394  ideal i=maxideal(1);
395  int k=size(i);
396  i[k]=0;
397  i=randomid(i,size(i),b);
398  ideal ires=maxideal(1);
399  ires[k]=i[1]+var(k);
400  return(ires);
401}
402example
403{ "EXAMPLE:"; echo = 2;
404   ring  r = 0,(x,y,z),lp;
405   ideal i = randomLast(10);
406   i;
407}
408///////////////////////////////////////////////////////////////////////////////
409
410proc randomBinomial(int k, int u, list #)
411"USAGE:   randomBinomial(k,u[,o,b]);  k,u,o,b integers
412RETURN:  binomial ideal, k homogeneous generators of degree d, u<=d<=o, with
413         randomly choosen monomials and coefficients in the interval [-b,b]
414         (default: u=o, b=10).
415EXAMPLE: example randomBinomial; shows an example
416"
417{
418//----------------------------- set defaults ----------------------------------
419   if( size(#)>=2 ) { int o=#[1]; int b=#[2]; }
420   if( size(#)==1 ) { int o=#[1]; int b=10; }
421   if( size(#)==0 ) { int o=u; int b=10; }
422//------------------ use sparsemat for creation of sparseid -------------------
423   ideal i,m;
424   int ii,jj,s,r1,r2;
425   if ( o<u ) { o=u; }
426   int a = k div (o-u+1);
427   int c = k mod (o-u+1);
428   for ( ii = u; ii<=o; ii++ )
429   { m = maxideal(ii);
430     s = size(m);
431     for ( jj=1; jj<=a; jj++ )
432     { r1 = random(-b,b);
433       r1 = r1 + (r1==0)*random(1,b);
434       r2 = random(-b,b);
435       r2 = r2 + (r2==0)*random(-b,-1);
436       i = i,r1*m[random(1,s/2)] + r1*m[random(s/2+1,s)];
437       if ( ii < c+u )
438       {  r1 = random(-b,b);
439          r1 = r1 + (r1==0)*random(1,b);
440          r2 = random(-b,b);
441          r2 = r2 + (r2==0)*random(-b,-1);
442          i = i,r1*m[random(1,s/2)] + r2*m[random(s/2+1,s)];
443       }
444     }
445   }
446   i = i[2..k+1];
447   return(i);
448}
449example
450{ "EXAMPLE:"; echo = 2;
451   ring  r = 0,(x,y,z),lp;
452   ideal i = randomBinomial(4,5,6);
453   i;
454}
455///////////////////////////////////////////////////////////////////////////////
Note: See TracBrowser for help on using the repository browser.