Opened 10 years ago

Closed 10 years ago

#9108 closed defect (fixed)

Mark long doctests in rings/polynomial/symmetric_ideal

Reported by: leif Owned by: malb
Priority: minor Milestone: sage-4.4.4
Component: commutative algebra Keywords: time-out, doctest, symmetric ideal, symmetric_ideal
Cc: SimonKing, cremona Merged in: sage-4.4.4.alpha0
Authors: Leif Leonhardy Reviewers: John Cremona, Simon King
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by SimonKing)

Two doctests/examples in sage/rings/polynomial/symmetric_ideal.py tend to time out on older/slower machines (and take a large amount of the overall test time of that module).

Can you say which one? Then I'll either try shorter tests (which might actually be quite instructive, like a principal symmetric ideal whose minimal symmetric Groebner basis is formed by quite many polynomials) or mark the offensive tests as long.

Attachments (1)

trac_9108-mark_long_doctests_in_symmetric_ideal.patch (2.5 KB) - added by leif 10 years ago.
Marks the offending lines with # long time. Based on 4.4.3.alpha0.

Download all attachments as: .zip

Change History (15)

comment:1 in reply to: ↑ description Changed 10 years ago by SimonKing

  • Description modified (diff)

Replying to leif:

Two doctests/examples in sage/rings/polynomial/symmetric_ideal.py tend to time out on older/slower machines (and take a large amount of the overall test time of that module).

Changed 10 years ago by leif

Marks the offending lines with # long time. Based on 4.4.3.alpha0.

comment:2 Changed 10 years ago by leif

  • Status changed from new to needs_review

Simon, you're too fast... ;-)

I've just uploaded a patch that reduces the module test time on a Pentium 4 (Prescott, 3.2 GHz) from 238.7 seconds to 33.1 seconds.

comment:3 Changed 10 years ago by leif

Perhaps you could add less demanding tests. ;-)

