Sage: Ticket #17886: Faster qqbar operations using resultants
https://trac.sagemath.org/ticket/17886
<p>
This is a spin-off from <a class="closed ticket" href="https://trac.sagemath.org/ticket/16964#comment:31" title="Comment 31 for Ticket #16964">comment:31:ticket:16964</a>.
</p>
<p>
Many operations on algebraic numbers can become painfully slow. Most of these operations can be expressed in terms of resultants, and surprisingly the corresponding computations are sometimes <em>way</em> faster than what Sage currently does. So much faster that I'm not sure whether to consider this ticket here a request for enhancement, or even a defect.
</p>
<p>
Take for example the difference between two algebraic numbers <code>r1</code> and <code>r2</code>, which are defined as follows:
</p>
<pre class="wiki">sage: x = polygen(ZZ)
sage: p1 = x^5 + 6*x^4 - 42*x^3 - 142*x^2 + 467*x + 422
sage: p2 = p1((x-1)^2)
sage: r1 = QQbar.polynomial_root(p2, CIF(1, (2.1, 2.2)))
sage: r2 = QQbar.polynomial_root(p2, CIF(1, (2.8, 2.9)))
</pre><p>
Computing their exact difference takes like forever:
</p>
<pre class="wiki">sage: r4 = r1 - r2
sage: %time r4.exactify()
CPU times: user 2h 57min 1s, sys: 2.16 s, total: 2h 57min 3s
Wall time: 2h 57min 5s
</pre><p>
On the other hand, computing a polynomial which has the difference as one root can be achieved fairly easily using resultants, and the resulting number is obtained in under one second:
</p>
<pre class="wiki">sage: a,b = polygens(QQ, 'a,b')
sage: %time p3 = r1.minpoly()(a + b).resultant(r2.minpoly()(b), b)
CPU times: user 62 ms, sys: 0 ns, total: 62 ms
Wall time: 68 ms
sage: rs = [r for f in p3.factor()
....: for r in f[0].univariate_polynomial().roots(QQbar, False)
....: if r._value.overlaps(r1._value - r2._value)]
sage: assert len(rs) == 1
sage: r3, = rs
sage: %time r3.exactify()
CPU times: user 599 ms, sys: 0 ns, total: 599 ms
Wall time: 578 ms
</pre><p>
One possible root of <code>p3</code> is <code>b=r2</code> and <code>a+b=r1</code> which means <code>a=r1-r2</code>. So eliminating b we get a (reducible, not minimal) polynomial in a which has that difference as one of its roots. I try to identify that by looking at the roots <code>r</code> of the factors <code>f</code>, checking whether they overlap the numeric interval.
</p>
<p>
The way I understand the current code, most exact binary operations are implemented by exactifying both operands to number field elements, then constructing the union of both number fields, converting both operands to that and performing the operation in there. But there is no reason why the number field for the result should be able to contain the operands. I guess dropping that is the main reason why direct resultant computations are faster.
</p>
<p>
I propose that we try to build all binary operations on algebraic numbers on resultants instead of union fields. I furthermore propose that we try to build the equality comparison directly on resultants of two univariate polynomials, without bivariate intermediate steps.
</p>
<p>
I can think of two possible problems. One is that we might be dealing with a special case in the example above, and that perhaps number field unions are in general cheaper than resultants. Another possible problem I can imagine is that the resultant could factor into several distinct polynomials, some of which might share a root. If that were the case, numeric refinement wouldn't be able to help choosing the right factor. Should we perhaps not factor the resultant polynomial, but instead compute roots for the fully expanded form?
</p>
<p>
I'll try to come up with a branch which implements this approach.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/17886
Trac 1.1.6gagernMon, 02 Mar 2015 18:00:04 GMTbranch set
https://trac.sagemath.org/ticket/17886#comment:1
https://trac.sagemath.org/ticket/17886#comment:1
<ul>
<li><strong>branch</strong>
set to <em>u/gagern/ticket/17886</em>
</li>
</ul>
TicketgagernMon, 02 Mar 2015 18:15:00 GMTcommit, author set
https://trac.sagemath.org/ticket/17886#comment:2
https://trac.sagemath.org/ticket/17886#comment:2
<ul>
<li><strong>commit</strong>
set to <em>db116160d1d082b38c8cd1f8f90bd20feaef942b</em>
</li>
<li><strong>author</strong>
set to <em>Martin von Gagern</em>
</li>
</ul>
<p>
OK, here is some work in progress, so you can see what I have in mind. This doesn't pass tests yet, so it will definitely require some more work.
</p>
<p>
The division <code>r1/r2</code> for the example from the ticket description still takes extremely long. Surprisingly, the step which takes so long is not the computation of the resultant, its factors or its roots. No, it's the <code>candidate.exactify()</code> step which turns an <code>ANRoot</code> element into an <code>ANExtensionElement</code>. The <code>do_polred</code> in there is taking ages. Any suggestions how that might be avoided? It's “only” a degree 80 polynomial we're dealing with.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=db116160d1d082b38c8cd1f8f90bd20feaef942b"><span class="icon"></span>db11616</a></td><td><code>trac #17886: Compute binary operations using resultants.</code>
</td></tr></table>
TicketgitMon, 02 Mar 2015 19:01:34 GMTcommit changed
https://trac.sagemath.org/ticket/17886#comment:3
https://trac.sagemath.org/ticket/17886#comment:3
<ul>
<li><strong>commit</strong>
changed from <em>db116160d1d082b38c8cd1f8f90bd20feaef942b</em> to <em>234b2c4f3435531007c095d278a4c02da8ee2365</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8d4b91b4a11d2a5dceb592f33a55c79de637b801"><span class="icon"></span>8d4b91b</a></td><td><code>Return a descriptor, not an algebraic number.</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=234b2c4f3435531007c095d278a4c02da8ee2365"><span class="icon"></span>234b2c4</a></td><td><code>Choose roots field based on approximation field.</code>
</td></tr></table>
TicketgagernMon, 02 Mar 2015 19:09:14 GMT
https://trac.sagemath.org/ticket/17886#comment:4
https://trac.sagemath.org/ticket/17886#comment:4
<p>
OK, the doctests look a lot better now. Mostly arbitrary choices made differently, like sign changes or using a different root as the reference generator, stuff like that. In several cases I obtain simpler results, i.e. polynomials of lower degree and the likes.
</p>
<p>
One thing that has me worried are cyclotomics. If both arguments are from cyclotomic fields, then we should do the union (which is fast in that case) instead of the minpoly and resultant. I haven't figured out how best to check for that case, though.
</p>
<p>
Another thing I fail is that test taken from that ARPREC paper. That example is really fast in current implementation, precisely because it's only operating in a single number field, so it doesn't really require any unions at all. Should we try to detect this fact, i.e. see if both arguments are either rational or elements of the same number field? My failure is only later on, where the original code somehow magically knows that the difference of two equal numbers is zero. I guess that if we did introduce a special case for equal number field, we might get that for free even though I don't know exactly how it works.
</p>
TicketgagernMon, 02 Mar 2015 19:21:27 GMTdescription changed
https://trac.sagemath.org/ticket/17886#comment:5
https://trac.sagemath.org/ticket/17886#comment:5
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/17886?action=diff&version=5">diff</a>)
</li>
</ul>
<p>
Including total CPU time for <code>r4.exactify()</code> using existing implementation.
</p>
TicketgitMon, 02 Mar 2015 19:27:56 GMTcommit changed
https://trac.sagemath.org/ticket/17886#comment:6
https://trac.sagemath.org/ticket/17886#comment:6
<ul>
<li><strong>commit</strong>
changed from <em>234b2c4f3435531007c095d278a4c02da8ee2365</em> to <em>12a1053f78c9efee9f3e6c88eb2c1c89d2db4312</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=12a1053f78c9efee9f3e6c88eb2c1c89d2db4312"><span class="icon"></span>12a1053</a></td><td><code>Name myself in list of authors</code>
</td></tr></table>
TicketvdelecroixWed, 04 Mar 2015 09:50:57 GMT
https://trac.sagemath.org/ticket/17886#comment:7
https://trac.sagemath.org/ticket/17886#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17886#comment:4" title="Comment 4">gagern</a>:
</p>
<blockquote class="citation">
<p>
One thing that has me worried are cyclotomics. If both arguments are from cyclotomic fields, then we should do the union (which is fast in that case) instead of the minpoly and resultant. I haven't figured out how best to check for that case, though.
</p>
</blockquote>
<p>
For cyclotomics, I really think that we should use the universal cyclotomic field (and enhanced it):
</p>
<pre class="wiki">sage: UCF = UniversalCyclotomicField()
sage: zeta3 = UCF.gen(3)
sage: zeta5 = UCF.gen(5)
sage: a = zeta3 + 2
sage: b = zeta5 + 1
sage: timeit("a*b")
625 loops, best of 3: 50.2 µs per loop
sage: a_QQbar = QQbar(a)
sage: b_QQbar = QQbar(b)
sage: timeit("a_QQbar*b_QQbar")
625 loops, best of 3: 13.2 µs per loop
sage: timeit("c = a_QQbar*b_QQbar; c.exactify()")
625 loops, best of 3: 774 µs per loop
</pre><blockquote class="citation">
<p>
Another thing I fail is that test taken from that ARPREC paper. That example is really fast in current implementation, precisely because it's only operating in a single number field, so it doesn't really require any unions at all. Should we try to detect this fact, i.e. see if both arguments are either rational or elements of the same number field? My failure is only later on, where the original code somehow magically knows that the difference of two equal numbers is zero. I guess that if we did introduce a special case for equal number field, we might get that for free even though I don't know exactly how it works.
</p>
</blockquote>
<p>
Definitely. If the two elements have the same parent (i.e. QQ, a number field or UCF) we should perform the operation directly. Moreover, I hope to have something fast for comparisons in a given number field <a class="closed ticket" href="https://trac.sagemath.org/ticket/17830" title="enhancement: Comparison of number field elements dependent of real embedding (closed: fixed)">#17830</a> that would also speed up some comparisons in that case.
</p>
<p>
Vincent
</p>
TicketgagernWed, 04 Mar 2015 16:14:12 GMT
https://trac.sagemath.org/ticket/17886#comment:8
https://trac.sagemath.org/ticket/17886#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17886#comment:2" title="Comment 2">gagern</a>:
</p>
<blockquote class="citation">
<p>
The division <code>r1/r2</code> for the example from the ticket description still takes extremely long. Surprisingly, the step which takes so long is not the computation of the resultant, its factors or its roots. No, it's the <code>candidate.exactify()</code> step which turns an <code>ANRoot</code> element into an <code>ANExtensionElement</code>. The <code>do_polred</code> in there is taking ages. Any suggestions how that might be avoided? It's “only” a degree 80 polynomial we're dealing with.
</p>
</blockquote>
<p>
I compared this with Mathematica. Apart from the fact that I prefer Sage's way of presenting these numbers, I first <a class="ext-link" href="http://mathematica.stackexchange.com/q/76413/8395"><span class="icon"></span>couldn't get Mathematica</a> to do elementary arithmetic on these two numbers at all. But using <a class="ext-link" href="http://mathematica.stackexchange.com/a/76423/8395"><span class="icon"></span>a different approach</a>, I managed to do so. In Mathematica the division takes about twice as long as the other three operations, which makes sense considering that the resulting minimal polynomial has twice the degree. But it's only a distinction between 0.1 and 0.2 seconds, so there should be no mathematically unavoidable reason why Sage takes as long as it takes.
</p>
<p>
Should we try to avoid polred completely? I have the impression that this ticket here moves the focus away from “an algebraic number field extension and some polynomial in its generator” towards “a defining polynomial and an isolating interval”. The change is gradual, and we definitely want to keep the former aspect available if we want to simplify cases where all operations take place in the same number field. But since we no longer use unions for all operations, the nice and small description of the field generator appears to be less important. And the way I understand it, <code>do_polred</code> is responsible for finding such a nice and small generator. Should I try omitting that?
</p>
TicketgagernWed, 04 Mar 2015 23:02:21 GMT
https://trac.sagemath.org/ticket/17886#comment:9
https://trac.sagemath.org/ticket/17886#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17886#comment:2" title="Comment 2">gagern</a>:
</p>
<blockquote class="citation">
<p>
The division <code>r1/r2</code> for the example …
</p>
</blockquote>
<p>
… can be used to exhibit several problems which are not directly related to arithmetic via resultants, so I filed separate tickets about these:
</p>
<ul><li><a class="closed ticket" href="https://trac.sagemath.org/ticket/17895" title="defect: Computing all roots is faster than computing a single one (closed: fixed)">#17895</a> about <code>p.roots(QQbar)</code> being faster than <code>QQbar.polynomial_root(p, …)</code>
</li><li><a class="closed ticket" href="https://trac.sagemath.org/ticket/17896" title="defect: Polred during exactification takes too long (closed: duplicate)">#17896</a> about the slow exactification mentioned above: still not completed after 6h
</li></ul>
TicketmmezzarobbaSat, 18 Apr 2015 18:22:53 GMTcc set
https://trac.sagemath.org/ticket/17886#comment:10
https://trac.sagemath.org/ticket/17886#comment:10
<ul>
<li><strong>cc</strong>
<em>mmezzarobba</em> added
</li>
</ul>
TicketmmezzarobbaSat, 18 Apr 2015 18:25:54 GMT
https://trac.sagemath.org/ticket/17886#comment:11
https://trac.sagemath.org/ticket/17886#comment:11
<p>
Regarding polred, see <a class="closed ticket" href="https://trac.sagemath.org/ticket/15600" title="defect: Skip polredbest() for large extensions in exact computations in QQbar (closed: fixed)">#15600</a>.
</p>
TicketvdelecroixMon, 18 Jan 2016 19:20:47 GMT
https://trac.sagemath.org/ticket/17886#comment:12
https://trac.sagemath.org/ticket/17886#comment:12
<p>
Note that <a class="closed ticket" href="https://trac.sagemath.org/ticket/18356" title="enhancement: special resultants ``composed_sum`` and ``composed_product`` (closed: fixed)">#18356</a> proposed a better solution rather than resultants (via an algorithm from Bostan-Flajolet-Salvy-Schost). I guess we should make it a dependency of this ticket.
</p>
TicketgagernMon, 11 Jul 2016 12:35:25 GMT
https://trac.sagemath.org/ticket/17886#comment:13
https://trac.sagemath.org/ticket/17886#comment:13
<p>
Status update: <a class="closed ticket" href="https://trac.sagemath.org/ticket/18356" title="enhancement: special resultants ``composed_sum`` and ``composed_product`` (closed: fixed)">#18356</a> has been merged by now (I hadn't noticed straight away), and <a class="new ticket" href="https://trac.sagemath.org/ticket/18242#comment:16" title="Comment 16 for Ticket #18242">comment:16:ticket:18242</a> suggests incorporating these new functions into this ticket here. So I intend to incorporate those functions into my modifications as soon as I find the time. Also note <a class="new ticket" href="https://trac.sagemath.org/ticket/18333" title="task: Cleanup and speedup in QQbar (new)">#18333</a> for the big picture of things planned for QQbar.
</p>
TicketmjoMon, 01 Mar 2021 06:04:51 GMTcc changed
https://trac.sagemath.org/ticket/17886#comment:14
https://trac.sagemath.org/ticket/17886#comment:14
<ul>
<li><strong>cc</strong>
<em>mjo</em> added
</li>
</ul>
<p>
Well I guess I'm interested in this now that I'm trying to do something where addition/multiplication in <code>AA</code> is the bottleneck:
</p>
<pre class="wiki"> 27065425 function calls (27065055 primitive calls) in 53.210 seconds
Ordered by: cumulative time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 53.216 53.216 {built-in method builtins.exec}
1 0.000 0.000 53.215 53.215 <string>:1(<module>)
19/1 0.000 0.000 53.215 53.215 unique_representation.py:992(__classcall__)
19/1 0.000 0.000 53.215 53.215 {sage.misc.classcall_metaclass.typecall}
1 0.000 0.000 53.215 53.215 eja_algebra.py:2568(__init__)
1 0.010 0.010 52.715 52.715 eja_algebra.py:1572(__init__)
2 0.038 0.019 52.699 26.350 eja_algebra.py:135(__init__)
1923634 4.034 0.000 31.679 0.000 qqbar.py:5092(__init__)
1923634 8.259 0.000 25.807 0.000 qqbar.py:3413(__init__)
956610 3.154 0.000 23.851 0.000 qqbar.py:3626(_add_)
240 2.260 0.009 23.787 0.099 eja_algebra.py:1779(jordan_product)
963694 3.176 0.000 23.677 0.000 qqbar.py:3579(_mul_)
</pre>
TicketvdelecroixMon, 01 Mar 2021 08:00:13 GMT
https://trac.sagemath.org/ticket/17886#comment:15
https://trac.sagemath.org/ticket/17886#comment:15
<p>
I don't think you are. Addition/multiplication are <code>O(1)</code> in <code>AA/QQbar</code> (the elements are stored as expression trees). More efficient datastructures could be used but this is not what this ticket is about. Serious problems in <code>AA/QQbar</code> starts when you try to compare elements. This is what this ticket is about.
</p>
<p>
In your example you perform 1000000 binary operations. That is of course costly.
</p>
TicketmjoMon, 01 Mar 2021 13:48:18 GMT
https://trac.sagemath.org/ticket/17886#comment:16
https://trac.sagemath.org/ticket/17886#comment:16
<p>
Ok, I must have misunderstood =(
</p>
<p>
The same function over <code>QQ</code> completes almost instantly:
</p>
<pre class="wiki"> 123510 function calls (119803 primitive calls) in 0.444 seconds
Ordered by: cumulative time
ncalls tottime percall cumtime percall filename:lineno(function)
402/1 0.001 0.000 0.451 0.451 {built-in method builtins.exec}
1 0.000 0.000 0.451 0.451 <string>:1(<module>)
92/1 0.000 0.000 0.451 0.451 unique_representation.py:992(__cl$
92/1 0.000 0.000 0.451 0.451 {sage.misc.classcall_metaclass.ty$
1 0.000 0.000 0.451 0.451 eja_algebra.py:2568(__init__)
11 0.001 0.000 0.289 0.026 __init__.py:1(<module>)
1 0.000 0.000 0.277 0.277 eja_algebra.py:1572(__init__)
1 0.006 0.006 0.270 0.270 eja_algebra.py:135(__init__)
...
</pre><p>
which is why I was optimistic that it could be improved over <code>QQbar</code>. (Maybe just by cythonizing it?) The underlying additions and multiplications are all from basic linear algebra. Products, inner products, coordinate computations (with respect to a basis), and so on for pairs of matrices.
</p>
TicketvdelecroixMon, 01 Mar 2021 13:53:20 GMT
https://trac.sagemath.org/ticket/17886#comment:17
https://trac.sagemath.org/ticket/17886#comment:17
<p>
Sure there is no tree needed to represent the objects in <code>QQ</code>. Could you post a link to your code and the command you used for this profiling?
</p>
TicketmjoMon, 01 Mar 2021 14:09:23 GMT
https://trac.sagemath.org/ticket/17886#comment:18
https://trac.sagemath.org/ticket/17886#comment:18
<p>
This particular code is here:
</p>
<blockquote>
<p>
<a class="ext-link" href="http://gitweb.michael.orlitzky.com/?p=sage.d.git;a=tree;f=mjo/eja;hb=HEAD"><span class="icon"></span>http://gitweb.michael.orlitzky.com/?p=sage.d.git;a=tree;f=mjo/eja;hb=HEAD</a>
</p>
</blockquote>
<p>
With the "all" module imported, the two commands I profiled are
</p>
<pre class="wiki">sage: %prun -s cumulative QuaternionHermitianEJA(3,field=AA,orthonormalize=False)
sage: %prun -s cumulative QuaternionHermitianEJA(3,field=QQ,orthonormalize=False)
</pre><p>
with the only difference being the <code>field</code> parameter. Unfortunately, for user interface reasons, <code>AA</code> has to be the default.
</p>
TicketmmezzarobbaMon, 01 Mar 2021 15:40:05 GMT
https://trac.sagemath.org/ticket/17886#comment:19
https://trac.sagemath.org/ticket/17886#comment:19
<p>
@mjo: I didn't read the full discussion, but: if, in the application where you take elements of <code>AA</code> as input, you can dynamically determine a number field over which you can perform the whole computation, you should probably try doing that.
</p>
<p>
Otherwise, I suspect the best option in terms of value/effort ratio to speed up operations with algebraic numbers in Sage is now to create an alternative to the existing <code>QQbar</code> based on <a class="ext-link" href="https://fredrikj.net/calcium/"><span class="icon"></span>Calcium</a>.
</p>
TicketvdelecroixMon, 01 Mar 2021 16:00:18 GMT
https://trac.sagemath.org/ticket/17886#comment:20
https://trac.sagemath.org/ticket/17886#comment:20
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17886#comment:19" title="Comment 19">mmezzarobba</a>:
</p>
<blockquote class="citation">
<p>
@mjo: I didn't read the full discussion, but: if, in the application where you take elements of <code>AA</code> as input, you can dynamically determine a number field over which you can perform the whole computation, you should probably try doing that.
</p>
</blockquote>
<p>
+1. More precisely
</p>
<pre class="wiki">sage: from sage.rings.qqbar import number_field_elements_from_algebraics
sage: l = [QQbar(2)**(1/2), QQbar(3)**(1/3) - QQbar(5)**(1/2)]
sage: number_field_elements_from_algebraics(l, minimal=True)
(Number Field in a with defining polynomial y^12 - 12*y^10 - 24*y^9 + 60*y^8 - 34*y^6 + 576*y^5 - 1164*y^4 - 1320*y^3 + 456*y^2 + 2448*y - 1151,
[-16518995559/7799826643957*a^11 - 10435260375/7799826643957*a^10 + 187520914172/7799826643957*a^9 + 508862279484/7799826643957*a^8 - 1241854471899/15599653287914*a^7 - 218478193524/7799826643957*a^6 + 313750924974/7799826643957*a^5 - 9705313541079/7799826643957*a^4 + 13428594964320/7799826643957*a^3 + 28757542878738/7799826643957*a^2 + 16368959650563/15599653287914*a - 24370182357588/7799826643957,
48080033585/15599653287914*a^11 + 92029987813/46798959863742*a^10 - 1654443694787/46798959863742*a^9 - 753537685652/7799826643957*a^8 + 3753942837309/31199306575828*a^7 + 1758351424153/23399479931871*a^6 - 496099642485/7799826643957*a^5 + 38328135347057/23399479931871*a^4 - 119433168311027/46798959863742*a^3 - 38969257820277/7799826643957*a^2 - 82694429544359/31199306575828*a + 156136708099345/23399479931871],
Ring morphism:
From: Number Field in a with defining polynomial y^12 - 12*y^10 - 24*y^9 + 60*y^8 - 34*y^6 + 576*y^5 - 1164*y^4 - 1320*y^3 + 456*y^2 + 2448*y - 1151
To: Algebraic Real Field
Defn: a |--> 0.9193952626442228?)
</pre><blockquote class="citation">
<p>
Otherwise, I suspect the best option in terms of value/effort ratio to speed up operations with algebraic numbers in Sage is now to create an alternative to the existing <code>QQbar</code> based on <a class="ext-link" href="https://fredrikj.net/calcium/"><span class="icon"></span>Calcium</a>.
</p>
</blockquote>
<p>
That would be nice to see how it performs. The approach in Calcium is quite different.
</p>
TicketmjoMon, 01 Mar 2021 16:15:27 GMT
https://trac.sagemath.org/ticket/17886#comment:21
https://trac.sagemath.org/ticket/17886#comment:21
<p>
Thanks, I actually started out with that approach since all I need to construct my example algebras is <code>sqrt(2)</code>. I ran into a lot of problems converting between number fields, though; and you can't choose one a priori that will work. I'd have issues like after taking the spectral decomposition, I'd get back eigenvalues in <code>NumberField over NumberField over NumberField... over NumberField</code> that couldn't be multiplied by an element of the <code>QQ(sqrt(2))</code> that I started with. And theoretically, it's annoying that eigenvalues should live in the base field and they don't if you have to make the base field bigger to find them.
</p>
<p>
In short, I gave up on it in commit 98da0ce1d11020 and switched to <code>AA</code> "because everything cool requires it."
</p>
<p>
This isn't a life threatening problem yet, it's just annoying that my test suite is so slow. I appreciate the suggestions though.
</p>
Ticket