On Thu, Jul 13, 2023 at 09:00:29AM +0200, Ralf Hemmecke wrote:
>
> 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
Concerning slow factorization: one significant reason for slow
factorization is that operations in general finite fields are
slow. And AFAICS finite fields represented by triangular sets
are slower than other slow variants.
Another thing is that you use expensive operations when faster
alternatives would do. For example, factoring
x^17 - 11*13*17*19
over FiniteField(16777777,17) takes 22.89 sec, factoring over
FiniteField(2305843009213693921,17) take 150.71, finding
root by powering can be done probably in few milliseconds.
AFAICS DynamicAlgebraicNumber introduces extra extention
of degree 2 and tries to factor cyclotomic polynomial.
Roots of cyclotomic polynomial are already in base field
and can can be found by factoring in about 40 milliseconds,
using powering it should be several time faster. On
much slower machine new factoring code needs about 1.2
milliseconds to factor cyclotomic polynomial over
PF(16777777).
Anyway, to be faster DynamicAlgebraicNumber should first
factor polynomial over smallest possible field (that is
field containing its coefficients). After that one can
compute which field is needed to split the polynomial
and one can do splitting in this field. Final part
is embedding splitting field in your final field, this
can be done once and can be done using roots which is
cheaper than factoring. Some of those improvements
could be done in factoring code, but in general
DynamicAlgebraicNumber or DynamicAlgebraicClosureFiniteField
has more information. For example factoring code could
check at resonable cost that polynomial has coefficients
in base field. But if coefficients are in intermediate
fields check in factorizer would be much more complicated.
Also, factorizer could compute emeddings on the fly,
but is is cheaper to create them once and reuse.
Concerning factorization, new factorizer (in ffact.spad)
can now handle general finite fields. For high algebraic
extentions it still need algorithmic improvement, but
but it is not far from best known algorithms. What is
most needed are fast low level routines like polynomial
mutiplication, gcd and matrix-vector mutiplication.
One thing to point out is that dealing with mutliple algebraic
extentions is inherently exponential. One can hope to make
easy cases fast, but general case are going to be expensive.
--
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/ZLCdbL4wS2KNzGww%40fricas.math.uni.wroc.pl.
