Hi everyone. My name is Pawel Kieliszczyk. I'm a student of Wroclaw University of Technology in Poland. 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_too... and usefull functions here: http://svn.boost.org/svn/boost/trunk/libs/math/doc/sf_and_dist/html/math_too... 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. What do you think about this? Please ask also if you have any questions. Pawel Kieliszczyk
Hi, I'm interested. I think we should have a basic transform object who can implement any kinds of transformation, such as Fourier Transform, Laplace Transform, Wavelet ..... It's useful, especially for info system. On Sat, Mar 22, 2008 at 2:14 AM, Zero Mind <lord.zerom1nd@gmail.com> wrote:
Hi everyone.
My name is Pawel Kieliszczyk. I'm a student of Wroclaw University of Technology in Poland. 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_too... and usefull functions here:
http://svn.boost.org/svn/boost/trunk/libs/math/doc/sf_and_dist/html/math_too...
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.
What do you think about this? Please ask also if you have any questions.
Pawel Kieliszczyk _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- ------------------------------- Enjoy life! Barco You
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Zero Mind Sent: 21 March 2008 18:15 To: boost@lists.boost.org Subject: [boost] [gsoc2008] Polynomial Library.
Hi everyone.
My name is Pawel Kieliszczyk. I'm a student of Wroclaw University of Technology in Poland. 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.
What do you think about this?
Sounds useful. If a niche need. But there are more people who need this than know they do ;-) Paul --- Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS pbristow@hetp.u-net.com
Hi Pawel El Viernes 21 Marzo 2008 19:14:52 Zero Mind escribió:
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.
What do you think about this? Please ask also if you have any questions.
Although I'm another student "competing" for a GSoC application, I find this library extremely useful. I've had to implement polynomial interpolation for doing crypto stuff (Shamir's Secret Sharing Scheme) and would have loved to have a library that already solved this problem. Cheers.
Barco You wrote:
I'm interested. I think we should have a basic transform object who can implement any kinds of transformation, such as Fourier Transform, Laplace Transform, Wavelet .....
It's useful, especially for info system.
Paul A Bristow wrote:
Sounds useful.
If a niche need.
But there are more people who need this than know they do ;-)
Although I'm another student "competing" for a GSoC application, I find
Esteve Fernandez wrote: this
library extremely useful. I've had to implement polynomial interpolation for doing crypto stuff (Shamir's Secret Sharing Scheme) and would have loved to have a library that already solved this problem.
Nice to see that some people are interested. To be honest I had to use small polynomials and implemented basic operations few months ago. However, that was a very simple program. I would like to create something more advanced this summer and in my opinion such a library may be useful sometimes. Thanks for answers. Pawel Kieliszczyk
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_too...
and usefull functions here:
http://svn.boost.org/svn/boost/trunk/libs/math/doc/sf_and_dist/html/math_too...
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.
Pawel,
I wait for suggestions or questions and I'm going to send my application in few days. :)
How about a numerically faithful evaluation function, eg, Langlois et al. Faithful Polynomial Evaluation with Compensated Horner Algorithm. Arxiv preprint cs.NA (2006) http://arxiv.org/abs/cs/0610122v1 Regards, Hugo
Hugo Duncan wrote:
How about a numerically faithful evaluation function, eg,
Langlois et al. Faithful Polynomial Evaluation with Compensated Horner Algorithm. Arxiv preprint cs.NA (2006) http://arxiv.org/abs/cs/0610122v1
Hi Hugo. You're right. I've been wondering about more faithful methods, too. The simple Horner scheme is fast (optimal without preconditioning) and efficient. However, faster algorithms are available and useful if a polynomial is to be evaluated many times. Such a function is a must in my opinion and I would like to add it to the library. On the other hand a programmer may use the library for precise calculations and here these algorithms from your link would be really helpful. I think both fast and faithful functions may be added. A programmer would choose between both. Thank you very much for this article! I haven't read it before. chose
Regards, Hugo
Regards, Pawel
participants (5)
-
Barco You -
Esteve Fernandez -
Hugo Duncan -
Paul A Bristow -
Zero Mind