Opened 11 years ago

Closed 11 years ago

Last modified 11 years ago

#7587 closed enhancement (fixed)

improve multi_polynomial_libsingular exponent method

Reported by: ylchapuy Owned by: AlexGhitza
Priority: major Milestone: sage-4.3
Component: algebra Keywords:
Cc: SimonKing Merged in: sage-4.3.alpha1
Authors: Yann Laigle-Chapuy Reviewers: Simon King
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

The returned result is a list of ETuples, but for people interested in maximum speed it would be useful to provide an option to return plain tuples.

Attachments (1)

trac_7587-multi_polynomial_libsingular_exponents.patch (1.9 KB) - added by ylchapuy 11 years ago.
based on 4.3.alpha0

Download all attachments as: .zip

Change History (9)

Changed 11 years ago by ylchapuy

based on 4.3.alpha0

comment:1 Changed 11 years ago by ylchapuy

  • Cc SimonKing added
  • Status changed from new to needs_review

For the record:

sage: R = PolynomialRing(QQ,100,'x') 
sage: p = R.random_element(degree=50,terms=50)
sage: timeit('p.exponents()')
625 loops, best of 3: 1.02 ms per loop
sage: timeit('p.exponents(as_ETuples=False)')
625 loops, best of 3: 110 µs per loop

comment:2 Changed 11 years ago by SimonKing

  • Status changed from needs_review to positive_review

Hi Yann!

First good new: The patch cleanly applies to sage-4.3.alpha0.

Second good news: Using regular expressions (as explained here) seem to still be faster in my applications:

sage: Vars = ['x_'+str(n) for n in range(50)]+['y'+str(n) for n in range(50)]
sage: R = PolynomialRing(QQ,Vars)
sage: RE = re.compile('([a-zA-Z0-9]+)_([0-9]+)\^?([0-9]*)')
sage: p = R.random_element()
sage: p *= R.random_element()
sage: p *= R.random_element()
sage: p *= R.random_element()
sage: p *= R.random_element()
sage: p *= R.random_element()
sage: L = [(Vars[i],e) for i,e in enumerate(p.lm().exponents(as_ETuples=False)[0][:50]) if e]
sage: L
[('x_0', 1),
 ('x_2', 1),
 ('x_4', 1),
 ('x_5', 2),
 ('x_10', 1),
 ('x_42', 1),
 ('x_47', 1)]
sage: RE.findall(str(p.lm()))
[('x', '0', ''),
 ('x', '2', ''),
 ('x', '4', ''),
 ('x', '5', '2'),
 ('x', '10', ''),
 ('x', '42', ''),
 ('x', '47', '')]
sage: timeit('L = RE.findall(str(p.lm()))')
625 loops, best of 3: 25.1 µs per loop
sage: timeit('L = [(Vars[i],e) for i,e in enumerate(p.lm().exponents(as_ETuples=False)[0][:50]) if e] ')
625 loops, best of 3: 11.2 µs per loop

I can also confirm that the computation time with the as_ETuples=False option is reduced by 90%. So, I can give it a positive review.

comment:3 follow-ups: Changed 11 years ago by ylchapuy

Thanks for the review.

I don't understand why 25.1 µs is better than 11.2 µs though, but I might miss something.

comment:4 in reply to: ↑ 3 Changed 11 years ago by SimonKing

Replying to ylchapuy:

Thanks for the review.

I don't understand why 25.1 µs is better than 11.2 µs though, but I might miss something.

The 25.1 µs is for using regular expressions, the 11.2 µs is for using exponents(). 11.2 µs is certainly better than 25.1 µs!

In other words: With your patch, I can finally avoid the use of regular expressions!

Cheers, Simon

comment:5 Changed 11 years ago by SimonKing

  • Reviewers set to Simon King

comment:6 in reply to: ↑ 3 Changed 11 years ago by SimonKing

Replying to ylchapuy:

I don't understand why 25.1 µs is better than 11.2 µs though, but I might miss something.

After reading what I wrote in comment 2, I see that I must apologize. I started to write the comment when I had just used exponents without the as_ETuples=False option --- which was still slower than the regular expression. When I repeated it with the option, it was finally beating the regular expression --- but I forgot to edit the sentence on top of the example.

Sorry for the noise...

comment:7 Changed 11 years ago by mhansen

  • Merged in set to sage-4.3.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:8 Changed 11 years ago by mvngu

  • Milestone set to sage-4.3
Note: See TracTickets for help on using tickets.