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

  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 12 years ago.
random_monomial.py (6.6 KB) - added by malb 12 years ago.
random-malb.txt (11.3 KB) - added by dfdeshom 12 years ago.
random-malb.hg (3.0 KB) - added by dfdeshom 12 years ago.
random_element.hg (29.6 KB) - added by malb 12 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 12 years ago by dfdeshom

  • Status changed from new to assigned
  • Summary changed from random_element() for multivariate polynomials to [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 follow-up: Changed 12 years ago by 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?

comment:3 Changed 12 years ago by was

  • Milestone changed from sage-2.9 to sage-2.8.10

comment:4 Changed 12 years ago by was

  • Component changed from algebraic geometry to basic arithmetic

Changed 12 years ago by dfdeshom

comment:5 in reply to: ↑ 2 Changed 12 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 12 years ago by dfdeshom

  • Cc dfdeshom@… added

comment:7 follow-ups: Changed 12 years ago by 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.

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 malb

comment:8 Changed 12 years ago by malb

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

comment:9 in reply to: ↑ 7 Changed 12 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 12 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 12 years ago by dfdeshom

comment:11 Changed 12 years ago by mabshoff

  • Milestone changed from sage-2.9 to sage-2.8.13

comment:12 Changed 12 years ago by cwitty

  • 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 dfdeshom

comment:13 Changed 12 years ago by dfdeshom

  • 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 malb

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

comment:15 Changed 12 years ago by rlm

  • 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 rlm

  • Resolution fixed deleted
  • Status changed from closed to reopened

unmerged.

comment:17 Changed 12 years ago by rlm

  • 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 robertwb

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 robertwb

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 follow-up: Changed 12 years ago by robertwb

  • 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 malb

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 12 years ago by malb

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

comment:22 Changed 12 years ago by malb

  • 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 cwitty

  • 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 mabshoff

  • Resolution set to fixed
  • Status changed from reopened to closed

Merged random_element.hg in Sage 2.10.1.rc1

Note: See TracTickets for help on using tickets.