[GiNaC-devel] Factoring, again (Factory)

[bernard.parisse]

>It immediately comes to mind that it should now be easy to get multivariate
>factoring for ginac. Just use NTL and those parts of Factory that are not
>already in ginac. Although there is another possibility (add Factory only)
>the Factory source says itself that NTL is faster. However, I see a third
>plan: if you already accept including another library then why not libpari?
>Univariate factoring in Pari is as fast as NTL, both use van Hoeij, and
>Pari has much more for the work, starting with a mature integer factoring
>package etc. All three mentioned packages are distributed under GPL.
>
>So, assuming I have summarized the situation correctly, which way?
>
>  
>
After experiencing both for integration inside giac,
I would recommend NTL over pari, because pari is a C library
that may cause conflict names (at compile time but also at
link time). Also I don't know if NTL supports threads, but I'm sure
pari does not.
I did not try direct integration of singular yet, I'm planning to do it
for Groebner basis, but if it gives better performance for factorization,
I will also use it for that purpose.
Another solution I would recommend (but I'm not impartial of course:-))
would be to build a GiNaC::ex to giac::gen converter, that would bring
to GiNaC multivariate factorization as well as all the other mathematical
functionnalities of giac (e.g. symbolic integration, etc.). That would 
factor(!)
the cost of integration of advanced math functionnalities over one library.

>My other question is a plea: does anyone of you have a good overview over
>what is to do algorithmically to get multivariate factoring, given an existing
>univariate implementation? I'm not at a university but I'd shell out the EUR 8 
>at Subito for a copy of a good introductory or review article. 
>So, please send refs/results to me or to the list.
>  
>
If you can read French, giac multivariate factorization algorithm is 
documented
on my webpage. First make some random evaluation to see
if the 1-variable evaluated polynomial is irreducible, if not choose a 
variable
so that the degree is the smallest possible, then evaluate other 
variables one by one
and reconstruct the factorization using symmetric representation like
for the heuristic GCD (this multivariate factorization is relatively 
easy to program
once you have univariate factorization).
There are probably more efficient algorithms on the market, I'd also be 
happy
if someone has good references.

Bernard Parisse
www-fourier.ujf-grenoble.fr/~parisse