[/digression stop] sorry. Have a good day! Le lun. 22 févr. 2021 à 16:19, Grégory Vanuxem <[email protected]> a écrit : > > In fact I've been thinking since some time to optionally interface > Julia for basic (and linear algebra) numerical things. The primary > purpose of Julia is numerical mathematics. It's very easy to link it > in C (a script in Julia is given) and Julia is available for Mac, > Linux, Windows, FreeBSD, maybe others. That discussion remains me that > but I have/had not in mind this interaction for other things than fast > numerical mathematics, FriCAS is about symbolic mathematics from my > point of view. > > Le lun. 22 févr. 2021 à 15:46, Grégory Vanuxem <[email protected]> a écrit : > > > > I see that too recently. At the beginning of COVID in the EU, I > > compared Flint vs FriCAS for multivariate polynomial operations. At > > that time nested univariate polynomials were needed. I use Nemo to do > > those things, a Julia package (https://github.com/Nemocas/Nemo.jl). > > > > Le lun. 22 févr. 2021 à 15:16, Dima Pasechnik <[email protected]> a écrit : > > > > > > 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. > > > > > > > > -- > > __ > > G. Vanuxem > > > > -- > __ > G. Vanuxem
-- __ 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/CAHnU2da1f-zVgeqnQbDX2%3DkEYBKyHcAbPD4-F%3D939hrazVe1Fw%40mail.gmail.com.
