On Mon, Feb 22, 2021 at 1:00 PM Grégory Vanuxem <[email protected]> wrote: > > 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.
flint nowadays does multivariate polynomial operations (no Groebner bases though), something what NTL does not do at all. > > 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. -- 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/CAAWYfq2UyPzSRnprSKhntvmN2x7hpaYPfWNtVHEY3q5NoX8YOA%40mail.gmail.com.
