Opened 15 years ago

Closed 15 years ago

#1617 closed defect (fixed)

[with patch, positive review] speed problem when factoring polynoms

Reported by: Harald Schilly Owned by: William Stein
Priority: major Milestone: sage-2.10.1
Component: commutative algebra Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

There is a huge speed difference. Any special reasons? A novice user would possibly not understand why!

var('x,y')
time p1=factor(x^99+y^99)

Time: CPU 0.05 s, Wall: 58.43 s


R.<x,y> = QQ[]
time p2=factor(x^99+y^99)

Time: CPU 0.06 s, Wall: 0.06 s

Attachments (1)

trac-1617.patch (4.0 KB) - added by William Stein 15 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 15 years ago by Michael Abshoff

Component: algebraic geometrycommutative algebra
Milestone: sage-2.9.2
Owner: changed from William Stein to Martin Albrecht

This is likely caused by using Maxima's factoring vs. Singular's libfactor. In the first case x and y are symbolic.

Cheers,

Michael

comment:2 Changed 15 years ago by Martin Albrecht

Summary: speed problem when factoring polynoms[wontfix?] speed problem when factoring polynoms

I vote for wontfix because I see no way of fixing this, this is a Maxima speed issue. The only fix I could think of is to add something about this in some documentation.

comment:3 Changed 15 years ago by William Stein

Owner: changed from Martin Albrecht to William Stein
Status: newassigned

Changed 15 years ago by William Stein

Attachment: trac-1617.patch added

comment:4 Changed 15 years ago by William Stein

Summary: [wontfix?] speed problem when factoring polynoms[with patch, needs review] speed problem when factoring polynoms

comment:5 Changed 15 years ago by Michael Abshoff

At least one comment is wrong in the patch since the "-" no longer shows up:

2288	2288	        Notice that the -1 factor is separated out: 
2289	2289	            sage: f.factor_list() 
2290	 	            [(-1, 1), (y - x, 1), (y^2 + x*y + x^2, 1)] 
 	2290	            [(x - y, 1), (y^2 + x*y + x^2, 1)] 

Cheers,

Michael

comment:6 Changed 15 years ago by ncalexan

Summary: [with patch, needs review] speed problem when factoring polynoms[with patch, needs review after #1391 is applied] speed problem when factoring polynoms

This patch could interact with #1391 (http://trac.sagemath.org/sage_trac/ticket/1391). That one should be applied first, I think, and then this looked at again.

comment:7 Changed 15 years ago by Martin Albrecht

Summary: [with patch, needs review after #1391 is applied] speed problem when factoring polynoms[with patch, positive review] speed problem when factoring polynoms

The patch applies to 2.10.1.alpha1 (hunks, but success). Afterwards, only the toy_buchberger.py tests fail which is unrelated. Thus, I say: apply.

comment:8 Changed 15 years ago by William Stein

The mabshoff comment above about "At least one comment is wrong in the patch since the "-" no longer shows up" was caused by ncalexan's patch related to factorization.py, which was after #1617.

comment:9 Changed 15 years ago by Michael Abshoff

Resolution: fixed
Status: assignedclosed

Merged in Sage 2.10.1.alpha2

Note: See TracTickets for help on using tickets.