source: git/Singular/LIB/random.lib @ 3d124a7

spielwiese
Last change on this file since 3d124a7 was 3d124a7, checked in by Olaf Bachmann <obachman@…>, 27 years ago
This commit was generated by cvs2svn to compensate for changes in r191, which included commits to RCS files with non-trunk default branches. git-svn-id: file:///usr/local/Singular/svn/trunk@192 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 8.8 KB
Line 
1// $Id: random.lib,v 1.1.1.1 1997-04-25 15:13:26 obachman Exp $
2//system("random",787422842);
3//(GMG+BM)
4///////////////////////////////////////////////////////////////////////////////
5
6LIBRARY:  random.lib    PROCEDURES OF RANDOM MATRIX AND POLY OPERATIONS
7
8 genericid(id[,p,b]);   generic sparse linear combinations of generators of id
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 sparsemat(n,m[,p,b]);  nxm sparse integer matrix with random coefficients
13 sparsepoly(u[,o,p,b]); random sparse polynomial with terms of degree in [u,o]
14 sparsetriag(n,m[..]);  nxm sparse lower-triag intmat with random coefficients
15           (parameters in square brackets [] are optional)
16
17LIB "inout.lib";
18LIB "general.lib";
19////////////////////////////////////////////////////////////////////////////////
20
21proc genericid (id, list #)
22USAGE:   genericid(id,[,p,b]);  id ideal/module, p,b integers
23RETURN:  system of generators of id which are generic, sparse, trigonal linear
24         combinations of given generators with coefficients in [1,b] and
25         sparsety p percent, bigger p being sparser (default: p=75, b=30000)
26NOTE:    For performance reasons try small bound b in characteristic 0
27EXAMPLE: example genericid; shows an example
28{
29//----------------------------- set defaults ----------------------------------
30   if( size(#)>=2 ) { int p=#[1]; int b=#[2]; }
31   if( size(#)==1 ) { int p=#[1]; int b=30000}
32   if( size(#)==0 ) { int p=75; int b=30000; }
33//---------------- use sparsetriag for creation of genericid ------------------
34   def i = simplify(id,10);                         
35   i = i*sparsetriag(ncols(i),ncols(i),p,b);
36   return(i);
37}               
38example
39{ "EXAMPLE:"; echo = 2;
40   ring r=0,(t,x,y,z),ds;
41   ideal i= x3+y4,z4+yx,t+x+y+z;         
42   genericid(i,0,10);         
43   module m=[x,0,0,0],[0,y2,0,0],[0,0,z3,0],[0,0,0,t4];
44   print(genericid(m));
45}
46////////////////////////////////////////////////////////////////////////////////
47
48proc randomid (id, list #)
49USAGE:   randomid(id,[k,b]);  id ideal/module, b,k integers
50RETURN:  ideal/module having k generators which are random linear combinations
51         of generators of id with coefficients in the interval [-b,b]
52         (default: b=30000, k=size(id))
53NOTE:    For performance reasons try small bound b in characteristic 0
54EXAMPLE: example randomid; shows an example
55{
56//----------------------------- set defaults ----------------------------------
57   if( size(#)>=2 ) { int k=#[1]; int b=#[2]; }
58   if( size(#)==1 ) { int k=#[1]; int b=30000; }
59   if( size(#)==0 ) { int k=size(id); int b=30000; }
60//--------------------------- create randomid ---------------------------------
61   def i = id;                         
62   i = matrix(id)*random(b,ncols(id),k);
63   return(i);
64}               
65example
66{ "EXAMPLE:"; echo = 2;
67   ring r=0,(x,y,z),dp;           
68   randomid(maxideal(2),2,9);         
69   module m=[x,0,1],[0,y2,0],[y,0,z3];
70   show(randomid(m));
71}
72////////////////////////////////////////////////////////////////////////////////
73
74proc randommat (int n, int m, list #)
75USAGE:   randommat(n,m[,id,b]);  n,m,b integers, id ideal
76RETURN:  nxm matrix, entries are random linear combinations of elements
77         of id and coefficients in [-b,b]
78         [default: (id,b) = (maxideal(1),30000)]
79NOTE:    For performance reasons try small bound b in char 0
80EXAMPLE:  example randommat; shows an example
81{
82//----------------------------- set defaults ----------------------------------
83   if( size(#)>=2 ) { ideal id=#[1]; int b=#[2]; }
84   if( size(#)==1 ) { ideal id=#[1]; int b=30000; }
85   if( size(#)==0 ) { ideal id=maxideal(1); int b=30000; }
86//--------------------------- create randommat --------------------------------
87   id=simplify(id,2);
88   int g=ncols(id);
89   matrix rand[n][m]; matrix ra[1][m];
90   for (int k=1; k<=n; k++)
91   {
92      ra = id*random(b,g,m);
93      rand[k,1..m]=ra[1,1..m];
94   }
95   return(rand);
96}
97example
98{ "EXAMPLE:"; echo = 2;
99   ring r=0,(x,y,z),dp;
100   matrix A=randommat(3,3,maxideal(2),9);
101   print(A);
102   A=randommat(2,3);
103   print(A);
104}               
105///////////////////////////////////////////////////////////////////////////////
106
107proc sparseid (int k, int u, list #)
108USAGE:   sparseid(k,u[,o,p,b]);  k,u,o,p,b integers
109RETURN:  ideal having k generators in each degree d, u<=d<=o, p percent of
110         terms in degree d are 0, the remaining have random coefficients
111         in the interval [1,b], (default: o=u=d, p=75, b=30000)
112EXAMPLE: example sparseid; shows an example
113{
114//----------------------------- set defaults ----------------------------------
115   if( size(#)>=3 ) { int o=#[1]; int p=#[2]; int b=#[3]; }
116   if( size(#)==2 ) { int o=#[1]; int p=#[2]; int b=30000; }
117   if( size(#)==1 ) { int o=#[1]; int p=75; int b=30000; }
118   if( size(#)==0 ) { int o=u; int p=75; int b=30000; }
119//------------------ use sparsemat for creation of sparseid -------------------
120   int ii; ideal i; intmat m;
121   for ( ii=u; ii<=o; ii++)
122   {
123       m = sparsemat(size(maxideal(ii)),k,p,b);
124       i = i+ideal(matrix(maxideal(ii))*m);
125   }
126   return(i);
127}
128example
129{ "EXAMPLE:"; echo = 2;
130   ring r = 0,(a,b,c,d),ds;
131   sparseid(3,4);"";
132   sparseid(2,2,5,90,9);
133}               
134///////////////////////////////////////////////////////////////////////////////
135
136proc sparsemat (int n, int m, list #)
137USAGE:   sparsemat(n,m[,p,b]);  n,m,p,b integers
138RETURN:  nxm integer matrix, p percent of the entries are 0, the remaining
139         are random coefficients >=1 and <= b; [defaults: (p,b) = (75,1)]
140EXAMPLE: example sparsemat; shows an example
141{
142   int r,h,ii;
143   int t = n*m;
144   intmat v[1][t];
145//----------------------------- set defaults ----------------------------------
146   if( size(#)>=2 ) { int p=#[1]; int b=#[2]; }
147   if( size(#)==1 ) { int p=#[1]; int b=1; }
148   if( size(#)==0 ) { int p=75; int b=1; }
149//------------------------- check trivial cases ------------------------------
150   if( p<0 ) { p = 0; }
151   if(p>100) { p=100; }
152//--------------- this is faster for not very sparse matrices ----------------
153   if( p<40 )
154   {
155      for( ii=1; ii<=t; ii++ )
156      { r=( random(1,100)>p ); v[1,ii]=r*random(1,b); h=h+r; }
157   }
158  int bb = t*(100-p);
159  if( 100*h > bb )
160  {
161     while( 100*h > bb )
162     { r=random(1,t); h=h-( v[1,r]>0 ); v[1,r]=0; }
163  }
164  else
165  {
166//------------------- this is faster for sparse matrices ---------------------
167     while ( 100*h < bb )
168     { r=random(1,t); h=h+(v[1,r]==0); v[1,r]=random(1,b); }
169  }
170  intmat M[n][m] = v[1,1..t];
171  return(M);
172}
173example
174{ "EXAMPLE:"; echo = 2;
175   sparsemat(5,5);
176   sparsemat(5,5,95);
177   sparsemat(5,5,5);
178   sparsemat(5,5,50,100);
179}               
180///////////////////////////////////////////////////////////////////////////////
181
182proc sparsepoly (int u, list #)
183USAGE:   sparsepoly(u[,o,p,b]);  u,o,p,b integers
184RETURN:  poly having only terms in degree d, u<=d<=o, p percent of the terms
185         in degree d are 0, the remaining have random coefficients in [1,b),
186         (defaults: o=u=d, p=75, b=30000)
187EXAMPLE:  example sparsepoly; shows an example
188{
189//----------------------------- set defaults ----------------------------------
190   if( size(#)>=3 ) { int o=#[1]; int p=#[2]; int b=#[3]; }
191   if( size(#)==2 ) { int o=#[1]; int p=#[2]; int b=30000; }
192   if( size(#)==1 ) { int o=#[1]; int p=75; int b=30000; }
193   if( size(#)==0 ) { int o=u; int p=75; int b=30000; }
194   int ii; poly f;
195//----------------- use sparseid for creation of sparsepoly -------------------
196   for( ii=u; ii<=o; ii++ ) { f=f+sparseid(1,ii,ii,p,b)[1]; }
197   return(f);
198}
199example
200{ "EXAMPLE:"; echo = 2;
201   ring r=0,(x,y,z),dp;
202   sparsepoly(5);"";
203   sparsepoly(3,5,90,9);
204}               
205///////////////////////////////////////////////////////////////////////////////
206
207proc sparsetriag (int n, int m, list #)
208USAGE:   sparsetriag(n,m[,p,b]);  n,m,p,b integers
209RETURN:  nxm lower triagonal integer matrix, diagonal entries equal to 1, about
210         p percent of lower diagonal entries are 0, the remaining are random
211         integers >=1 and <= b; [defaults: (p,b) = (75,1)]
212EXAMPLE: example sparsetriag; shows an example
213{
214   int ii,min,l,r; intmat M[n][m];
215   int t=(n*(n-1))/2;
216//----------------------------- set defaults ----------------------------------
217   if( size(#)>=2 ) { int p=#[1]; int b=#[2]; }
218   if( size(#)==1 ) { int p=#[1]; int b=1; }
219   if( size(#)==0 ) { int p=75; int b=1; }
220//---------------- use sparsemat for creation of sparsetriag ------------------
221   intmat v[1][t]=sparsemat(1,t,p,b);
222   if( n<=m ) { min=n-1; M[n,n]=1; }
223   else { min=m; }
224   for( ii=1; ii<=min; ii++ )
225   {
226      l=r+1; r=r+n-ii;
227      M[ii..n,ii]=1,v[1,l..r];
228   }
229   return(M);
230}
231example
232{ "EXAMPLE:"; echo = 2;
233   sparsetriag(5,7);
234   sparsetriag(7,5,90);
235   sparsetriag(5,5,0);
236   sparsetriag(5,5,50,100);
237}               
238///////////////////////////////////////////////////////////////////////////////
Note: See TracBrowser for help on using the repository browser.