1 | // $Id: random.lib,v 1.8 1999-07-26 13:03:35 Singular Exp $ |
---|
2 | //system("random",787422842); |
---|
3 | //(GMG/BM, last modified 22.06.96) |
---|
4 | /////////////////////////////////////////////////////////////////////////////// |
---|
5 | |
---|
6 | version="$Id: random.lib,v 1.8 1999-07-26 13:03:35 Singular Exp $"; |
---|
7 | info=" |
---|
8 | LIBRARY: random.lib PROCEDURES OF RANDOM MATRIX AND POLY OPERATIONS |
---|
9 | |
---|
10 | genericid(id[,p,b]); generic sparse linear combinations of generators of id |
---|
11 | randomid(id,[k,b]); random linear combinations of generators of id |
---|
12 | randommat(n,m[,id,b]); nxm matrix of random linear combinations of id |
---|
13 | sparseid(k,u[,o,p,b]); ideal of k random sparse poly's of degree d [u<=d<=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 | randomLast(b); random transformation of the last variable |
---|
18 | randomBinomial(k,u[,.]); binomial ideal, k random generators of degree >=u |
---|
19 | (parameters in square brackets [] are optional) |
---|
20 | "; |
---|
21 | |
---|
22 | LIB "inout.lib"; |
---|
23 | LIB "general.lib"; |
---|
24 | /////////////////////////////////////////////////////////////////////////////// |
---|
25 | |
---|
26 | proc genericid (id, list #) |
---|
27 | "USAGE: genericid(id,[,p,b]); id ideal/module, k,p,b integers |
---|
28 | RETURN: system of generators of id which are generic, sparse, triagonal linear |
---|
29 | combinations of given generators with coefficients in [1,b] and |
---|
30 | sparsety p percent, bigger p being sparser (default: p=75, b=30000) |
---|
31 | NOTE: For performance reasons try small bound b in characteristic 0 |
---|
32 | EXAMPLE: example genericid; shows an example |
---|
33 | " |
---|
34 | { |
---|
35 | //----------------------------- set defaults ---------------------------------- |
---|
36 | if( size(#)>=2 ) { int p=#[1]; int b=#[2]; } |
---|
37 | if( size(#)==1 ) { int p=#[1]; int b=30000} |
---|
38 | if( size(#)==0 ) { int p=75; int b=30000; } |
---|
39 | //---------------- use sparsetriag for creation of genericid ------------------ |
---|
40 | def i = simplify(id,10); |
---|
41 | i = i*sparsetriag(ncols(i),ncols(i),p,b); |
---|
42 | return(i); |
---|
43 | } |
---|
44 | example |
---|
45 | { "EXAMPLE:"; echo = 2; |
---|
46 | ring r=0,(t,x,y,z),ds; |
---|
47 | ideal i= x3+y4,z4+yx,t+x+y+z; |
---|
48 | genericid(i,0,10); |
---|
49 | module m=[x,0,0,0],[0,y2,0,0],[0,0,z3,0],[0,0,0,t4]; |
---|
50 | print(genericid(m)); |
---|
51 | } |
---|
52 | /////////////////////////////////////////////////////////////////////////////// |
---|
53 | |
---|
54 | proc randomid (id, list #) |
---|
55 | "USAGE: randomid(id,[k,b]); id ideal/module, b,k integers |
---|
56 | RETURN: ideal/module having k generators which are random linear combinations |
---|
57 | of generators of id with coefficients in the interval [-b,b] |
---|
58 | (default: b=30000, k=size(id)) |
---|
59 | NOTE: For performance reasons try small bound b in characteristic 0 |
---|
60 | EXAMPLE: example randomid; shows an example |
---|
61 | " |
---|
62 | { |
---|
63 | //----------------------------- set defaults ---------------------------------- |
---|
64 | if( size(#)>=2 ) { int k=#[1]; int b=#[2]; } |
---|
65 | if( size(#)==1 ) { int k=#[1]; int b=30000; } |
---|
66 | if( size(#)==0 ) { int k=size(id); int b=30000; } |
---|
67 | //--------------------------- create randomid --------------------------------- |
---|
68 | def i = id; |
---|
69 | i = matrix(id)*random(b,ncols(id),k); |
---|
70 | return(i); |
---|
71 | } |
---|
72 | example |
---|
73 | { "EXAMPLE:"; echo = 2; |
---|
74 | ring r=0,(x,y,z),dp; |
---|
75 | randomid(maxideal(2),2,9); |
---|
76 | module m=[x,0,1],[0,y2,0],[y,0,z3]; |
---|
77 | show(randomid(m)); |
---|
78 | } |
---|
79 | /////////////////////////////////////////////////////////////////////////////// |
---|
80 | |
---|
81 | proc randommat (int n, int m, list #) |
---|
82 | "USAGE: randommat(n,m[,id,b]); n,m,b integers, id ideal |
---|
83 | RETURN: nxm matrix, entries are random linear combinations of elements |
---|
84 | of id and coefficients in [-b,b] |
---|
85 | [default: (id,b) = (maxideal(1),30000)] |
---|
86 | NOTE: For performance reasons try small bound b in char 0 |
---|
87 | EXAMPLE: example randommat; shows an example |
---|
88 | " |
---|
89 | { |
---|
90 | //----------------------------- set defaults ---------------------------------- |
---|
91 | if( size(#)>=2 ) { ideal id=#[1]; int b=#[2]; } |
---|
92 | if( size(#)==1 ) { ideal id=#[1]; int b=30000; } |
---|
93 | if( size(#)==0 ) { ideal id=maxideal(1); int b=30000; } |
---|
94 | //--------------------------- create randommat -------------------------------- |
---|
95 | id=simplify(id,2); |
---|
96 | int g=ncols(id); |
---|
97 | matrix rand[n][m]; matrix ra[1][m]; |
---|
98 | for (int k=1; k<=n; k=k+1) |
---|
99 | { |
---|
100 | ra = id*random(b,g,m); |
---|
101 | rand[k,1..m]=ra[1,1..m]; |
---|
102 | } |
---|
103 | return(rand); |
---|
104 | } |
---|
105 | example |
---|
106 | { "EXAMPLE:"; echo = 2; |
---|
107 | ring r=0,(x,y,z),dp; |
---|
108 | matrix A=randommat(3,3,maxideal(2),9); |
---|
109 | print(A); |
---|
110 | A=randommat(2,3); |
---|
111 | print(A); |
---|
112 | } |
---|
113 | /////////////////////////////////////////////////////////////////////////////// |
---|
114 | |
---|
115 | proc sparseid (int k, int u, list #) |
---|
116 | "USAGE: sparseid(k,u[,o,p,b]); k,u,o,p,b integers |
---|
117 | RETURN: ideal having k generators in each degree d, u<=d<=o, p percent of |
---|
118 | terms in degree d are 0, the remaining have random coefficients |
---|
119 | in the interval [1,b], (default: o=u=d, p=75, b=30000) |
---|
120 | EXAMPLE: example sparseid; shows an example |
---|
121 | " |
---|
122 | { |
---|
123 | //----------------------------- set defaults ---------------------------------- |
---|
124 | if( size(#)>=3 ) { int o=#[1]; int p=#[2]; int b=#[3]; } |
---|
125 | if( size(#)==2 ) { int o=#[1]; int p=#[2]; int b=30000; } |
---|
126 | if( size(#)==1 ) { int o=#[1]; int p=75; int b=30000; } |
---|
127 | if( size(#)==0 ) { int o=u; int p=75; int b=30000; } |
---|
128 | //------------------ use sparsemat for creation of sparseid ------------------- |
---|
129 | int ii; ideal i; intmat m; |
---|
130 | for ( ii=u; ii<=o; ii=ii+1) |
---|
131 | { |
---|
132 | m = sparsemat(size(maxideal(ii)),k,p,b); |
---|
133 | i = i+ideal(matrix(maxideal(ii))*m); |
---|
134 | } |
---|
135 | return(i); |
---|
136 | } |
---|
137 | example |
---|
138 | { "EXAMPLE:"; echo = 2; |
---|
139 | ring r = 0,(a,b,c,d),ds; |
---|
140 | sparseid(3,4);""; |
---|
141 | sparseid(2,2,5,90,9); |
---|
142 | } |
---|
143 | /////////////////////////////////////////////////////////////////////////////// |
---|
144 | |
---|
145 | proc sparsemat (int n, int m, list #) |
---|
146 | "USAGE: sparsemat(n,m[,p,b]); n,m,p,b integers |
---|
147 | RETURN: nxm integer matrix, p percent of the entries are 0, the remaining |
---|
148 | are random coefficients >=1 and <= b; [defaults: (p,b) = (75,1)] |
---|
149 | EXAMPLE: example sparsemat; shows an example |
---|
150 | " |
---|
151 | { |
---|
152 | int r,h,ii; |
---|
153 | int t = n*m; |
---|
154 | intmat v[1][t]; |
---|
155 | //----------------------------- set defaults ---------------------------------- |
---|
156 | if( size(#)>=2 ) { int p=#[1]; int b=#[2]; } |
---|
157 | if( size(#)==1 ) { int p=#[1]; int b=1; } |
---|
158 | if( size(#)==0 ) { int p=75; int b=1; } |
---|
159 | //------------------------- check trivial cases ------------------------------ |
---|
160 | if( p<0 ) { p = 0; } |
---|
161 | if(p>100) { p=100; } |
---|
162 | //--------------- this is faster for not very sparse matrices ---------------- |
---|
163 | if( p<40 ) |
---|
164 | { |
---|
165 | for( ii=1; ii<=t; ii=ii+1 ) |
---|
166 | { r=( random(1,100)>p ); v[1,ii]=r*random(1,b); h=h+r; } |
---|
167 | } |
---|
168 | int bb = t*(100-p); |
---|
169 | if( 100*h > bb ) |
---|
170 | { |
---|
171 | while( 100*h > bb ) |
---|
172 | { r=random(1,t); h=h-( v[1,r]>0 ); v[1,r]=0; } |
---|
173 | } |
---|
174 | else |
---|
175 | { |
---|
176 | //------------------- this is faster for sparse matrices --------------------- |
---|
177 | while ( 100*h < bb ) |
---|
178 | { r=random(1,t); h=h+(v[1,r]==0); v[1,r]=random(1,b); } |
---|
179 | } |
---|
180 | intmat M[n][m] = v[1,1..t]; |
---|
181 | return(M); |
---|
182 | } |
---|
183 | example |
---|
184 | { "EXAMPLE:"; echo = 2; |
---|
185 | sparsemat(5,5);""; |
---|
186 | sparsemat(5,5,95);""; |
---|
187 | sparsemat(5,5,5);""; |
---|
188 | sparsemat(5,5,50,100); |
---|
189 | } |
---|
190 | /////////////////////////////////////////////////////////////////////////////// |
---|
191 | |
---|
192 | proc sparsepoly (int u, list #) |
---|
193 | "USAGE: sparsepoly(u[,o,p,b]); u,o,p,b integers |
---|
194 | RETURN: poly having only terms in degree d, u<=d<=o, p percent of the terms |
---|
195 | in degree d are 0, the remaining have random coefficients in [1,b), |
---|
196 | (defaults: o=u=d, p=75, b=30000) |
---|
197 | EXAMPLE: example sparsepoly; shows an example |
---|
198 | " |
---|
199 | { |
---|
200 | //----------------------------- set defaults ---------------------------------- |
---|
201 | if( size(#)>=3 ) { int o=#[1]; int p=#[2]; int b=#[3]; } |
---|
202 | if( size(#)==2 ) { int o=#[1]; int p=#[2]; int b=30000; } |
---|
203 | if( size(#)==1 ) { int o=#[1]; int p=75; int b=30000; } |
---|
204 | if( size(#)==0 ) { int o=u; int p=75; int b=30000; } |
---|
205 | int ii; poly f; |
---|
206 | //----------------- use sparseid for creation of sparsepoly ------------------- |
---|
207 | for( ii=u; ii<=o; ii=ii+1 ) { f=f+sparseid(1,ii,ii,p,b)[1]; } |
---|
208 | return(f); |
---|
209 | } |
---|
210 | example |
---|
211 | { "EXAMPLE:"; echo = 2; |
---|
212 | ring r=0,(x,y,z),dp; |
---|
213 | sparsepoly(5);""; |
---|
214 | sparsepoly(3,5,90,9); |
---|
215 | } |
---|
216 | /////////////////////////////////////////////////////////////////////////////// |
---|
217 | |
---|
218 | proc sparsetriag (int n, int m, list #) |
---|
219 | "USAGE: sparsetriag(n,m[,p,b]); n,m,p,b integers |
---|
220 | RETURN: nxm lower triagonal integer matrix, diagonal entries equal to 1, about |
---|
221 | p percent of lower diagonal entries are 0, the remaining are random |
---|
222 | integers >=1 and <= b; [defaults: (p,b) = (75,1)] |
---|
223 | EXAMPLE: example sparsetriag; shows an example |
---|
224 | " |
---|
225 | { |
---|
226 | int ii,min,l,r; intmat M[n][m]; |
---|
227 | int t=(n*(n-1)) div 2; |
---|
228 | //----------------------------- set defaults ---------------------------------- |
---|
229 | if( size(#)>=2 ) { int p=#[1]; int b=#[2]; } |
---|
230 | if( size(#)==1 ) { int p=#[1]; int b=1; } |
---|
231 | if( size(#)==0 ) { int p=75; int b=1; } |
---|
232 | //---------------- use sparsemat for creation of sparsetriag ------------------ |
---|
233 | intmat v[1][t]=sparsemat(1,t,p,b); |
---|
234 | if( n<=m ) { min=n-1; M[n,n]=1; } |
---|
235 | else { min=m; } |
---|
236 | for( ii=1; ii<=min; ii=ii+1 ) |
---|
237 | { |
---|
238 | l=r+1; r=r+n-ii; |
---|
239 | M[ii..n,ii]=1,v[1,l..r]; |
---|
240 | } |
---|
241 | return(M); |
---|
242 | } |
---|
243 | example |
---|
244 | { "EXAMPLE:"; echo = 2; |
---|
245 | sparsetriag(5,7);""; |
---|
246 | sparsetriag(7,5,90);""; |
---|
247 | sparsetriag(5,5,0);""; |
---|
248 | sparsetriag(5,5,50,100); |
---|
249 | } |
---|
250 | /////////////////////////////////////////////////////////////////////////////// |
---|
251 | |
---|
252 | proc randomLast(int b) |
---|
253 | "USAGE: randomLast(b); b int |
---|
254 | RETURN: ideal = maxideal(1), but the last variable is exchanged by a random |
---|
255 | linear combination of all variables, with coefficients in the |
---|
256 | interval [-b,b]. |
---|
257 | EXAMPLE: example randomLast; shows an example |
---|
258 | " |
---|
259 | { |
---|
260 | ideal i = maxideal(1); |
---|
261 | i[size(i)] = randomid(maxideal(1),1,b)[1]; |
---|
262 | return(i); |
---|
263 | } |
---|
264 | example |
---|
265 | { "EXAMPLE:"; echo = 2; |
---|
266 | ring r = 0,(x,y,z),lp; |
---|
267 | ideal i = randomLast(10); |
---|
268 | i; |
---|
269 | } |
---|
270 | /////////////////////////////////////////////////////////////////////////////// |
---|
271 | |
---|
272 | proc randomBinomial(int k, int u, list #) |
---|
273 | "USAGE: randomBinomial(k,u[,o,b]); k,u,o,b integers |
---|
274 | RETURN: binomial ideal, k homogeneous generators of degree d, u<=d<=o, with |
---|
275 | randomly choosen monomials and coefficients in the interval [-b,b] |
---|
276 | (default: u=o, b=10). |
---|
277 | EXAMPLE: example randomBinomial; shows an example |
---|
278 | " |
---|
279 | { |
---|
280 | //----------------------------- set defaults ---------------------------------- |
---|
281 | if( size(#)>=2 ) { int o=#[1]; int b=#[2]; } |
---|
282 | if( size(#)==1 ) { int o=#[1]; int b=10; } |
---|
283 | if( size(#)==0 ) { int o=u; int b=10; } |
---|
284 | //------------------ use sparsemat for creation of sparseid ------------------- |
---|
285 | ideal i,m; |
---|
286 | int ii,jj,s,r1,r2; |
---|
287 | if ( o<u ) { o=u; } |
---|
288 | int a = k div (o-u+1); |
---|
289 | int c = k mod (o-u+1); |
---|
290 | for ( ii = u; ii<=o; ii++ ) |
---|
291 | { m = maxideal(ii); |
---|
292 | s = size(m); |
---|
293 | for ( jj=1; jj<=a; jj++ ) |
---|
294 | { r1 = random(-b,b); |
---|
295 | r1 = r1 + (r1==0)*random(1,b); |
---|
296 | r2 = random(-b,b); |
---|
297 | r2 = r2 + (r2==0)*random(-b,-1); |
---|
298 | i = i,r1*m[random(1,s/2)] + r1*m[random(s/2+1,s)]; |
---|
299 | if ( ii < c+u ) |
---|
300 | { r1 = random(-b,b); |
---|
301 | r1 = r1 + (r1==0)*random(1,b); |
---|
302 | r2 = random(-b,b); |
---|
303 | r2 = r2 + (r2==0)*random(-b,-1); |
---|
304 | i = i,r1*m[random(1,s/2)] + r2*m[random(s/2+1,s)]; |
---|
305 | } |
---|
306 | } |
---|
307 | } |
---|
308 | i = i[2..k+1]; |
---|
309 | return(i); |
---|
310 | } |
---|
311 | example |
---|
312 | { "EXAMPLE:"; echo = 2; |
---|
313 | ring r = 0,(x,y,z),lp; |
---|
314 | ideal i = randomBinomial(4,5,6); |
---|
315 | i; |
---|
316 | } |
---|
317 | /////////////////////////////////////////////////////////////////////////////// |
---|