Opened 15 years ago

Closed 15 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: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

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

  1. 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)

rand-poly.txt (2.1 KB) - added by dfdeshom 15 years ago.
random_monomial.py (6.6 KB) - added by Martin Albrecht 15 years ago.
random-malb.txt (11.3 KB) - added by dfdeshom 15 years ago.
random-malb.hg (3.0 KB) - added by dfdeshom 15 years ago.
random_element.hg (29.6 KB) - added by Martin Albrecht 15 years ago.
new bundle against 2.9.2 which fixes the default parameter remark by robertwb

Download all attachments as: .zip

Change History (29)

comment:1 Changed 15 years ago by dfdeshom

Status: newassigned
Summary: random_element() for multivariate polynomials[with patch] random_element() for multivariate polynomials

I've atached a patch. The individual degree distribution is a little better:

sage: f=ZZ['q,w,e,r,t,y'].random_element(degree=5,terms=9) ;f
 3*q^5 - q^4*w + 2*q^3*w^2 + q^2*w^3 - q*w^3*e + q^2*w*r*t + 2*q*w*e*r*t + q^2*e*t^2 + 8*r^2*t^2*y
sage: f=ZZ['q,w,e,r,t,y'].random_element(degree=4,terms=9) ;f
 q^2*w*e + q*w^2*r + q^2*r^2 - 24*w^3*t - 4*q^2*e*t - 5*t^4 - 4*q^3 + 2*q^2*w

comment:2 Changed 15 years ago by Martin Albrecht

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 15 years ago by William Stein

Milestone: sage-2.9sage-2.8.10

comment:4 Changed 15 years ago by William Stein

Component: algebraic geometrybasic arithmetic

Changed 15 years ago by dfdeshom

Attachment: rand-poly.txt added

comment:5 in reply to:  2 Changed 15 years ago by dfdeshom

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 15 years ago by dfdeshom

Cc: dfdeshom@… added

comment:7 Changed 15 years ago by Martin Albrecht

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 15 years ago by Martin Albrecht

Attachment: random_monomial.py added

comment:8 Changed 15 years ago by Martin Albrecht

Whoops, it is called random_monomial.py instead of random_element.py

comment:9 in reply to:  7 Changed 15 years ago by dfdeshom

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 15 years ago by dfdeshom

Replying to malb:

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.

If you don't mind, I've attached a patch against 2.8.11 for this. The patch is named random-malb.txt

Changed 15 years ago by dfdeshom

Attachment: random-malb.txt added

comment:11 Changed 15 years ago by Michael Abshoff

Milestone: sage-2.9sage-2.8.13

comment:12 Changed 15 years ago by Carl Witty

Summary: [with patch] random_element() for multivariate polynomials[with broken patch] random_element() for multivariate polynomials

Unfortunately, random-malb.txt no longer applies against sage-2.8.14.

Changed 15 years ago by dfdeshom

Attachment: random-malb.hg added

comment:13 Changed 15 years ago by dfdeshom

Summary: [with broken patch] random_element() for multivariate polynomials[with patch] random_element() for multivariate polynomials

I've added an hg bundle against 2.8.14

comment:14 Changed 15 years ago by Martin Albrecht

Uploaded bundle which applies against 2.9.alpha7 and doctests pass.

comment:15 Changed 15 years ago by Robert Miller

Resolution: fixed
Status: assignedclosed
Summary: [with patch] random_element() for multivariate polynomials[with patch, positive review] random_element() for multivariate polynomials

random_element.hg merged in 2.9.1 alpha2

comment:16 Changed 15 years ago by Robert Miller

Resolution: fixed
Status: closedreopened

unmerged.

comment:17 Changed 15 years ago by Robert Miller

Summary: [with patch, positive review] random_element() for multivariate polynomials[with patch, awaiting review] random_element() for multivariate polynomials

Robert Bradshaw is currently reviewing this

comment:18 Changed 15 years ago by Robert Bradshaw

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 15 years ago by Robert Bradshaw

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:

  1. (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.
  1. (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 Changed 15 years ago by Robert Bradshaw

Summary: [with patch, awaiting review] random_element() for multivariate polynomials[with patch, with negative review] random_element() for multivariate polynomials

comment:21 in reply to:  20 Changed 15 years ago by Martin Albrecht

Replying to robertwb:

  1. (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 15 years ago by Martin Albrecht

Attachment: random_element.hg added

new bundle against 2.9.2 which fixes the default parameter remark by robertwb

comment:22 Changed 15 years ago by Martin Albrecht

Priority: minormajor
Summary: [with patch, with negative review] random_element() for multivariate polynomials[with patch, needs review] random_element() for multivariate polynomials

comment:23 Changed 15 years ago by Carl Witty

Summary: [with patch, needs review] random_element() for multivariate polynomials[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 15 years ago by Michael Abshoff

Resolution: fixed
Status: reopenedclosed

Merged random_element.hg in Sage 2.10.1.rc1

Note: See TracTickets for help on using tickets.