On Wed, Oct 21, 2020 at 11:47:19PM +0200, Waldek Hebisch wrote:
> 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.
Just little more about possible speed. I tried toy
problem as a benchmark:
pF := PrimeField(nextPrime(10^7)) -- 10000019
uP := UnivariatePolynomial(x, pF)
pol := reduce(*, [x - (20 + 5*i)::pF for i in 1..84])
On my computer (rather slow one) I get the following times
(in seconds):
regular FriCAS factor 1.03
mfractor from MODFACT 0.018
flint 0.009
NTL 0.038
Note: it is possible that I am using NTL incorrectly. Namely,
NTL have a type for machine sized integers modulo prime, but
ATM I found no way to use polynomials of machine sized integers
modulo prime. Also, for the test I compiled critical FriCAS
routines at safety 0 (most of the time extra safety checks
are cheap, but in low level code involved here they make
significant difference).
As you can see there is possibility for 50 times speedup and
that brings us within factor of 2 to flint and is better than
my current NTL result.
Concerning your original problem, degree 3 case in flint
took 0.08s, and in NTL about 1.2s. Current regular FriCAS
factorizer needs 15.88s on my machine. AFAICS using
similar methods like in MODFACT it should be possible
to have speed within factor 2-4 to flint. Let me add
that there are other possiblities for faster arithmetic
over finite fields, but my impression is that flint
does not use them: basically it seems that flint
advantage is mainly due to better machine optimization
in gcc compared to sbcl.
Looking again at the problem it is not clear what is the
intent. Is the intent to benchmark finite field factorizer?
Then the example is somewhat atypical because polynomials
split into linear factors. If the intend is to embed
smaller field into bigger one, then there are better
methods. For example, factorizer spends some thime to
find out that polynomials split, this can be skipped
if we know this. For purpose of embedding single
root should be enough, that is cheaper than finding
all roots. In this case we know more: polynomial
will spilt over a subfield, so we can bias factoring
to effectively work in this subfield. And working
in opposite direction may be cheaper: computing power
of single element with high probablity we will get
minimal polynomial for subfield, factoring this
polynomial over smaller field will give us embedding.
On my machine I need 0.92s to compite power and 0.3s
to compite minimal polynomial (which is of degree 3).
Both operations should allows significant speed-up
by using more efficient low level routines.
--
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/20210220164727.GA19590%40math.uni.wroc.pl.
