Re: [boost] [gsoc2008] Polynomial Library.

From: Zero Mind (lord.zerom1nd_at_[hidden])
Date: 2008-03-25 08:24:50

Pawel Kieliszczyk wrote:
> My idea for a GSoC project was to biuld
> an advanced library for polynomial manipulation.
> Boost offers a simple class with basic operations here:
>
http://svn.boost.org/svn/boost/trunk/libs/math/doc/sf_and_dist/html/math_toolkit/toolkit/internals2/polynomials.html
> and usefull functions here:
>
http://svn.boost.org/svn/boost/trunk/libs/math/doc/sf_and_dist/html/math_toolkit/toolkit/internals1/rational.html
>
> John Maddock suggested me via e-mail
> to improve and extend this library.
> I would like to introduce to you my proposals.
>
> What could be added?
> - multiplication algorithm using FFT
> - '/', '/=', '%' and '%=' operators
> - greatest common divisor of polynomials
> - factorisation
> - derivatives and integrals
> - conversions between various polynomial forms
> - faster evaluation of a polynomial
> - finding a polynomial if n points are given (degree of a polynomial is
n-1)
> - I am still thinking.
>
> Generally speaking the library would become more advanced.

Hi again.

Here are some of proposed ideas for Boost.Polynomial:

1. Now there is a special function for evaluation. I think operator() woudl
be comfortable and also intuitive. Short example:

int a[] = {3, 4, 5};
polynomial<int> p(a, 2);
cout << "p(4) = " << p(4) << endl; // p(4) = 99

2. Fast swap function (in constant time) using vector::swap().

3. Two versions of functions for evaluating derivatives:

polynomial<T> derivative(unsigned k = 1) const; // returns the k-order
derivative
void replace_by_derivative(unsigned k = 1); // replaces the polynomial by
the derivative

4. For integrals:

template <class U>
polynomial<U> integral(const U& c = 0) const; // returns the integral and c
is the coefficient for x^0
template <class U>
void replace_by_integral(const U& c = 0);

5. As far as I know a conversion for Chebyshev form has been already done. I
would like to add conversion and special functions for Hermitte, Laguerre
and Legendre forms. Obviously I wait also for other suggestions.

6. extern function for finding a polynomial based on N points.

template <std::size_t N, class T>
polynomial<T> create_polynomial(const T(&poly)[N]);

Other ideas like new operators and functions seem to be clear.

I wait for suggestions or questions and I'm going to send my application in
few days. :)

Pawel Kieliszczyk.