Opened 12 years ago
Closed 12 years ago
#980 closed defect (fixed)
[with patch, with positive review] random_element() for multivariate polynomials
Reported by: | dfdeshom | Owned by: | dfdeshom |
---|---|---|---|
Priority: | major | Milestone: | sage-2.10.1 |
Component: | basic arithmetic | Keywords: | |
Cc: | dfdeshom@… | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
There are 2 quirks about random multivariate polynomials outlined below:
1) Degrees are severely restricted:
The maximum degree in every variable is (maximum total degree of resulting polynomial) / (number of varialbes of the polynomial).
2) Too many zero elements. Polynomials generated are too sparse.
The second point is about the number of coefficients that are set to
- This might a point to argue about, but if I create a random
polynomial with a (maximum number of terms to generate) then I expect that the 0 occur
Attachments (5)
Change History (29)
comment:1 Changed 12 years ago by
- Status changed from new to assigned
- Summary changed from random_element() for multivariate polynomials to [with patch] random_element() for multivariate polynomials
comment:2 follow-up: ↓ 5 Changed 12 years ago by
Your patch seems to prefer variables with lower indexes, i.e. the probability that x in x,y,z has the highest degree is quite high because you are making the search space smaller for each variable. Maybe you could permute the exponent tuple randomly afterwards to take care of that bias?
comment:3 Changed 12 years ago by
- Milestone changed from sage-2.9 to sage-2.8.10
comment:4 Changed 12 years ago by
- Component changed from algebraic geometry to basic arithmetic
Changed 12 years ago by
comment:5 in reply to: ↑ 2 Changed 12 years ago by
Replying to malb:
Your patch seems to prefer variables with lower indexes, i.e. the probability that x in x,y,z has the highest degree is quite high because you are making the search space smaller for each variable. Maybe you could permute the exponent tuple randomly afterwards to take care of that bias?
Thanks. This also takes care of too many nonzero terms being generated. I've updated the patch
comment:6 Changed 12 years ago by
- Cc dfdeshom@… added
comment:7 follow-ups: ↓ 9 ↓ 10 Changed 12 years ago by
the attached file random_element.py
implements my proposal for this method. It is supposed to guarantee uniformly randomly chosen monomials per default and also supports to choose the degree randomly before choosing a monomial of that given degree.
NOTE: random_element.py
is not a patch but a py
file to load/attach into SAGE to test it. I will provide a proper patch if we agree on the strategy.
Changed 12 years ago by
comment:8 Changed 12 years ago by
Whoops, it is called random_monomial.py
instead of random_element.py
comment:9 in reply to: ↑ 7 Changed 12 years ago by
Replying to malb:
the attached file
random_element.py
implements my proposal for this method. It is supposed to guarantee uniformly randomly chosen monomials per default and also supports to choose the degree randomly before choosing a monomial of that given degree.
The general strategy is OK with me. One minor implementation nitpick: I would use ZZ.random_element() instead of randint() because it is faster.
comment:10 in reply to: ↑ 7 Changed 12 years ago by
Replying to malb:
NOTE:
random_element.py
is not a patch but apy
file to load/attach into SAGE to test it. I will provide a proper patch if we agree on the strategy.
If you don't mind, I've attached a patch against 2.8.11 for this. The patch is named random-malb.txt
Changed 12 years ago by
comment:11 Changed 12 years ago by
- Milestone changed from sage-2.9 to sage-2.8.13
comment:12 Changed 12 years ago by
- Summary changed from [with patch] random_element() for multivariate polynomials to [with broken patch] random_element() for multivariate polynomials
Unfortunately, random-malb.txt no longer applies against sage-2.8.14.
Changed 12 years ago by
comment:13 Changed 12 years ago by
- Summary changed from [with broken patch] random_element() for multivariate polynomials to [with patch] random_element() for multivariate polynomials
I've added an hg bundle against 2.8.14
comment:14 Changed 12 years ago by
Uploaded bundle which applies against 2.9.alpha7 and doctests pass.
comment:15 Changed 12 years ago by
- Resolution set to fixed
- Status changed from assigned to closed
- Summary changed from [with patch] random_element() for multivariate polynomials to [with patch, positive review] random_element() for multivariate polynomials
random_element.hg
merged in 2.9.1 alpha2
comment:16 Changed 12 years ago by
- Resolution fixed deleted
- Status changed from closed to reopened
unmerged.
comment:17 Changed 12 years ago by
- Summary changed from [with patch, positive review] random_element() for multivariate polynomials to [with patch, awaiting review] random_element() for multivariate polynomials
Robert Bradshaw is currently reviewing this
comment:18 Changed 12 years ago by
For the most part, this looks good, but it seems that your algorithm is flawed in some cases (e.g more than two variables?). For example:
sage: [QQ['x,y,z'].random_element() for _ in range(10)] [-2/3, 1/6, 2, -2/11, 1, 11/2, 1/3, -5, 1/3, 3] sage: [ZZ['x,y,z,w'].random_element() for _ in range(10)] [-1, -10, -1, -8, 1, 4, -32, 1, 1, -1]
It also has a bias against repeating variables in a monomial. None of these are of degree 7...
sage: [ZZ['x,y,z,w'].random_element(7,1) for _ in range(10)] [-1*w, y*z, -2*x*z*w, -22*x*y*w, -1*z, -5*x*y*w, 7*y*w, x*w, -2*y*z, 2*y*w]
comment:19 Changed 12 years ago by
Trying to understand why the good-looking code produced such bad results, I figured out that I had forgotten to merge, so ignore the previous comments.
There are only two things I'd change:
- (Minor) There are multiple uses of ZZ.random_element(min,max), especially used to compute degrees in the monomials. I would highly recommend using Python's randint from http://docs.python.org/lib/module-random.html for speed.
- (Blocker) Not having default arguments for random_element means it can't be used generically. For example:
sage: random_matrix(QQ['x,y,z'], 2, 2) ------------------------------------------------------------ Traceback (most recent call last): File "<ipython console>", line 1, in <module> File "/Users/robert/sage/current/local/lib/python2.5/site-packages/sage/matrix/constructor.py", line 503, in random_matrix A.randomize(density=density, *args, **kwds) File "matrix2.pyx", line 2752, in sage.matrix.matrix2.Matrix.randomize <type 'exceptions.TypeError'>: function takes at least 2 arguments (0 given)
It should not be necessary to special-case the basering being a multipolynomial element before calling random_element on it. Some default should be specified, even if it's degree and terms = 1+abs(ZZ.random_element()).
Even worse
sage: R = QQ['x,y'] sage: S = R['t,u'] sage: S.random_element(d=2, t=3) # BOOM
It is impossible to pass the required degree/number of terms arguments on to the basering of S.
comment:20 follow-up: ↓ 21 Changed 12 years ago by
- Summary changed from [with patch, awaiting review] random_element() for multivariate polynomials to [with patch, with negative review] random_element() for multivariate polynomials
comment:21 in reply to: ↑ 20 Changed 12 years ago by
Replying to robertwb:
- (Minor) There are multiple uses of ZZ.random_element(min,max), especially used
to compute degrees in the monomials. I would highly recommend using Python's randint from http://docs.python.org/lib/module-random.html for speed.
I cannot confirm this:
Sage Integers:
sage: l = 0 sage: u = 5 sage: %timeit randint(l,u) 10000 loops, best of 3: 31.1 µs per loop sage: %timeit ZZ.random_element(l,u) 100000 loops, best of 3: 2.63 µs per loop
Python Integers:
sage: l = int(0) sage: u = int(5) sage: %timeit randint(l,u) 100000 loops, best of 3: 7.65 µs per loop sage: %timeit ZZ.random_element(l,u) 100000 loops, best of 3: 7.25 µs per loop
What am I missing?
Changed 12 years ago by
new bundle against 2.9.2 which fixes the default parameter remark by robertwb
comment:22 Changed 12 years ago by
- Priority changed from minor to major
- Summary changed from [with patch, with negative review] random_element() for multivariate polynomials to [with patch, needs review] random_element() for multivariate polynomials
comment:23 Changed 12 years ago by
- Summary changed from [with patch, needs review] random_element() for multivariate polynomials to [with patch, with positive review] random_element() for multivariate polynomials
Looks good to me! doctests pass, Robert's issues with default arguments have been fixed.
comment:24 Changed 12 years ago by
- Resolution set to fixed
- Status changed from reopened to closed
Merged random_element.hg in Sage 2.10.1.rc1
I've atached a patch. The individual degree distribution is a little better: