On Tue, Oct 20, 2020 at 08:50:27PM +0200, Waldek Hebisch wrote:
> On Tue, Oct 20, 2020 at 02:40:32PM +0200, Ralf Hemmecke wrote:
> > Hello,
> >
> > The attached file is code comes from the problem of creating the
> > algebraic closure of PrimeField(p) by dynamically extending with a field
> > with a new polynomial that does not completely factor. It basically
> > works, but when I tried with the polynomials over GF(43) I realized very
> > long running times.
> >
> > The following maps this to FiniteField(43,84) (the splitting field of
> > the 3 polynomials
> >
> > p3 := x^3 - 29
> > p5 := x^5 - 29
> > p7 := x^7 - 29
> >
> > When I factor them on my lapto I get:
> >
> > Time: 8.57 (EV) + 0.00 (OT) = 8.57 sec
> > Time: 23.81 (EV) + 0.00 (OT) = 23.82 sec
> > Time: 35.38 (EV) = 35.38 sec
> >
> > After analyzing where the time is spent I found that there is an
> > exptMod(t1, (p1 quo 2)::NNI, fprod) call in ddfact.spad
> > where t1 and fprod are polynomials of degree 1 and 7 (for the last case)
> > and (p1 quo 2)::NNI is
> >
> > 81343016389104495051429314429892710283748121052067002779751599748804821941
> > 461709990823638183537929646810274525597886525946443695227097400
> >
> > Clearly, that is a huge number and the coefficients of the polynomials
> > are (as elements of FF(43,84)) univariate polynomials of degree 83).
> > So it is expected to take a while.
> >
> > However, I did the same computation with Magma in a fraction of a
> > second. Is FriCAS so bad here? :-(
>
> One possible way is to create variant of FiniteField
> which uses U32Vector as representation. To say how
> much speedup one would get one needs to implement it
> and measure.
I have implemented toy domain like this (just operations
needed for test above). On my machine it runs 3 times
faster with default build. With sbcl at highest
optimization level it runs 4 times faster. There
is significant room for easy improvement as polynomial
remainder U32VectorPolynomialOperations is rather slow.
--
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/20201021214719.GA27755%40math.uni.wroc.pl.
