Multivariate polynomial factorization

poulard poulard at
Fri Jun 27 09:45:30 CEST 2003

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.

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
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.


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)    | 25 Chemin de Pouvourville    _/
_/ Fax : (33)    | 31432 Toulouse Cedex 04      _/
_/                             | FRANCE                       _/
_/ E-Mail                      |                              _/
_/ - poulard at          |        _/
_/ - poulard at           | _/
_/ - poulard.herve at  |     _/
_/ (plz cc for security)       |                              _/

More information about the GiNaC-list mailing list