Opened 13 years ago

Closed 13 years ago

Last modified 13 years ago

#7587 closed enhancement (fixed)

improve multi_polynomial_libsingular exponent method

Reported by: ylchapuy Owned by: Alex Ghitza
Priority: major Milestone: sage-4.3
Component: algebra Keywords:
Cc: Simon King 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 13 years ago.
based on 4.3.alpha0

Download all attachments as: .zip

Change History (9)

Changed 13 years ago by ylchapuy

based on 4.3.alpha0

comment:1 Changed 13 years ago by ylchapuy

Cc: Simon King added
Status: newneeds_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 13 years ago by Simon King

Status: needs_reviewpositive_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 Changed 13 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 13 years ago by Simon King

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 13 years ago by Simon King

Reviewers: Simon King

comment:6 in reply to:  3 Changed 13 years ago by Simon King

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 13 years ago by Mike Hansen

Merged in: sage-4.3.alpha1
Resolution: fixed
Status: positive_reviewclosed

comment:8 Changed 13 years ago by Minh Van Nguyen

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