# source:git/Singular/LIB/random.lib

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