Multivariate polynomial factorization

[Richard B. Kreckel]

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 at GiNaC.DE>
<http://www.ginac.de/~kreckel/>