lazy algebraic numbers

[parisse]

I'm looking at the algorithms used in Calcium now included in flint to simplify expressions with algebraic numbers, in order to improve giac : I don't think we can share code, but for sure we can share ideas and improve both libraries (giac and flint I mean). Looking at the Fredrik's paper https://inria.hal.science/hal-02986375v2/file/paper.pdf does not give some details on how relations are proven if the numeric check says that an expression may be 0. I'm interested in the case where all numbers involved are algebraic and the multivariate polynomial representation is used (i.e. not qqbar with univariate representation).
My first attempt to do that in giac is compute a gcd of the expression (that is numerically 0) with the last relation in the system of relations (ordered by complexity). I believe Magma does like that (replacing the numerical check by a modular check), because that way one can handle algebraic numbers without factoring over extensions.
Example sqrt(6)-sqrt(2)*sqrt(3) -> x3-x1*x2 where x1^2-2,x2^2-3,x3^2-6 are 0, compute gcd of x3^2-6 with x3-x1*x2 with euclidean algorithm and pseudo-divisions, reduce the remainder with the relations system. Here it will return remainder x1^2*x2^2-6 (without reduction) then 0. Then we can reduce the relation system, replacing degree 2 x3^2-6 by degree 1 x3-x1*x2=0. If the first division does not return a 0 remainder, we have to check the gcd and the cofactor of the "probably 0 expression" in the gcd, and decide which one is 0 with a numerical check.
Does Calcium/flint includes something similar? I had a quick look and I could not find code, but may be that's because I'm not familiar with flint.

Thanks!

[Fredrik Johansson]

Hi Bernard,

Currently calcium only looks for special relations (e.g. purely linear, multiplicative, or conjugate) between algebraic numbers when constructing fields. This isn't by design so much as the fact that a general algorithm hasn't been implemented yet.

To test if a multivariate expression is zero, after checking numerically, the first step is currently to factor it as a polynomial over Z. Any purely algebraic factor that is numerically zero is then simply evaluated using qqbar arithmetic. I can think of some heuristics to improve this last step. For example, instead of checking F(x,y,z) = 0, decompose it as F = G - H and check if G(x,y,z) = H(x,y,z).

The GCD method you propose looks quite interesting.

Fredrik

--

---
You received this message because you are subscribed to the Google Groups "flint-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to flint-devel...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/flint-devel/3ae15be7-ee03-4725-a89a-f53858e428a0n%40googlegroups.com.

[parisse]

One reason to avoid qqbar is to spare a factorization of the minimal polynomial of a new algebraic number over the current extension, The other reason is that computing in a unique algebraic extension containing all the algebraic numbers of an expression is just too expensive. Avoiding a factorization of a multivariate polynomial over Z and computing a multivariate GCD is certainly an improvement. It's not as general as Calcium since it's limited to algebraic number, but if the GCD is trivial, I also recursively check the coefficients with respect to the main variable, if all gcd are trivial, then it's a proof that the algebraic number is "different from 0 (and it also means I probably need to increase the precision for interval arithmetic).

Starting version 1.9.0-73, Giac/Xcas is using a mixed representation for algebraic number simplification: compute in qqbar if the extension degree is smaller than a limit (default 64, may be changed, e.g. with max_common_alg_ext_order_size(72)), if it becomes larger, switch to lazy multivariate representation. Numerical 0 checking is done with (complex) interval arithmetic, if the value may be 0, then check with the GCD algorithm.
It is still somewhat experimental, I mean I do not have a lot of regression tests. I checked with a few benchmarks of Calcium like on the web session linked here (this is the wasm-compiled version of giac, computation are done on the client browser device, it's a little bit slower than native versions of Giac/Xcas but you don't need a server to run the computation).