Module for Univariate POLynomials with a Direct Access Representation. More...

Classes
struct	monomials

Functions
template<class R >
int	degree (const R &p)

TMPL int	degree (const Polynomial &a)

TMPL int	check_degree (Polynomial &a)

TMPL void	add (Polynomial &r, const Polynomial &a, const Polynomial &b)

TMPL void	add (Polynomial &r, const Polynomial &a, const C &c)

TMPL void	add (Polynomial &r, const C &c)

TMPL void	add (Polynomial &r, const Polynomial &a)

TMPL void	sub (Polynomial &r, const Polynomial &a, const Polynomial &b)

TMPL void	sub (Polynomial &r, const Polynomial &a)

TMPL void	sub (Polynomial &r, const Polynomial &a, const C &c)

TMPLX void	sub (Polynomial &r, const Polynomial &a, const X &x)

TMPL void	sub (Polynomial &r, const C &c)

TMPL void	mul (Polynomial &r, const Polynomial &a, const Polynomial &b)

TMPL void	mul (Polynomial &r, const C &c)
	Multiplication of a polynomial by a monomial or a scalar. More...

TMPL void	mul (Polynomial &a, const Polynomial &b)
	Multiplication of a polynomial by a polynomial;. More...

TMPL void	mul (Polynomial &r, const Polynomial &p, const C &c)

TMPL void	shift (Polynomial &r, const Polynomial &p, int d, int v=0)

TMPL void	div (Polynomial &r, const Polynomial &a, const Polynomial &b)

TMPL void	div (Polynomial &r, const Polynomial &b)

TMPL void	div (Polynomial &r, const C &c)

template<class R >
R::value_type	lcoeff (const R &p)

template<class R >
R::value_type	tcoeff (const R &p)

template<class OSTREAM , class C >
OSTREAM &	print_as_coeff (OSTREAM &os, const C &c, bool plus)

template<class OSTREAM , class C , class VAR >
OSTREAM &	print (OSTREAM &os, const Polynomial &p, const VAR &var)

template<class OSTREAM , class C >
OSTREAM &	print (OSTREAM &os, const Polynomial &p)

template<class R , class C >
void	set_monomial (R &x, const C &c, unsigned n)

template<class R , class S >
void	add_cst (R &r, const S &c)

template<class R , class S >
void	sub_cst (R &r, const S &c)

template<class R >
void	mul_index (R &r, const R &a, const R &b)

template<class R >
void	mul_index_it (R &r, const R &a, const R &b)

template<class R >
void	mul (R &a, const R &b)

template<class R >
void	mul_index (R &a, const R &b)

template<class C , class R >
C	eval_horner (const R &p, const C &c)

template<class C , class R >
C	eval_horner_idx (const R &p, const C &c)

template<class C , class R >
C	eval (const R &p, const C &c)

template<class C , class R >
C	eval_homogeneous (const R &p, const C &a, const C &b)

template<typename POL , typename X >
int	sign_at (const POL &p, const X &x)

template<class R >
void	div_rem (R &q, R &a, const R &b)

template<class R >
void	checkdegree (R &p)

template<class R >
R	diff (const R &p)

template<class R >
void	reciprocal (R &w, const R &p)

template<class R >
void	reverse (R &p, typename R::size_type n)

template<class R >
R::value_type	derive (const R p, typename R::value_type x)

template<class R >
void	reduce (R &p, const typename R::size_type &e)

template<class R , class C >
void	scale (R &t, const R &p, const C &l)

template<class R >
void	diff (R &r, const R &p)

template<class T >
void	reduce (T &p, const typename T::size_type &e)

template<class T >
void	reverse (T &p, int n)

template<class O , class R , class I >
void	eval (O &p, O &dp, const R &Pol, const I &x)

template<class R >
R::value_type	derive (const R &Pol, const typename R::value_type &x)

template<class R , class C >
void	shift (R &p, const C &c)

template<class R , class C >
void	shift (R &r, const R &p, const C &x0)

template<class R , class C >
void	inv_scale (R &r, const R &p, const C &l)

template<class T , class P , class C >
void	convertm2b (T &bz, const P &p, unsigned size, const C &a, const C &b)

template<class R >
void	coeff_modulo (R &r, const typename R::value_type &x)

template<class S , class R >
S	numer (const R &f)

Detailed Description

Module for Univariate POLynomials with a Direct Access Representation.

It contains generic implementations on univariate (dense) polynomials. This set of functions apply when R provides the following methods or definitions:

typename R::value_type;
typename R::size_type;
typename R::iterator;
typename R::reverse_iterator;
iterator_t R::begin();
iterator_t R::end();
value_type R::operator[](int);

Function Documentation

