Implement modular multivariate GCD (based on chinese remaindering algorithm).
authorAlexei Sheplyakov <varg@metalica.kh.ua>
Mon, 19 Jan 2009 06:45:38 +0000 (08:45 +0200)
committerJens Vollinga <jensv@balin.nikhef.nl>
Tue, 3 Feb 2009 12:16:23 +0000 (13:16 +0100)
commit45b1e47372090352ac5af655b32473df2abab23b
tree0ed4dbc772e5450188e249819ed55e646b4dcfbb
parent3f0b0165865bbb297901e9542fced88a0e32298e
Implement modular multivariate GCD (based on chinese remaindering algorithm).

Both algorithm and implementation are a bit inefficient:

* algorithm does not make use of sparseness of inputs (and most of
  multivariate polynomials are quite sparse)
* GiNaC's expressions are essentially immutable. Thus some simple
  operations (i.e. multiplying a polynomial by an element of the base ring)
  are prohibitively expensive.
* All numbers (i.e. GiNaC::numeric objects) are heap allocated.

Still it's much faster (~5x on bivariate polynomials, ~100x on 3-variate
ones) than (subresultant) PRS algorithm, so gcd() uses modular algorithm
by default.
22 files changed:
ginac/Makefile.am
ginac/normal.cpp
ginac/normal.h
ginac/polynomial/chinrem_gcd.cpp [new file with mode: 0644]
ginac/polynomial/chinrem_gcd.h [new file with mode: 0644]
ginac/polynomial/collect_vargs.cpp [new file with mode: 0644]
ginac/polynomial/collect_vargs.h [new file with mode: 0644]
ginac/polynomial/debug.hpp
ginac/polynomial/divide_in_z_p.cpp [new file with mode: 0644]
ginac/polynomial/divide_in_z_p.h [new file with mode: 0644]
ginac/polynomial/euclid_gcd_wrap.h [new file with mode: 0644]
ginac/polynomial/eval_point_finder.h [new file with mode: 0644]
ginac/polynomial/mgcd.cpp [new file with mode: 0644]
ginac/polynomial/newton_interpolate.h [new file with mode: 0644]
ginac/polynomial/optimal_vars_finder.cpp [new file with mode: 0644]
ginac/polynomial/optimal_vars_finder.h [new file with mode: 0644]
ginac/polynomial/pgcd.cpp [new file with mode: 0644]
ginac/polynomial/pgcd.h [new file with mode: 0644]
ginac/polynomial/poly_cra.h [new file with mode: 0644]
ginac/polynomial/primes_factory.h [new file with mode: 0644]
ginac/polynomial/primpart_content.cpp [new file with mode: 0644]
ginac/polynomial/smod_helpers.h [new file with mode: 0644]