1.Naive algorithms
Univariate polynomials over C
are implemented in the class polynomial<C,V>, defined in polynomial.hpp. The default variant polynomial_naive assumes that C
is a field, not necessarily commutative. This provides implementations
of the naive algorithms. For instance the product, the division, and
the gcd have quadratic costs.
#include <numerix/rational.hpp>
#include <algebramix/polynomial.hpp>
…
polynomial<rational> x (C(1), 1); // defines the monomial x
polynomial<rational> p= square (x) + 3 * x + 1; |
Remark that you cannot use the infix operation ^ for powering, for it is usually
reserved to bitwise operations. Instead you can use binary powering
with binpow (a, n). For
the sake of efficiency, the monomial must be
constructed as polynomial<C,V>
(C(1), n).
For polynomials over a ring you must add the variant poynomial_ring_naive<V>
defined in polynomial_ring_naive.hpp, that essentially contains implementations for the
subresultants due to Ducos.
2.Divide and conquer algorithms
All classical generic divide and conquer algorithms over any field are
implemented in polynomial_dicho.hpp. Therein is defined the variant polynomial_dicho<V> that implements the Karatsuba product, division with Newton's
inversion algorithm, fast Euclidean sequence, the half-gcd algorithm,
Padé approximants, fast multipoint evaluation and
interpolation, fast multimod and Chinese remaindering. If you want
these algorithms to be applied in you can
modify the above piece of code into:
#include <algebramix/polynomial.hpp>
#include <algebramix/polynomial_dicho.hpp>
#define polynomial_dicho<polynomial_naive> V
…
polynomial<rational,V> x (C(1), 1); // defines the monomial x
polynomial<rational,V> p= square (x) + 3 * x + 1; |
For polynomials over a ring you must add the variant polynomial_ring_dicho<V> defined in
polynomial_ring_dicho.hpp, that essentially contains the half-subresultant algorithm.
3.Asymptotically fast algorithms
Schönhage & Strassen's, and Cantor & Kaltofen's fast
products are implemented in polynomial_schonhage. It supports any ring with unity. This provides the generic a default variant.
4.Special types of coefficients
4.1.Kronecker's substitution
The Kronecker substitution is available for polynomials over
polynomials, hardware or long integers, and also with modular
coefficients. One must include one of the corresponding files:
-
polynomial_polynomial.hpp,
-
polynomial_integer.hpp, polynomial_modular_integer.hpp
-
polynomial_int.hpp, polynomial_modular_int.hpp
4.2.Modulars
If the coefficient ring are modular numbers then a special product is
available from polynomial_modular.hpp: it first computes the product of the polynomials made of the
preimages of the coefficients and reduces the coefficients at the end.
4.3.Complex numbers
For polynomial over complex numbers you must use polynomial_complex.hpp.
4.4.Quotient fields
If coefficients are in a quotient field of type quotient, then one should
include polynomial_quotient.hpp. A special variant is directly available for rational numbers
in polynomial_rational.hpp.
5.Quotient ring
Operations in are available through the class
modular. Special types
of moduli for polynomials is defined in modular_polynomial.hpp.
#include "numerix/rational.hpp"
#include "algebramix/modular_polynomial.hpp"
#define C rational
#define Polynomial polynomial<C>
#define Modular modular<modulus<Polynomial> >
…
Polynomial x (C(1), 1);
Polynomial p= square (x) - 2;
Modular::set_modulus (p);
mmout << binpow (Modular (x), 1000) << "\n"; |
6.Mathemagix
interface
Mmx] |
use "algebramix";
type_mode? := true; |
Mmx] |
x == polynomial (0, 1) |
:
:
Mmx] |
gcd (1 + 2*x + x^2, 1 - x^2) |
:
Mmx] |
discriminant (1 + x + x^2) |
:
:
© 2010 Grégoire Lecerf
Permission is granted to copy, distribute and/or modify this document
under the terms of the
GNU General Public License. If you
don't have this file, write to the Free Software Foundation, Inc., 59
Temple Place - Suite 330, Boston, MA 02111-1307, USA.