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 -- 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/CAHnU2dZCdz%3DOAkrPiLOAkW1wrJ4ratDF_GC5XK6sra5FoEhGLw%40mail.gmail.com.