TMPL void mmx::univariate::add	(	Polynomial &	r,
		const Polynomial &	a,
		const Polynomial &	b
	)

inline

TMPL void mmx::univariate::add	(	Polynomial &	r,
		const Polynomial &	a,
		const C &	c
	)

inline

TMPL void mmx::univariate::add	(	Polynomial &	r,
		const C &	c
	)

inline

TMPL void mmx::univariate::add	(	Polynomial &	r,
		const Polynomial &	a
	)

inline

template<class R , class S >

void mmx::univariate::add_cst	(	R &	r,
		const S &	c
	)

inline

TMPL int mmx::univariate::check_degree ( Polynomial & a )

inline

template<class R >

void mmx::univariate::checkdegree ( R & p )

inline

template<class R >

void mmx::univariate::coeff_modulo	(	R &	r,
		const typename R::value_type &	x
	)

template<class T , class P , class C >

void mmx::univariate::convertm2b	(	T &	bz,
		const P &	p,
		unsigned	size,
		const C &	a,
		const C &	b
	)

Convert the representation in the monomial basis to the representation in the Bezier basis of $[a,b]$. The matrix of the change of bases is $(c_{i,j})_{0\le i,j \le d}$ with $c_{i,j}= {{i}\choose{j}}/{{d}\choose{j}}$ if $j\le i$ and $0$ otherwise.

template<class R >

int mmx::univariate::degree ( const R & p )

TMPL int mmx::univariate::degree ( const Polynomial & a )

inline

template<class R >

R::value_type mmx::univariate::derive	(	const R	p,
		typename R::value_type	x
	)

template<class R >

R::value_type mmx::univariate::derive	(	const R &	Pol,
		const typename R::value_type &	x
	)

inline

Return an evaluation of the derivation of an univariate polynomial for the value $x$ . Example:

upoldse<R> p(...);
upoldse<R>::value_type x,d;
d=univariate::derive(p,x);

template<class R >

R mmx::univariate::diff ( const R & p )

inline

The derivative of the polynomial p is put in r.

template<class R >

void mmx::univariate::diff	(	R &	r,
		const R &	p
	)

inline

The derivative of the polynomial p is put in r. r should be allocated wi the correct size.

TMPL void mmx::univariate::div	(	Polynomial &	r,
		const Polynomial &	a,
		const Polynomial &	b
	)

inline

TMPL void mmx::univariate::div	(	Polynomial &	r,
		const Polynomial &	b
	)

inline

TMPL void mmx::univariate::div	(	Polynomial &	r,
		const C &	c
	)

inline

template<class R >

void mmx::univariate::div_rem	(	R &	q,
		R &	a,
		const R &	b
	)

Quotient and remainder of a by b. The polynomial a is modified. At the end of the computation, it is equal to the remainder in the euclidean division. The type R should provide a degree function and a direct access operator.

template<class C , class R >

C mmx::univariate::eval	(	const R &	p,
		const C &	c
	)

inline

template<class O , class R , class I >

void mmx::univariate::eval	(	O &	p,
		O &	dp,
		const R &	Pol,
		const I &	x
	)

inline

Return an evaluation of the polynomial and its derivative at $x$ Example:

upoldse<R> p(...);
upoldse<R>::value_type x,vp,vd;
d=univariate::eval(vp,vd,p,x);

template<class C , class R >

C mmx::univariate::eval_homogeneous	(	const R &	p,
		const C &	a,
		const C &	b
	)

inline

template<class C , class R >

C mmx::univariate::eval_horner	(	const R &	p,
		const C &	c
	)

inline

template<class C , class R >

C mmx::univariate::eval_horner_idx	(	const R &	p,
		const C &	c
	)

inline

template<class R , class C >

void mmx::univariate::inv_scale	(	R &	r,
		const R &	p,
		const C &	l
	)

Scale the variable in the polynomial p by l and put the result r. It computes the coefficients of the polynomial $p(l \, x)$ .

template<class R >

R::value_type mmx::univariate::lcoeff ( const R & p )

inline

Returns the leading coefficient of the polynomial p.

TMPL void mmx::univariate::mul	(	Polynomial &	r,
		const Polynomial &	a,
		const Polynomial &	b
	)

inline

TMPL void mmx::univariate::mul	(	Polynomial &	r,
		const C &	c
	)

inline

Multiplication of a polynomial by a monomial or a scalar.

TMPL void mmx::univariate::mul	(	Polynomial &	a,
		const Polynomial &	b
	)

inline

Multiplication of a polynomial by a polynomial;.

TMPL void mmx::univariate::mul	(	Polynomial &	r,
		const Polynomial &	p,
		const C &	c
	)

inline

template<class R >

