On Sat, Feb 20, 2021 at 05:47:27PM +0100, Waldek Hebisch wrote: > 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: > > > > > > > > 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 > > > > <snip> > 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.
Correction: header files for such polynomials are hidden under names 'lzz_pX...' and 'lzz_pEX...'. Using them I get 0.006 s for problem above (so slightly better than flint) and 0.345s for orignal factoring in degree 3. A little extra remak: MODFACT in trunk has silly performace bug and time is much longer. Time above is using fixed version. > 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. -- 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/20210220182040.GA26535%40math.uni.wroc.pl.
