Opened 10 years ago

Closed 10 years ago

#12846 closed defect (duplicate)

Multivariate Factorisation can be randomly slow (over extension fields)

Reported by: Martin Albrecht Owned by: tbd
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: factorization Keywords: singular
Cc: Paul Zimmermann Merged in:
Authors: Reviewers: Jeroen Demeyer
Report Upstream: Fixed upstream, in a later stable release. Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

The following code may take 1 second or not terminate in 1 minute, depending on random choices in the algorithm: 

sage: K=GF(4,'a')                                                          
sage: a=K.gens()[0]
sage: R.<x,y> = K[]
sage: f=(a + 1)*x^145*y^84 + (a + 1)*x^205*y^17 + x^32*y^112 + x^92*y^45
sage: time r=f.factor(proof=False)

Change History (10)

comment:1 Changed 10 years ago by Martin Albrecht

Type: PLEASE CHANGE → defect

comment:3 Changed 10 years ago by Paul Zimmermann

Cc: Paul Zimmermann added

comment:4 Changed 10 years ago by Paul Zimmermann

it seems upgrading to Singular 3-1-4-2 will solve this issue (see the thread in comment 2).

Paul

comment:5 Changed 10 years ago by David Roe

Report Upstream: Reported upstream. Little or no feedback. → Reported upstream. No feedback yet.

comment:6 Changed 10 years ago by Paul Zimmermann

Report Upstream: Reported upstream. No feedback yet. → Fixed upstream, but not in a stable release.

if you look at the comment from Martin Lee on April 24 at the thread pointed from comment 2, the problem is fixed in the Singular repository.

Paul

comment:7 Changed 10 years ago by Jeroen Demeyer

Fixed by #13237 (where the above command consistently takes less than 10ms, which is more than a factor 100 improvement).

comment:8 Changed 10 years ago by Jeroen Demeyer

Milestone: sage-wishlist → sage-duplicate/invalid/wontfix
Report Upstream: Fixed upstream, but not in a stable release. → Fixed upstream, in a later stable release.
Reviewers: → Jeroen Demeyer
Status: new → needs_review

comment:9 Changed 10 years ago by Jeroen Demeyer

Status: needs_review → positive_review

comment:10 Changed 10 years ago by Jeroen Demeyer

Resolution: → duplicate
Status: positive_review → closed
Note: See TracTickets for help on using tickets.