Multivariate polynomial factorization

poulard poulard at actia.fr
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.

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 at actia.fr          | http://www.actia.com/        _/
_/ - poulard at laas.fr           | http://www.laas.fr/~poulard/ _/
_/ - poulard.herve at wanadoo.fr  | http://www.actielec.com/     _/
_/ (plz cc for security)       |                              _/
_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/




More information about the GiNaC-list mailing list