On Thu, Jul 13, 2023 at 09:00:29AM +0200, Ralf Hemmecke wrote:
>
> Using triangular sets reminds me of my attempts to implement dynamical
> algebraic closures \cite{Steel_AlgebraicallyClosedFields_2002}.
>
> Code is currently here. I haven't touched it recently, but it worked for
> simple cases, became, however, unmanageably slow with several extensions
> due to slow factorization of finite fields in FriCAS.
>
> https://github.com/hemmecke/qeta/blob/master/src/iffts.spad
> https://github.com/hemmecke/qeta/blob/master/src/ffalgclos.spad
> https://github.com/hemmecke/qeta/blob/master/src/algclos.spad
>
> I'd be happy, if that makes it in one form or the other into FriCAS.
> Maybe, Waldek, it does not exactly solve your problem from above, but I
> wanted to share my experiments.
Tried it a bit. First, CyklotomicPolynomialPackage is now removed,
need to replace it by CyklotomicUtilities. Second, it seems that
you are factoring numbers under roots:
(32) ax := xx^2 - 6
2
(32) ? - 6
Type: SparseUnivariatePolynomial(DynamicAlgebraicNumber)
(33) -> r := rootsOf(ax)
[:> , DACFF rootOf poly, ?^2+2305843009213693919]
(33) [r1 r7, - r1 r7]
Type: List(DynamicAlgebraicNumber)
So, code is smart enough to notice that square root of 3 already
appeared, but expressions are more complicated then they would
be otherwise (without reusing previous root this doubles degree
of exention). And when there are four factors we get:
(36) -> ax := xx^2 - 11*13*19*43
2
(36) ? - 116831
Type: SparseUnivariatePolynomial(DynamicAlgebraicNumber)
(37) -> r := rootsOf(ax)
[:> , DACFF rootOf poly, ?^2+2305843009213693910]
[:> , DACFF rootOf poly, ?^2+2305843009213693908]
[:> , DACFF rootOf poly, ?^2+2305843009213693902]
[:> , DACFF rootOf poly, ?^2+2305843009213693878]
(37) [r10 r11 r12 r13, - r10 r11 r12 r13]
Type: List(DynamicAlgebraicNumber)
so there are three extra roots.
(5) -> ax := xx^3 - 1/2305843009213693921
3 1
(5) ? - -------------------
2305843009213693921
Type: SparseUnivariatePolynomial(DynamicAlgebraicNumber)
(6) -> r := rootsOf(ax)
>> Error detected within library code:
IFFTS: inv: cannot invert zero element
Of course, chance that somebody will randomly find your prime is
negligible. But there is nontrivial cost of using 61-bit prime
and with more practical primes chance of error while low is no
longer negligible.
BTW: Steel et all write that they force full factoring of
defining polynomials in case of failure. But AFAICS one
can simply choose different prime and choose roots in
finite field in a way which is compatible with current
defining polynomials.
> Actually, also here we have domains with history, i.e. store some state
> (namely the triangular set). Theoretically, it works like an algebraic
> closure, but the more extensions are involved the more time it consumes, so
> it might be necessary to implement a way to either (A) create a second copy
> of such a domain that builds another triangular set or (B) to clear the
> triangular set and build it anew for a different task.
> (A) has the problem that one would have to add a parameter like the minimal
> polynomial for SAE, but that is what I actually wanted to hide in an
> implementation of an algebraic closure.
> (B) is problematic, since it invalidates all elements of the domain that
> have been created before.
Either way, it seems problematic to store elements of such domains
in files. And even if we ignore problems above mutable domains
cause various troubles. Borderline case is Kernel: kernels depend
on kernel cache which is separate from Kernel. A kernel carry
enough information to re-create it after kernel cache is cleared.
And we have code to mark kernels as needing re-insertion in cache.
> Actually, there could be a third option. Elements carry a pointer to the
> underlying triangular set of the extension, but then it's probably not so
> easy to add elements that have different triangular sets attached.
As long as you do not need to simplify just append both (or maybe
intelive). Whith some smarts unused variables (generators) should have
little cost.
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/fricas-devel/ZLBgSHoTibkOUYlY%40fricas.math.uni.wroc.pl.
