[GiNaC-devel] Factoring, again (Factory)

[Ralf Stephan]

Hello,

my current work on partial fraction decomposition ultimately demands
a working implementation of multivariate factoring and, therefore,
I would like to refresh discussions about factoring in GiNaC, as there
have been some developments since the last thread on it which was years
ago[0].

 "Singular is a Computer Algebra system for polynomial computations with
  emphasize on the special needs of commutative algebra, algebraic
  geometry, and singularity theory. [...]"

That's the blurb about Singular[1], from their Readme and, guess,
they even have multivar. factoring. Even better, the factoring module
(named 'Factory') is independent from the rest, and can so be downloaded
as C++ source[2]. From the Readme:

 "Factory is a C++ class library that implements a recursive representation
  of multivariate polynomial data.  It is being developed by Ruediger Stobbe
  and Jens Schmidt at the University of Kaiserslautern as an independent and
  self-contained part of the computer algebra system Singular (developed by
  G.-M. Greuel, G. Pfister and H. Schoenemann).

  Factory handles sparse multivariate polynomials over different
  coefficient domains, such as Z, Q and GF(q), as well as algebraic
  extensions over Q and GF(q) in an efficient way.  Factory includes
  algorithms for computing univariate and multivariate gcds, resultants,
  chinese remainders, and several algorithms to factorize univariate
  polynomials over the integers and over finite fields.  Factorization of
  multivariate polynomials over the integers is in beta test stage.

  The interface to the polynomial system of Factory is provided by a single
  class `CanonicalForm' which can deal with elements of the coefficient
  domain as well as polynomials.  Using operator overloading, you can handle
  polynomial data similarly to built-in types such as the machine integers.
  [...]"
	
Factory optionally uses NTL for univariate factoring and GCD computation. 
Factory itself is used by another package within Singular that implements 
factoring over algebraic extensions and other algorithms, the name is 
libfac[3] by Michael Messollen. Both use the same recursive CanonicalForm.

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?

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.


Thanks for your time. Sincerely,
ralf

[0] http://thep.physik.uni-mainz.de/pipermail/ginac-devel/2001-July/000270.html
[1] http://www.singular.uni-kl.de
[2] ftp://www.mathematik.uni-kl.de/pub/Math/Singular/SOURCES/Singular-factory-2-0-5.tar.gz
[3] ftp://www.mathematik.uni-kl.de/pub/Math/Singular/SOURCES/Singular-libfac-2-0-5.tar.gz