Switch UniPoly to cl_UP_MI
Dear all, with the latest commit 2a5d912dc940... the polynomial factorization now uses the cln class cl_UP_MI instead of the ad-hoc invented UniPoly class. Maybe it is interesting to note that my benchmarks show no improvements in speed at all (rather some tiny change for the worse). This is kind of disappointing, because I expected some decent improvement due to the inefficient and times stupid ways UniPoly was set up. Maybe this recent remark on the cln mailing list gives a good explanation for that finding: Alexei Sheplyakov schrieb:
For example, the same univariate GCD code works about 3 -- 10 times faster (and uses less memory) if I use std::vector<cl_I> instead of cl_UP.
Well, at least the line count in factor.cpp has decreased. Regards, Jens
Dear Jens,
This is kind of disappointing, because I expected some decent improvement due to the inefficient and times stupid ways UniPoly was set up.
You might want to try polynomial/upoly.hpp. Feel free to ask me to implement the operations you need, propose any reasonable API changes, etc. Best regards, Alexei -- All science is either physics or stamp collecting.
Dear Alexei, Alexei Sheplyakov schrieb:
You might want to try polynomial/upoly.hpp. Feel free to ask me to implement the operations you need, propose any reasonable API changes, etc.
for the next three/four weeks I will not change to upoly/umodpoly. I want to try more efficient algorithms first, and there is still a strange bug in the multivariate case that happens just occasionally and that I need to catch. For modular polynomials I only need *,+,- and the functions in lines 105-350 in factor.cpp like div/rem/gcd/... You are probably going to implement them anyway, I guess. I don't care much about the API as long as it allows for efficient and elegant usage. Since you are using umodpoly for a modular gcd you have the same requirements as I do, so just got ahead with it and do it as you like. Side question: is the cln code (cl_UP_UI) going to improve in the future or is the development stuck? Eventually, I'll going to move factor.cpp into the ginac/polynomial directory. Maybe I will split the modular matrix code into a separate file as well. BTW, do you plan to have a multivariate (modular) polynomial class? At the moment, in factor.cpp I use the silly make_modular() function that looks at coefficients in a ex and changes them to their ring value. Dirty hack it is. Regards, Jens
participants (2)
-
Alexei Sheplyakov
-
Jens Vollinga