On Sat, Feb 20, 2021 at 08:01:51PM +0100, Ralf Hemmecke wrote:
> Hi Waldek,
>
> > Looking again at the problem it is not clear what is the
> > intent.
>
> I had posted the original intend here.
> https://groups.google.com/g/fricas-devel/c/jmEWZvM5Jdk/m/1j33ik34AAAJ
>
> https://www.mail-archive.com/[email protected]/msg13091.html
>
> I did this some time ago so I guess the code attached there is not
> up-to-date. But you asked about the intend.
I remember that you talked about algebraic closure. I forgot that
you posted the code.
> What I have posted at the beginning of the "slow factorization in finite
> field" thread is connected to it. I experimented with my implementation
> of a dynamic algebraically closed field and wondered about long running
> times.
OK, so the intent is to speed up your algebraic closure code.
I would say that first step is to avoid factorization when
simpler thing will do. Factorization has its cost. IME
factorization is cheaper than say resultants, so "rational"
algorithms that use resultants may be more expensive
than methods depending on resultants. Algebraic
extentions have serious cost, with current FriCAS methods at
best compute time will grow quadraticaly with extension degree
and frequently faster. For large extension degrees we would
need asymptotically fast methods (currently not present in
FriCAS). Doing things in smaller fields (if possible)
usually will be faster.
Of course, faster routines for basic operations will
speed up everthing, but IMO also at higher level
there is possibilty for savings.
As extra remarks: Expression is supposed to implement
algebraic closure. I spent some time thinking about
possible improvements to Expression and related code
(in particular handling of algebraic functions in
integrator). I view using finite fields as key
factor in possible improvements. In particular,
I expect to make more uses of routines based on
U32Vector. OTOH I expect most algebaic quantities
to be radicals and for radicals in many cases one
can do better than for roots of general polynomials.
> The polynomials
>
> p3 := x^3 - 29
> p5 := x^5 - 29
> p7 := x^7 - 29
>
> are somewhat made up, because I wanted to test whether my code can
> recognize zeros in an algebraic setup.
As I wrote, they are rather special.
> In fact, a dynamically algebraic closure is like AlgebraicNumber with
> the property that the zero test really finds zeros. For example, it can
> decide whether sqrt(2)*sqrt(3)-sqrt(6) is true or false. That example is
> too easy, but you get the point. Note that is could also be that by
> independently creating sqrt(2), sqrt(3) and sqrt(6), it coudl also be
> that for consistency, we would have
>
> zero?(sqrt(2)*sqrt(3) - sqrt(6)) is false
> and
> zero?(sqrt(2)*sqrt(3) + sqrt(6)) is true.
>
> Internally, the dynamic algebraic closure relies on a projection into a
> finite field (with enough roots). Clearly with the dynamic extension of
> the field one also must sometimes extend the underlying finite field.
> And there I need to factor polynomials in finite fields.
In code you posted I see:
Exports ==> Join(AlgebraicallyClosedField, FiniteFieldCategory) with
This is mathematical contradiction and we should not do this.
--
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 [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/fricas-devel/20210221002809.GA4195%40math.uni.wroc.pl.
