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? :-(
Yes. > I guess, we need fast polynomial multiplication here. > Actually, Marc Moreno Maza implemented it. > > http://fricas.github.io/api/UnivariatePolynomialMultiplicationPackage > Well, it would be significant effort to decide when to use it and when not. And for your example I would expect something between no speedup and say 2 times speedup. You apparently looked at profiler report but did not see what is visible from the report. First, most of actual compute time goes into division with remainder (Lisp TRUNCATE). Next, actual compute time is rather small compared to various overheads. This example actually nicely illustrate why generic code is frequently much slower than specialized one. Namely, FiniteField uses univariate polynomials as representation, that is arithmetic operations are taken from SparseUnivariatePolynomial, which allocate a list node for each term and used arithmetic from coefficient domain, that is PrimeField(43). Now, each operation in PrimeField uses division with reminder as final step (that is why TRUNCATE dominates runtime). This division is a single machine instruction, but is done as a Lisp function call (because Lisp does not know that arguments are machine-size integers). Efficient arithmetic with modular polynomials is more like U32VectorPolynomialOperations. Namely, one perfoms several arithmetic operations and does division with remainder only as last step. One keeps coefficients in specialized arrays (like U32Vector), to avoid cost of memory menagement needed for lists. And one uses type-specific operations which can be compiled to inline code instead of function calls. 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 would expect 10 times faster than current version or more, but ATM it is just a wild guess. One possible trap is that in sbcl allocating vectors is much more expensive than allocating list node (it should be the opposise as vector actually require less work...), so for small degree (say 2 or 3) current implementation is likely to be faster. Also, U32Vector and friends assume coefficients of limited size. There are other ways to speed up factorization. I am not sure if they would help in this case. Anyway, before looking at other tricks one should invest in fast low-level implementation as this would give biggest speedup and decide if anything more is really needed/helpful. -- 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/20201020185027.GA9995%40math.uni.wroc.pl.
