These are chat archives for bluescarni/piranha

8th
Mar 2016
Ralf Stephan
@rwst
Mar 08 2016 04:23
We were looking for the fastest way to speed up multivar series in Pynac and the thought process started with what Nemo is doing, ie leveraging flint types. Now to completely implement what they are doing in C++ is likely too much for the student since he also has univar on the plate, so I thought maybe this can be shortened by using Piranha as generic layer. But independently it's an interesting idea. Of course there is still the option to simply use Piranha only but maybe there are benefits from a poly type. Did you compare the fateman benchmark yourself on one machine (silly question I know)?
Francesco Biscani
@bluescarni
Mar 08 2016 09:44
@rwst I had a mail conversation with @certik who actually ran the benchmarks on his machine
I also remember a conversation between Ondrej and Fredrik Johansson (FLINT co-author) about recursive representation of multivariate polys/series, with Fredrik stating that the recursive dense representation they use in Nemo is not optimal for many variables or sparse objects
but I cannot find a reference to this at the moment... might have been a mailing list message
Francesco Biscani
@bluescarni
Mar 08 2016 09:47
ah right, thanks @isuruf !
https://github.com/bluescarni/piranha/blob/poly_division/src/polynomial.hpp#L1201 this is an example of poly with poly coefficients... this is a method that takes a multivariate poly and transforms it into a univariate in the first variable with poly coefficients in the other variables
it's used recursively in the division/GCD code
Francesco Biscani
@bluescarni
Mar 08 2016 09:54
@rwst I like generally a distributed representation for the polynomials rather than a recursive one, but books and the general literature tend to favour the recursive one
in some sense the recursive is better suited for theoretical considerations as you can demonstrate facts and implement algorithms in an inductive fashion
are you familiar with the papers of Pearce and Monagan about the new poly representation in Maple?
it's based on the heap data structure
http://www.cecm.sfu.ca/~rpearcea/ there's some links to papers here
Ralf Stephan
@rwst
Mar 08 2016 09:58
No, and thanks for putting this together. It would be a GSoC project alone, anyway.
Francesco Biscani
@bluescarni
Mar 08 2016 09:58
my understanding is that it's not as fast as Piranha's for multiplication, but it's better suited for division/GCD/Groebner basis as it keeps track of the leading terms
Ralf Stephan
@rwst
Mar 08 2016 09:59
have you ever looked at what giac does? I didn't understand the code at first glance
Francesco Biscani
@bluescarni
Mar 08 2016 10:00
sure I understand that :smile: it's a topic with quite a bit of research in it, I think nobody has found the "best" overall data structure yet
sorry connection problems
no I just looked at GIAC's performance numbers in the past
but never at the code
my understanding is that it's also using hash tables, but GIAC as a project has a much wider scope
Ralf Stephan
@rwst
Mar 08 2016 10:01
Parisse claimed it faster than Singular IIRC but that does not mean so much
Francesco Biscani
@bluescarni
Mar 08 2016 10:02
right yes. Probably Singular is not a good comparison for things like multiplication
my understanding is that its strength lies in Groebner basis computation and things like that
Ralf Stephan
@rwst
Mar 08 2016 10:05
So maybe we'll chose Piranha and use what @isuruf and me were doing in SymEngine as model or even base for Pynac series...
Francesco Biscani
@bluescarni
Mar 08 2016 10:05
sure I can help with that
Ralf Stephan
@rwst
Mar 08 2016 10:06
thanks anyway for the infos
Francesco Biscani
@bluescarni
Mar 08 2016 10:06
no problem, any time
I just wanted to point out that it is really tricky to get something which works well in general, I am seeing it more clearly now that I am working on division/GCD
Ralf Stephan
@rwst
Mar 08 2016 10:08
yes fortunately Pynac series is a clear use case