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: |
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)
Change History (13)
comment:1 Changed 13 years ago by
comment:2 follow-up: ↓ 5 Changed 13 years ago by
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
Note that for now the doctest has been disabled to get the doctests to pass.
Cheers,
Michael
comment:4 Changed 13 years ago by
- 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: ↓ 6 Changed 12 years ago by
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
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
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
- 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
- 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
comment:10 Changed 12 years ago by
- Report Upstream set to N/A
- Status changed from needs_work to needs_review
comment:11 Changed 12 years ago by
- Status changed from needs_review to positive_review
comment:12 Changed 12 years ago by
- Merged in set to sage-4.3.alpha1
- Resolution set to fixed
- Reviewers set to Robert Bradshaw
- Status changed from positive_review to closed
You can still access my old (numeric) minpoly code via
However, for many cases this is much slower or fails completely.