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