Multivariate polynomial factorization
Dear all, I have a great challenge to manage and a deep thinking before beginning the developpement. First before entering into the real subject I wish tell you (if it has not been before) that GiNaC+CLN compile well on W2K under cygwin with gcc (gcc version 3.2 20020927 (prerelease)) All chech and tests are ok! Great job. NOW THE REAL SUBJECT OF THE MAIL -------------------------------- For one of our project WE DEFINITLY need a package for multivariate polynomial factorization under Z. For this I will have rapidely the man.power to begin this great challenge (next week). My great wish would be to work within open-source framework. As this subject is one of the ToDo list of GiNac, and a very difficult task. Before compiling GiNaC, I beleived that I could use it as a native library un Win32. But it seems that not, unless modification. Perhaps someone has did it ? I have a constraint that I can't modify : I MUST BE ABLE to use and link with a classic native win32 application. So, unless someone tell me the modification to do to be able to compile cln + ginac under VC6++ I cannot use ginac as a basis for further developpment. ----------------------------------------------------------- The solution for me today is the use of NTL (which compile well with VC6) as univariate basis. ----------------------------------------------------------- BUT the developpement of this package under NTL could serve as a basis for GiNac also ! So I need you help for this developpement at a information level. --------------------------------------------------------- What is today the best method for multivariate polynomial factorization under Z ? --------------------------------------------------------- I have the old algorithm from Berlekamp & Hensel for univariate (p-adique method) and only an extension for multivariate, but the algorithm complexity seems to be very high, and I guess that new algorithms have been found far now ? Someone could help me to indicate what is today the best algorithm for this task ? REMARK = The rapidity and accuracy of the result of such task made by Maple5 indicates that there should be a quit rapid algorithm ! For finish this - call to contribution - , I must be honest and indicate that the polynom I have to factorize are little special : - they are very very very long in term of monomial : the number of monomial could be 100, 1000 !!! - they could be a lot of variable (when I say a lot, it could be 10 and more) !!!! - THEY ARE homogeneous : the total degree of monomial are always the same - The coefficient of each monomial is : 1, 2 or not very high - IT SEEMS, after lot experiment under Maple5 that they are squarre free (BUT we have not demonstrate this assertion) UNDER this condition I can tell you that the kernel of Maple5 (in Matlab), for a HUGE HUGE polynomial like I describe, result is almost immediate !!!!! Very very speed. I hope that it will interest you to collaborate and help me to develop this piece of software under open-source. Herve PS = If you the modification to do to GiNaC to be able to be a native win32 library is not to complex I promiss to collaborate to do this task. Thank you, if you have read all :-) _/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/ _/ Dr Herve Poulard | ACTIA - ACTIELEC Hold. _/ _/ Research Manager | BP 4215 _/ _/ Tel : (33) 5.61.17.68.79 | 25 Chemin de Pouvourville _/ _/ Fax : (33) 5.61.55.42.31 | 31432 Toulouse Cedex 04 _/ _/ | FRANCE _/ _/ E-Mail | _/ _/ - poulard@actia.fr | http://www.actia.com/ _/ _/ - poulard@laas.fr | http://www.laas.fr/~poulard/ _/ _/ - poulard.herve@wanadoo.fr | http://www.actielec.com/ _/ _/ (plz cc for security) | _/ _/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/
Dear Herve, On Fri, 27 Jun 2003, poulard wrote:
I have a great challenge to manage and a deep thinking before beginning the developpement.
It is always advised to do some deep thinking before embarking on a great and challenging venture. [...]
So, unless someone tell me the modification to do to be able to compile cln + ginac under VC6++ I cannot use ginac as a basis for further developpment.
I don't know what VC6++ is but in case you mean the MSVC++6 compiler you are hosed. It's unprofessional to even think of touching this piece of garbage. You should really stay away from it. Far away. It has, however, come to our attention, that the situation has improved considerably with MSVC++7.1.
----------------------------------------------------------- The solution for me today is the use of NTL (which compile well with VC6) as univariate basis. -----------------------------------------------------------
BUT the developpement of this package under NTL could serve as a basis for GiNac also !
Sure. NTL is a respectable package and should be used for this kind of thing.
--------------------------------------------------------- What is today the best method for multivariate polynomial factorization under Z ? ---------------------------------------------------------
-------------------------------------------------------------------------- Do the Hensel construction and factorize in Z[x], possibly using NTL, then lift back. --------------------------------------------------------------------------
I have the old algorithm from Berlekamp & Hensel for univariate (p-adique method) and only an extension for multivariate, but the algorithm complexity seems to be very high, and I guess that new algorithms have been found far now ? Someone could help me to indicate what is today the best algorithm for this task ?
Point your favored search engine at the name "Mark van Hoeij" and browse the papers you there find.
REMARK = The rapidity and accuracy of the result of such task made by Maple5 indicates that there should be a quit rapid algorithm !
For finish this - call to contribution - , I must be honest and indicate that the polynom I have to factorize are little special : - they are very very very long in term of monomial : the number of monomial could be 100, 1000 !!!
That's not very very very long, that's still sane.
- they could be a lot of variable (when I say a lot, it could be 10 and more) !!!!
That's not a lot, that's quite moderate.
- THEY ARE homogeneous : the total degree of monomial are always the same
Okay.
- The coefficient of each monomial is : 1, 2 or not very high
That's fine.
- IT SEEMS, after lot experiment under Maple5 that they are squarre free (BUT we have not demonstrate this assertion)
Never mind. [...]
PS = If you the modification to do to GiNaC to be able to be a native win32 library is not to complex I promiss to collaborate to do this task.
I herewith promise you that the problems to make CLN/GiNaC run under Windows are negligible. Very very very minor. Just start reading cln/include/modules.h. Best Regards -richy. -- Richard B. Kreckel <Richard.Kreckel@GiNaC.DE> <http://www.ginac.de/~kreckel/>
participants (2)
-
poulard
-
Richard B. Kreckel