Volunteer to continue the work on NTL factorisation bindings
I have created a simple factorisation for polynomials in Q[x] with real roots (source attached, based on [2]) but it's really slow. Creating a reasonable implementation would require much work. An NTL based implementation would be very powerfull and feasible, as said in [1]. I would like to volunteer to continue this work. I have the following questions: 1) Where can I obtain the source of this binding? (or should I start from the code in gTybalt, or from scratch?) 2) Is there any chance such a patch will be included? (this would imply dependecy on NTL) 2a) And if it is compile-time optional? 2b) And if it also included integration of rational functions? 2c) And if it also included integration of trancedental functions? 3) Do you have any related advice, hints or pointers? [1] http://www.ginac.de/pipermail/ginac-devel/2004-August/000695.html [2] http://yacas.sourceforge.net/Algochapter3.html
Hi, Remco Bloemen schrieb:
An NTL based implementation would be very powerfull and feasible, as said in [1]. I would like to volunteer to continue this work.
I have the following questions:
1) Where can I obtain the source of this binding? (or should I start from the code in gTybalt, or from scratch?)
the binding is part of the gtybalt sources. So you have to look at that code. IIRC the relevant code consists of only few lines of code. It is just doing data conversions back and forth and calling NTL in between. I am not so sure whether this approach gives a good performance. NTL is fast, but the conversions ... Maybe your code is already better.
2) Is there any chance such a patch will be included? (this would imply dependecy on NTL)
I don't like the idea of adding another dependency very much. But maybe that is the price to pay. For me it depends on the additional functionality beyond "simple" Q[x] factorization that would be added to GiNaC. Multi-variate factorization, integration, ... that would justify the _non-optional_ inclusion, I think.
2a) And if it is compile-time optional?
Yes, then I would include such a patch even if it is just a simple mono-variate factorization.
2b) And if it also included integration of rational functions? 2c) And if it also included integration of trancedental functions?
See above. Regards, Jens
Hello! On Tue, Aug 28, 2007 at 06:02:08PM +0200, Remco Bloemen wrote:
I have created a simple factorisation for polynomials in Q[x] with real roots (source attached, based on [2]) but it's really slow.
I _think_ there are two reasons for that. First, GiNaC::add and GiNaC::mul are way to abstract to repersent polynomials (especially univariate ones) efficiently. For example, this snippet of code
if(is_exactly_a<add>(poly)) { ex result = 0; for (size_t i=0; i < poly.nops(); i++) { result += polymod2n(poly.op(i), n); } return result; }
involves N = poly.nops() calls to add.eval(), each of them is O(N). poly.op(i) is O(N) too. So, you'd better use std::vector to represent univariate polynomials: void mod2n(std::vector<cln::cl_MI>& result, std::vector<cln::cl_I>& poly, const unsigned int n) { result.reserve(poly.size()); cln::cl_modint_ring R(cln::cl_I(1) << n); for (std::size_t i = 0; i < poly.size(); ++i) result.push_back(R.canonhom(poly[i])); } Secondly, your implementation of mod 2^n arithmetic is really far from optimal.
numeric mod2n(const numeric &p, const int n) { numeric modulus = pow(numeric(2), numeric(n)); return mod(p, modulus); }
Operations on mod 2^n integers and polynomials can (and should) be done using bit shifts (a very fast operation). Actually this is why yacas (and some other software) use them in first place. So, it should be static inline const cln::cl_MI mod2n(const cln::cl_I& p, const unsigned int n) { cln::cl_modint_ring R(cln::cl_I(1) << n); return R.canonhom(p); }
Creating a reasonable implementation would require much work.
Sure.
An NTL based implementation would be very powerfull and feasible, as said in [1]. I would like to volunteer to continue this work.
IMHO, using two different bignum libraries and converting expressions (and numbers) between them is a bad idea. Much better option is to port NTL's algorithms to CLN. Best regards, Alexei -- All science is either physics or stamp collecting.
Alexei, First of all, thank you very much for looking at my code and giving good pointers! It really makes a newcomer feel appreciated. On Wednesday 05 September 2007 15:07:36 Sheplyakov Alexei wrote:
On Tue, Aug 28, 2007 at 06:02:08PM +0200, Remco Bloemen wrote:
I have created a simple factorisation for polynomials in Q[x] with real roots (source attached, based on [2]) but it's really slow.
I _think_ there are two reasons for that. First, GiNaC::add and GiNaC::mul are way to abstract to repersent polynomials (especially univariate ones) efficiently.
Your suggestion of using std::vector was already on my mind, I will certainly implement it. It's just that I wanted to evaluate the NTL way before I would spent time improving my own humble factorizer.
Secondly, your implementation of mod 2^n arithmetic is really far from optimal.
Yes, I am aware of that. I wrote the *2n functions as a temporary solution, mainly because I did not know how to do it efficiently using CLN. Your examples teach me that this can be easily done.
An NTL based implementation would be very powerfull and feasible, as said in [1]. I would like to volunteer to continue this work.
IMHO, using two different bignum libraries and converting expressions (and numbers) between them is a bad idea. Much better option is to port NTL's algorithms to CLN.
I also looked at Singular and I came to the same conclusion that it would be best to port the algorithms. The main reasons was that NTL only supports univariate integer factorization and that is only a fairly small (though performance-wise important) part of full multivariate polynomial factorization over extension fields. Kind regards, Remco
participants (3)
-
Jens Vollinga
-
Remco Bloemen
-
varg＠theor.jinr.ru