Hi Waldek, all, If that matters, I know that Victor Shoup maintains a set of benchmarks that compares NTL vs Flint. He even spotted a recently introduced bug in Flint via his set (fixed since). If you want here is a link of some of his results : https://libntl.org/benchmarks.pdf.
Cheers, Le sam. 20 févr. 2021 à 17:47, Waldek Hebisch <[email protected]> a écrit : > > 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. -- __ G. Vanuxem -- 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/CAHnU2dZD86zUL47-rw8%3DzJ3ihKNxVqmDNt85iABps-77DB8Qmg%40mail.gmail.com.