Also, some docstring lines are "too long". (I personally don't mind source code that exceeds 80 columns, but the help output should perhaps be limited to 80 characters in width.)

comment:4 Changed 10 years ago by leif

  • Cc cremona added

comment:5 follow-up: Changed 10 years ago by cremona

  • Status changed from needs_review to positive_review

Before applying the patch to 4.4.3.alpha0:

jec@selmer%sage -t sage/rings/polynomial/symmetric_ideal.py 
sage -t  "sage/rings/polynomial/symmetric_ideal.py"         
	 [110.8 s]
 
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 110.8 seconds
jec@selmer%sage -t -long sage/rings/polynomial/symmetric_ideal.py 
sage -t -long "sage/rings/polynomial/symmetric_ideal.py"    
	 [109.8 s]
 
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 109.8 seconds

and after:

jec@selmer%sage -t sage/rings/polynomial/symmetric_ideal.py sage -t  "sage/rings/polynomial/symmetric_ideal.py"         
	 [16.5 s]
 
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 16.5 seconds
jec@selmer%sage -t -long sage/rings/polynomial/symmetric_ideal.py sage -t -long "sage/rings/polynomial/symmetric_ideal.py"    
	 [108.2 s]
 
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 108.2 seconds

Interesting to note that it is essentially just one test which takes the time!

comment:6 in reply to: ↑ 5 ; follow-ups: Changed 10 years ago by SimonKing

Replying to cremona:

Interesting to note that it is essentially just one test which takes the time!

Off list, Leif just sent me some timings:

There is one symmetric Groebner basis computation that takes 73 seconds, but most of the time is actually spent for testing whether all variable permutations of all basis elements do indeed have symmetric reduction zero modulo the symmetric Groebner basis: 130 s.

I see two ways to proceed, depending on how soon the next release is due:

  1. Leif's patch could go in, as John gave it a positive review, and it is certainly harmless and solves the problem.
  2. I could try to find a solution for the one offending doc test. For example, the long Groebner basis computation could be replaced by something else, such us the following, of course without the timings that I just inserted for demonstration:
    sage: R.<x,y> = InfinitePolynomialRing(GF(5),order='degrevlex')
    sage: I = [2*x[4]*x[3]*y[4] - 2*y[0]^3]*R
    sage: %time G = I.groebner_basis()
    CPU times: user 1.70 s, sys: 0.01 s, total: 1.71 s
    Wall time: 1.71 s
    sage: G
    [x_2*x_1*y_1 - y_0^3, x_2*x_1*y_2 - y_0^3, y_2*y_0^3 - y_1*y_0^3]
    sage: %time [[(p^P).reduce(G) for p in G] for P in Permutations(Integer(3))]
    CPU times: user 1.38 s, sys: 0.00 s, total: 1.38 s
    Wall time: 1.38 s
    [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
    

I think this example would actually be a good one, as it shows:

  • Even a "principal" symmetric ideal may have a reduced symmetric Groebner basis formed by more than one element.
  • The test whether the elements still reduce to zero after variable permutation is easier, since the maximal variable index can be smaller (3 instead of 4; it should be bigger than the maximal index 2 that occurs in the symmetric Groebner basis).

So, if the next release will be soon, I suggest to take Leif's patch as it is. But I think in the long run, a new example (like the one above) is needed.

Concerning line lengths: Does this only concern the first line of the doc strings? I know that my first lines tend to be rather lengthy, as I learnt that the basic description of the functionality should be given in the first line of the doc string (this is why I don't do a line wrap).

comment:7 Changed 10 years ago by leif

Replying to cremona:

[...] Interesting to note that it is essentially just one test which takes the time!

Actually two lines/tests take very long:

line#  walltime statement (preparsed)
[0116  72.980s] J=I.groebner_basis()
[0135 130.070s] [[(p**P).reduce(J) for p in J] for P in Permutations(Integer(4))]

(of a total of ~240s on that system)

Note that line numbers slightly change after applying the patch.

comment:8 in reply to: ↑ 6 Changed 10 years ago by SimonKing

Replying to SimonKing:

I think this example would actually be a good one, as it shows:

Or perhaps not that good...

The generator is not minimally chosen in its orbit, and I don't like that the second summand has index zero. But I recently did a series of random examples in order to test how large a symmetric Groebner basis of a symmetric ideal generated by a single small polynomial can actually be, so, it is likely that I'll find a better one.

comment:9 in reply to: ↑ 6 ; follow-up: Changed 10 years ago by leif

Replying to SimonKing:

So, if the next release will be soon, I suggest to take Leif's patch as it is. But I think in the long run, a new example (like the one above) is needed.

Feel free to add additional (short) tests... ;-)

Perhaps on another ticket?

Concerning line lengths: Does this only concern the first line of the doc strings? I know that my first lines tend to be rather lengthy, as I learnt that the basic description of the functionality should be given in the first line of the doc string (this is why I don't do a line wrap).

I just noticed that e.g. some parameter description lines are wider (net width).

Also, some are "marked" (optional); the current practice seems to be repeating the default value from the function definition, too, i.e.

    ``param`` -- (type, default: some_value) further description...

comment:10 in reply to: ↑ 9 Changed 10 years ago by SimonKing

Replying to leif:

Replying to SimonKing:

So, if the next release will be soon, I suggest to take Leif's patch as it is. But I think in the long run, a new example (like the one above) is needed.

Feel free to add additional (short) tests... ;-)

Perhaps on another ticket?

Seems reasonable. So, for now, the solution is to skip the long test unless it is wanted, and on a different ticket, I'll try to replace the offensive example (not add an example) and will also deal with the line length etc.

Thank you for your patch!

comment:11 Changed 10 years ago by cremona

I am quite happy with the the conclusion to this discussion! John

comment:12 Changed 10 years ago by SimonKing

I created a new ticket #9114 (ready for review) that replaces the offensive test by something better, and also improves the formatting of the documentation of "infinite polynomial rings and friends".

Since Leif's patch already has a positive review, I based #9114 on it.

comment:13 Changed 10 years ago by mhansen

  • Authors set to Leif Leonhardy
  • Merged in set to sage-4.4.4.alpha0
  • Reviewers set to John Cremona, Simon King

comment:14 Changed 10 years ago by mhansen

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.