Ticket #12846 (closed defect: duplicate)

Opened 13 months ago

Last modified 9 months ago

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 Work issues:
Report Upstream: Fixed upstream, in a later stable release. Reviewers: Jeroen Demeyer
Authors: Merged in:
Dependencies: Stopgaps:

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

comment:1 Changed 13 months ago by malb

  • Type changed from PLEASE CHANGE to defect

comment:3 Changed 13 months ago by zimmerma

  • Cc zimmerma added

comment:4 Changed 13 months 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 12 months ago by roed

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

comment:6 Changed 12 months 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 10 months 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 10 months ago by jdemeyer

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

comment:9 Changed 10 months ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:10 Changed 9 months ago by jdemeyer

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