Opened 13 years ago

Closed 12 years ago

#5338 closed defect (fixed)

Sage 3.2.2: speed regression/infinite loop for "K.<b> = QQ[a]"

Reported by: mabshoff Owned by: tbd
Priority: critical Milestone: sage-4.3
Component: algebra Keywords:
Cc: robertwb Merged in: sage-4.3.alpha1
Authors: William Stein Reviewers: Robert Bradshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

The code below works instantly in Sage 3.2.1, but starting with Sage 3.2.2 it doesn't even finish the last command in 30 minutes CPU time:

----------------------------------------------------------------------
| Sage Version 3.2.2, Release Date: 2008-12-18                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage:     sage: x = var('x')
sage:     sage: eqn =  x^3 + sqrt(2)*x + 5 == 0
sage:     sage: a = solve(eqn, x)[0].rhs()
sage:     sage: K.<b> = QQ[a]

Carl Witty suggests:

[10:23am] mabs: So far it has eaten *4 minutes* of CPU time.
[10:23am] cwitty: It looks like somebody changed the embedding 
system to use QQbar instead of wstein's algdep-of-numerical-value.

This is likely related to the new embedding code in Sage 3.2.2, so I am CCing RobertWB.

Cheers,

Michael

Attachments (1)

trac_5338.2.patch (4.0 KB) - added by was 12 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 13 years ago by robertwb

You can still access my old (numeric) minpoly code via

sage: x = var('x')
sage: eqn =  x^3 + sqrt(2)*x + 5 == 0
sage: a = solve(eqn, x)[0].rhs()
sage: a.minpoly(algorithm='numeric')
x^6 + 10*x^3 - 2*x^2 + 25

However, for many cases this is much slower or fails completely.

comment:2 follow-up: Changed 13 years ago by robertwb

Hmm, this is insanely slow (i.e. never finishes for me)

sage: b = (sqrt(sqrt(2) + 1)/(sqrt(3)) - 1)^(1/3)
sage: time QQbar(b).minpoly()

comment:3 Changed 13 years ago by mabshoff

Note that for now the doctest has been disabled to get the doctests to pass.

Cheers,

Michael

comment:4 Changed 13 years ago by AlexGhitza

  • Summary changed from Sage 3.2.2: speed regression/infite loop for "K.<b> = QQ[a]" to Sage 3.2.2: speed regression/infinite loop for "K.<b> = QQ[a]"

comment:5 in reply to: ↑ 2 ; follow-up: Changed 12 years ago by AlexGhitza

Replying to robertwb:

Hmm, this is insanely slow (i.e. never finishes for me)

sage: b = (sqrt(sqrt(2) + 1)/(sqrt(3)) - 1)^(1/3)
sage: time QQbar(b).minpoly()

The problem seems to be here:

sage: b = (sqrt(sqrt(2) + 1)/(sqrt(3)) - 1)^(1/3)
sage: c = QQbar(b)
sage: od = c._descr
sage: od.exactify()    # doesn't seem to finish

comment:6 in reply to: ↑ 5 Changed 12 years ago by cremona

Replying to AlexGhitza:

Replying to robertwb:

Hmm, this is insanely slow (i.e. never finishes for me)

sage: b = (sqrt(sqrt(2) + 1)/(sqrt(3)) - 1)^(1/3)
sage: time QQbar(b).minpoly()

The problem seems to be here:

sage: b = (sqrt(sqrt(2) + 1)/(sqrt(3)) - 1)^(1/3)
sage: c = QQbar(b)
sage: od = c._descr
sage: od.exactify()    # doesn't seem to finish

As far as I can see, the latter is getting into an infinite loop. If that is right, it's real bug and not just a new inefficiency.

comment:7 Changed 12 years ago by AlexGhitza

It seems that exactify is not the culprit, it's just a bit slow:

----------------------------------------------------------------------
| Sage Version 4.2, Release Date: 2009-10-24                         |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: b = (sqrt(sqrt(2) + 1)/(sqrt(3)) - 1)^(1/3)
sage: c = QQbar(b)
sage: od = c._descr
sage: time od.exactify()
CPU times: user 102.89 s, sys: 0.17 s, total: 103.06 s
Wall time: 117.04 s
-13576/8180757*a^23 + 833411/13634595*a^20 - 6092092/13634595*a^17 + 2402147/4544865*a^14 + 16778234/4544865*a^11 - 5085581/504985*a^8 + 2414627/302991*a^5 - 1318781/504985*a^2 where a^24 - 36*a^21 + 240*a^18 - 144*a^15 - 2214*a^12 + 4320*a^9 - 2484*a^6 + 648*a^3 - 162 = 0 and a in -0.4328720060607604? + 0.7497563076715000?*I

comment:8 Changed 12 years ago by was

  • Status changed from new to needs_review

I've attached a patch that reverses the order: it first tries the numerical algorithm, and if that fails, it then tries the algebraic algorithm. This makes vastly more sense to me, since the numerical algorithm -- if it will fail -- is likely to fail in a reasonable amount of time, but the algebraic algorithm can succeed and take a huge amount of time.

comment:9 Changed 12 years ago by robertwb

  • Status changed from needs_review to needs_work
sage: b = sin(pi/5)
sage: time sage.calculus.calculus.minpoly(b, algorithm='algebraic')
CPU times: user 0.05 s, sys: 0.00 s, total: 0.05 s
Wall time: 0.05 s
x^4 - 5/4*x^2 + 5/16
sage: time sage.calculus.calculus.minpoly(b)
Traceback (most recent call last):
...
NotImplementedError: Could not prove minimal polynomial x^4 - 5/4*x^2 + 5/16 (epsilon 0.00000000000000e-1)

We need to wrap raising this error to not be raised if the algorithm is numeric...

I remember doing it in this order because there were cases where the numeric algorithm was way slower, but at least the numeric one finishes in constant bounded time.

I really feel there should be a quicker way of computing compositums than using QQbar.

Changed 12 years ago by was

comment:10 Changed 12 years ago by robertwb

  • Report Upstream set to N/A
  • Status changed from needs_work to needs_review

comment:11 Changed 12 years ago by robertwb

  • Status changed from needs_review to positive_review

comment:12 Changed 12 years ago by mhansen

  • Authors set to William Stein
  • Merged in set to sage-4.3.alpha1
  • Resolution set to fixed
  • Reviewers set to Robert Bradshaw
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.