Opened 9 years ago

Closed 9 years ago

#12846 closed defect (duplicate)

Multivariate Factorisation can be randomly slow (over extension fields)

Reported by: malb Owned by: tbd
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: factorization Keywords: singular
Cc: zimmerma 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 9 years ago by malb

  • Type changed from PLEASE CHANGE to defect

comment:3 Changed 9 years ago by zimmerma

  • Cc zimmerma added

comment:4 Changed 9 years ago by zimmerma

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

Paul

comment:5 Changed 9 years ago by roed

  • Report Upstream changed from Reported upstream. Little or no feedback. to Reported upstream. No feedback yet.

comment:6 Changed 9 years ago by zimmerma

  • Report Upstream changed from Reported upstream. No feedback yet. to 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 9 years ago by jdemeyer

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

comment:8 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-wishlist to sage-duplicate/invalid/wontfix
  • Report Upstream changed from Fixed upstream, but not in a stable release. to Fixed upstream, in a later stable release.
  • Reviewers set to Jeroen Demeyer
  • Status changed from new to needs_review

comment:9 Changed 9 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:10 Changed 9 years ago by jdemeyer

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