Hi everyone, can you tell me what's the current situation regarding polynomial factorization in GiNaC? According to your wishlist, it's still missing, but I've just read some mails in this list saying that some people are working on the task. I'm a student of mathematics, and my diploma thesis is about polynomial factorization. I'm interested in both factorization in Z[x] and algebraic extensions, and I wonder if I could implement some algorithms or contribute to any ongoing projects. Wolfgang By the way, I've found out how to declare a polynomial ring over modular integers in CLN, so I don't need an example any more.
Hi there, On Thu, 5 Jul 2001, Wolfgang Abele wrote:
can you tell me what's the current situation regarding polynomial factorization in GiNaC? According to your wishlist, it's still missing, but I've just read some mails in this list saying that some people are working on the task.
Not that I knew of...
I'm a student of mathematics, and my diploma thesis is about polynomial factorization. I'm interested in both factorization in Z[x] and algebraic extensions, and I wonder if I could implement some algorithms or contribute to any ongoing projects.
Factorization in Z[x] is something that would be somewhat outside the normal GiNaC usage. As you have already found out there is no support for univariate polynomials over, say, Z. The reason for this is threefold: 1) for our physics applications here this is uninteresting, 2) we needed the more general expressions anyways and 3) implementation-wise this is the more trivial case anyway and already cleanly implemented in other libraries, CLN for instance. However, factorization in GiNaC would become really interesting as soon as one considers all the lifting up to multivariate polynomials over Z (and maybe algebraic extensions but I think these are not the main difficulty). If this is in any way tractable, I would suggest not investing too much time into factorization over Zp[x] by maybe implementing this in CLN -- which by the way would be a good place for factorization. Instead, maybe what should be done is use Victor Shoup's GPL'ed library NTL which seems to be the powerhorse in this field. But then again, I am not an expert in this field and would be glad to be convinced otherwise. Suggestions?
By the way, I've found out how to declare a polynomial ring over modular integers in CLN, so I don't need an example any more.
Cool! Regards -richy. -- Richard Kreckel <Richard.Kreckel@Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>
time into factorization over Zp[x] by maybe implementing this in CLN -- which by the way would be a good place for factorization. Instead, maybe what should be done is use Victor Shoup's GPL'ed library NTL which seems to be the powerhorse in this field. I've played around with NTL a bit, and once you've got the hang of using
Am Freitag, 6. Juli 2001 13:36 schrieben Sie: those numerous conversions, I find it quite easy to work with. When it comes to factoring polynomials over Z[x] or Zp[x], NTL is the best tool you can get. So you could do a lot worse than integrate NTL in GiNaC. I don't know, though, how this integration should be done technically since NTL uses its own number classes that may confict with CLN's. Also, NTL doesn't support multivariate polynomials, calculations in Q, and algebraic extensions of Q. As for the ginsh installation, yes, you were right. The rpms worked fine. Don't know why I didn't use them in the first place. Wolfgang
Hi there, On Sat, 7 Jul 2001, Wolfgang Abele wrote:
I've played around with NTL a bit, and once you've got the hang of using those numerous conversions, I find it quite easy to work with. When it comes to factoring polynomials over Z[x] or Zp[x], NTL is the best tool you can get. So you could do a lot worse than integrate NTL in GiNaC. I don't know, though, how this integration should be done technically since NTL uses its own number classes that may confict with CLN's.
That should not be a real problem. The newest version of NTL is fully powered by GMP, so the underlying representation is the same. Also, Victor is wise enough to target for ANSI C++ and he even has wrapped all his bases into a namespace. Care has to be taken for a couple of exceptions like CLN's immediate data types and so on but if serious interest arises I could provide reasonable adaptor stuff.
Also, NTL doesn't support multivariate polynomials, calculations in Q, and algebraic extensions of Q.
Q is a no-brainer once the lifting is in place. It is the latter which we know nothing about over here. Are algebraic extensions really difficult? I remember Bernard Parisse once claimed they are not. Bernard? Regards -richy. -- Richard Kreckel <Richard.Kreckel@Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>
"Richard B. Kreckel" wrote:
Also, NTL doesn't support multivariate polynomials, calculations in Q, and algebraic extensions of Q.
Q is a no-brainer once the lifting is in place. It is the latter which we know nothing about over here. Are algebraic extensions really difficult? I remember Bernard Parisse once claimed they are not. Bernard?
Factoring over algebraic extension is indeed not difficult. The algorithm can be found for example in the excellent book of number theory of Henri Cohen (See algorithm 3.6.4 in Henri Cohen book). In short, if P(X,Y) is a polynomial of X where Y denotes the algebraic extension, and Q(Y) the minimal polynomial of Y, you compute the resultant N(X) with respect to Y of P(X+kY,Y) and Q(Y), where k is an integer such that the resultant N is square-free. Then the factors of P(X,Y) are the gcd of the factors of N(X+kY) and Q(Y). The implementation in giac is in the gausspol.cc file (functions ext_factor and algfactor). BTW, I have not checked NTL recently, but last year, it did not implement the best reconstruction algorithm which is AFAIK the knapsack algorithm (based on LLL). Did that change?
Am Sonntag, 8. Juli 2001 13:56 schrieben Sie:
Factoring over algebraic extension is indeed not difficult. In short, if P(X,Y) is a polynomial of X where Y denotes the algebraic extension, and Q(Y) the minimal polynomial of Y, you compute the resultant N(X) with respect to Y of P(X+kY,Y) and Q(Y), where k is an integer such that the resultant N is square-free. Then the factors of P(X,Y) are the gcd of the factors of N(X+kY) and Q(Y). This is the standard Trager algorithm. Like you're saying, you need to have a gcd over extensions and resultant as subroutines. If Richy provides that adaptor stuff, I'll try and implement Trager. If anybody's interested in the more difficult multivariate factorization I could provide him or her with a step-by-step guide to start with.
BTW, I have not checked NTL recently, but last year, it did not implement the best reconstruction algorithm which is AFAIK the knapsack algorithm (based on LLL). Did that change? There is an implementation for NTL written by Paul Zimmermann. It's linked on
Incidentally, the problem with Trager is that it soon becomes inefficient with high degree polynomials. This is because the polynomial's coefficients and degree become much bigger in the norm polynomial. Also, the norm tends to have many modular factors. People are currently looking into whether Trager can be improved by the new knapsack algorithm, either through faster factorization of the norm or a direct application to the algebraic extensions. the NTL web site. Regards, Wolfgang
Gentlemen, we wrote some small routines which integrates the factorization of univariate polynomials into the GiNaC framework. The hard work is done by the NTL library, we just wrote the necesarry conversion routines for (possibly very long) integers and a function ex polyfactor( const ex &PolyIn, const symbol &x ) which factorizes PolyIn if it is a univariate polynomial in x. The source code is in the latest verstion of gTybalt (0.0.6) and is quite independent of gTybalt. Feel free to use this code, we don't have any plans to move on to multivariate polynomials. Stefan
Can anybody tell me how to include Stefan's conversion routines from gtybalt in GiNaC? Should I write a symbolic function or add a class or copy the routines in normal.cpp and normal.h and 'make' GiNaC again? (The latter won't work with me, though, because I get those ginsh error messages no matter if I use readline 4.1 or 4.2 (the bug is supposedly fixed in 4.2))
Hence, the general mutivariate stuff would be what is really suited for GiNaC. But if you think that doing univariate first is the right thing to do in order to get started with factorization Multivariate factorization is always reduced to univariate factorization. So you've got to have it in GiNaC, even if it's just a subroutine.
there is currently no class that represents algebraic extensions. Representation is another no-brainer, as far as I can see, since it should just hold one expression which represents the zero. Yes, that's right. Computing the polynomial remainder of a division is already implemented, isn't it? Later we also may need a routine to compute the primitive element for a tower of extensions.
our GCD routines are not prepared for extensions. Is that needed? We would need one as a subroutine for Trager. Trager, by the way, can handle multivariate polynomials as well. Is it difficult???applies to The algorithm isn't, which doesn't imply that's it's also easy to implement, at least not as far as I'm concerned.
Servus, Wolfgang
On Mon, 9 Jul 2001, Wolfgang Abele wrote:
This is the standard Trager algorithm. Like you're saying, you need to have a gcd over extensions and resultant as subroutines. If Richy provides that adaptor stuff, I'll try and implement Trager. If anybody's interested in the more difficult multivariate factorization I could provide him or her with a step-by-step guide to start with.
Err,... the problem is that we never bothered with univariate polynomials in GiNaC. You can of course declare them using the sparse general representation provided by classes `add' and `mul'. Then you need a conversion routine from NTL's data type to this one and vice-versa. Is that what you are looking for? (It seems like Stefan has written this already; I'll look into it this weekend.) However, nothing prevents people from poking multivariate polynomials into such a factorizer. Hence, the general mutivariate stuff would be what is really suited for GiNaC. But if you think that doing univariate first is the right thing to do in order to get started with factorization, then please go ahead! Two remarks: there is currently no class that represents algebraic extensions. Representation is another no-brainer, as far as I can see, since it should just hold one expression which represents the zero. Also, our GCD routines are not prepared for extensions. Is that needed? Is it difficult??? Regards -richy. -- Richard Kreckel <Richard.Kreckel@Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>
participants (4)
-
Bernard Parisse
-
Richard B. Kreckel
-
Stefan Weinzierl
-
Wolfgang Abele