Hi Vincent,
On Sunday, April 25, 2021 at 4:26:18 PM UTC+2 vdelecroix wrote:
> Dear Fredrik,
>
> One technical question: I thought that your ca_t implementation
> used multivariate polynomials. This is what Magma does but not
> what sage does. The latter uses expression trees and take union
> fields anytime there is an exactification to be done. Is it a
> misconception of mine?
>
Yes, ca_t uses multivariate polynomials (in fact, multivariate fraction
field elements). It uses univariate polynomials in the special case of
simple (univariate) number fields.
Symbolic expressions are effectively used to represent non-field operations
generating new extension elements (e.g. square roots, when not converted to
absolute qqbar elements).
>
> For "real world" problems
>
> 1) algebraic solutions of zero dimensional varieties
> defined over QQ
>
> sage: R.<x,y,z> = QQ[]
> sage: A = x^4 + y^4 + z^3 - 1
> sage: B = x^2*z + 2*y^2*x - x*y*z + 5
> sage: C = y*z^2 - 2*(x+y+z) + 2
> sage: %time solutions = R.ideal([A,B,C]).variety(QQbar)
> CPU times: user 24.3 s, sys: 23.3 ms, total: 24.3 s
> Wall time: 24.4 s
>
> Though here is the bottleneck is Groebner basis computation
> of multivariate polynomials and not really QQbar (21s over the 24s).
>
>
> 2) Two examples somehow similar to your huge_expr
>
> sage: a = sum(AA(p).sqrt() for p in prime_range(18))
> sage: %time a.exactify()
> CPU times: user 30.7 s, sys: 13.3 ms, total: 30.8 s
> Wall time: 30.8 s
> sage: a.degree() # does not terminates
>
> In the above situation, the problem is that sage is representing
> the number a as a complicated element in a rather complicated
> number field. Computing the minpoly involves apparently too
> complicated linear algebra (?). However, if instead of exactifying
> in that way but using the minimal polynomial (which looks reasonable
> in this range of degrees) the latter would be very quick.
>
> sage: b = sum(QQbar.zeta(n) for n in range(1,8))
> sage: b.exactify() # does not terminate
>
> Here sage is stuck at building union fields.
>
With qqbar_t:
In [2]: %time sum(qqbar(p).sqrt() for p in [2, 3, 5, 7, 11, 13, 17])
CPU times: user 286 ms, sys: 4.23 ms, total: 291 ms
Wall time: 290 ms
Out[2]: 19.0734 (deg 128)
In [3]: %time sum(qqbar(RootOfUnity(n)) for n in range(1,8))
CPU times: user 24.1 ms, sys: 30 µs, total: 24.1 ms
Wall time: 23.5 ms
Out[3]: 0.932507 + 4.46494*I (deg 96)
With ca_t:
In [2]: %time sum(ca(p).sqrt() for p in [2, 3, 5, 7, 11, 13, 17])
CPU times: user 2.77 ms, sys: 265 µs, total: 3.03 ms
Wall time: 2.63 ms
Out[2]: 19.0734 {a+b+c+d+e+f+g where a = 4.12311 [a^2-17=0], b = 3.60555
[b^2-13=0], c = 3.31662 [c^2-11=0], d = 2.64575 [d^2-7=0], e = 2.23607
[e^2-5=0], f = 1.73205 [f^2-3=0], g = 1.41421 [g^2-2=0]}
In [3]: %time sum(ca(qqbar(RootOfUnity(n))) for n in range(1,8))
CPU times: user 3.13 ms, sys: 0 ns, total: 3.13 ms
Wall time: 2.55 ms
Out[3]: 0.932507 + 4.46494*I {a+b+c+d where a = 0.623490 + 0.781831*I
[a^6+a^5+a^4+a^3+a^2+a+1=0], b = 0.309017 + 0.951057*I [b^4+b^3+b^2+b+1=0],
c = 1.73205*I [c^2+3=0], d = I [d^2+1=0]}
Of course, it is debatable whether the result has really been "computed"
here. If you convert the result to a qqbar_t, it will basically take as
long as using qqbar_t in the first place. But these examples are trivial;
in other cases, the multivariate arithmetic will be helpful.
Fredrik
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-devel/7979c2fe-936e-4b25-9ca7-7c4cd2b71fa7n%40googlegroups.com.