void mmx::univariate::mul	(	R &	a,
		const R &	b
	)

inline

template<class R >

void mmx::univariate::mul_index	(	R &	r,
		const R &	a,
		const R &	b
	)

inline

template<class R >

void mmx::univariate::mul_index	(	R &	a,
		const R &	b
	)

inline

template<class R >

void mmx::univariate::mul_index_it	(	R &	r,
		const R &	a,
		const R &	b
	)

inline

template<class S , class R >

S mmx::univariate::numer ( const R & f )

template<class OSTREAM , class C , class VAR >

OSTREAM & mmx::univariate::print	(	OSTREAM &	os,
		const Polynomial &	p,
		const VAR &	var
	)

inline

template<class OSTREAM , class C >

OSTREAM & mmx::univariate::print	(	OSTREAM &	os,
		const Polynomial &	p
	)

inline

template<class OSTREAM , class C >

OSTREAM & mmx::univariate::print_as_coeff	(	OSTREAM &	os,
		const C &	c,
		bool	plus
	)

template<class R >

void mmx::univariate::reciprocal	(	R &	w,
		const R &	p
	)

Compute the reciprocal of the univariate polynomial $p$ . The result is given in $w$ . We assume $p[0] != 0$ . For this, we consider the equation $f(w)\ =\ P - \frac{1}{w}\ =\ 0$ , where $P=p(z)$ , $w=w(z)= \frac{1}{p(z)}$ over the ring of formal power series in $z$ , and apply Newton's iteration to this equation. So we have : $w_{0}=\frac{1}{p(0)}$ , and $w_{j+1}=w_{j}(2-Pw_{j}$ where $j=0,1,\ldots$ By reducing the different polynomials modulo $z^{2^{j+1}}$ at each step, we have two convolutions of two pairs of vectors of dimensions at most $2^{j+1}=$ by step.

template<class R >

void mmx::univariate::reduce	(	R &	p,
		const typename R::size_type &	e
	)

template<class T >

void mmx::univariate::reduce	(	T &	p,
		const typename T::size_type &	e
	)

inline

Truncate an univariate polynomial $p$ which is modified in output, with a new degree of $e-1$ .

template<class R >

void mmx::univariate::reverse	(	R &	p,
		typename R::size_type	n
	)

template<class T >

void mmx::univariate::reverse	(	T &	p,
		int	n
	)

inline

Reverse the coefficients of an univariate polynomial, it is performed in place. For a call of this function, the list of arguments must specify, in last, an instance of univariate, the generic type $T$ is assumed to be a valid class of univariate polynomial. Example of such a call:

upoldse<...> p(...);

univariate::reverse(p,i);

template<class R , class C >

void mmx::univariate::scale	(	R &	r,
		const R &	p,
		const C &	l
	)

Scale the variable in the polynomial p by l and put the result r. It computes the coefficients of the polynomial $p(l \, x)$ .

template<class R , class C >

void mmx::univariate::set_monomial	(	R &	x,
		const C &	c,
		unsigned	n
	)

inline

TMPL void mmx::univariate::shift	(	Polynomial &	r,
		const Polynomial &	p,
		int	d,
		int	v = `0`
	)

inline

template<class R , class C >

void mmx::univariate::shift	(	R &	p,
		const C &	c
	)

Inplace shift of the polynomial r at the point x0. It computes the coefficients of the polynomial $p(x+x_{0})$ .

template<class R , class C >

void mmx::univariate::shift	(	R &	r,
		const R &	p,
		const C &	x0
	)

Shift the polynomial p at the point x0 and put the result in r. In other words, it computes the coefficients of the polynomial $p(x+x_{0})$ .

template<typename POL , typename X >

int mmx::univariate::sign_at	(	const POL &	p,
		const X &	x
	)

inline

TMPL void mmx::univariate::sub	(	Polynomial &	r,
		const Polynomial &	a,
		const Polynomial &	b
	)

inline

TMPL void mmx::univariate::sub	(	Polynomial &	r,
		const Polynomial &	a
	)

inline

TMPL void mmx::univariate::sub	(	Polynomial &	r,
		const Polynomial &	a,
		const C &	c
	)

inline

TMPLX void mmx::univariate::sub	(	Polynomial &	r,
		const Polynomial &	a,
		const X &	x
	)

inline

TMPL void mmx::univariate::sub	(	Polynomial &	r,
		const C &	c
	)

inline

template<class R , class S >

void mmx::univariate::sub_cst	(	R &	r,
		const S &	c
	)

inline

template<class R >

R::value_type mmx::univariate::tcoeff ( const R & p )

inline

Return the tail coefficient of the polynomial p.

Classes

Functions

Detailed Description

Function Documentation