[math] Efficient polynomial multiplication

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[math] Efficient polynomial multiplication

Boost - Dev mailing list
Hello all

This is my first post to the mailing list.

While looking at the source code for polynomial multiplication
(boost/math/tools/polynomial.hpp) I discovered that the library used
O(N^2) algorithm for multiplication. I would like to work on
implementing a more efficient algorithm (complexity: O(N log(N))).

I am writing this mail to get views and feedback from the community
and have a healthy discussion before starting the work.

Lakshay

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [math] Efficient polynomial multiplication

Boost - Dev mailing list
Hello.

At first please give us bencmark results, where NlogN is faster and
where is slower.


After that please write email to Boost.Math maintainer or create issue
on Github Boost.Math repo.


13.07.2017 08:00, Lakshay Garg via Boost пишет:

> Hello all
>
> This is my first post to the mailing list.
>
> While looking at the source code for polynomial multiplication
> (boost/math/tools/polynomial.hpp) I discovered that the library used
> O(N^2) algorithm for multiplication. I would like to work on
> implementing a more efficient algorithm (complexity: O(N log(N))).
>
> I am writing this mail to get views and feedback from the community
> and have a healthy discussion before starting the work.
>
> Lakshay
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [math] Efficient polynomial multiplication

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list


On 13/07/2017 06:00, Lakshay Garg via Boost wrote:

> Hello all
>
> This is my first post to the mailing list.
>
> While looking at the source code for polynomial multiplication
> (boost/math/tools/polynomial.hpp) I discovered that the library used
> O(N^2) algorithm for multiplication. I would like to work on
> implementing a more efficient algorithm (complexity: O(N log(N))).
>
> I am writing this mail to get views and feedback from the community
> and have a healthy discussion before starting the work.

There has been some work towards this here:
https://github.com/boostorg/math/pull/32, but it's a long way from ready
to go.

The Karatsuba algorithm is probably/possibly of more interest than FFT
based ones too: as FFT's only really kick in when the digit count is
exceptionally large.

So I would say if you're looking for something to do, then a PR for the
Karatsuba algorithm would be the best choice: most of the work would be
in up-rating the tests and doing performance testing to see what order
of polynomial needs the more complex algorithm.

Best, John Maddock.

---
This email has been checked for viruses by AVG.
http://www.avg.com


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [math] Efficient polynomial multiplication

Boost - Dev mailing list
>
> ​[...] then a PR for the Karatsuba algorithm would be the best choice:
> most of the work would be in up-rating the tests and doing performance
> testing to see what order of polynomial needs the more complex algorithm.
>

I have been doing some experiments with the Karatsuba multiplication
algorithm. Karatsuba multiplication is outperforming the regular
multiplication method for high degree polynomials (> 500). I believe it can
still be improved since I haven't spent much time trying to optimize it.
But before that I would like to share some bench-marking result and have a
discussion.

Here are some benchmark results (using google-benchmark):

| Polynomial |                     TIME                                   |
| Size       | Boost Polynomial | Naive array impl | Karatsuba array impl |
|------------+------------------+------------------+----------------------|
|      1     |         167 ns   |        47 ns     |        60 ns         |
|      2     |         163 ns   |        59 ns     |        93 ns         |
|      4     |         200 ns   |        87 ns     |       208 ns         |
|      8     |         231 ns   |       134 ns     |       264 ns         |
|     16     |         324 ns   |       243 ns     |       495 ns         |
|     32     |         601 ns   |       534 ns     |      1005 ns         |
|     64     |        1479 ns   |      1873 ns     |      2626 ns         |
|    128     |        5192 ns   |      5280 ns     |      7031 ns         |
|    256     |       18512 ns   |     18215 ns     |     18221 ns         |
|    512     |       79322 ns   |     66010 ns     |     54160 ns         |
|   1024     |      267440 ns   |    247470 ns     |    152651 ns         |
|   2048     |     1158600 ns   |    968172 ns     |    433985 ns         |
|------------|------------------|------------------|----------------------|
| Complexity |     0.34 N^2     |    0.23 N^2      |    2.47 N^1.585      |
| BigO RMS   |      15 %        |       2 %        |        5 %           |

Boost Polynomial -> Polynomial class in the boost.math library
Naive array impl -> O(N^2) polynomial multiplication on plain C arrays
Karatsuba array  -> Karatsuba polynomial multiplication using plain C arrays

Looking at the data, I'm wondering why is boost's implementation so slow
for polynomials of lower degree? I could not see any obvious reason by
looking at the source.

--
​Lakshay​

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [math] Efficient polynomial multiplication

Boost - Dev mailing list

> Looking at the data, I'm wondering why is boost's implementation so slow
> for polynomials of lower degree? I could not see any obvious reason by
> looking at the source.

I would guess memory allocation: if you're multiplying into already
allocated arrays and don't have to dynamically allocate memory for the
result of the multiplication, then that should be a lot quicker.  I
can't remember if the polynomial class operators are move-optimised
either (they should be).

John.

---
This email has been checked for viruses by AVG.
http://www.avg.com


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [math] Efficient polynomial multiplication

Boost - Dev mailing list
>
> I would guess memory allocation: if you're multiplying into already
> allocated arrays and don't have to dynamically allocate memory for the
> result of the multiplication, then that should be a lot quicker.
>

​No, I do not pre-allocate arrays. Here is the code for O(N^2) algorithm
I'm using:

double * g(double * p, double * q, size_t len) {
    double * out = new double[2*len];
    clear(out, 2*len); // calls memset
    for (int i=0; i<len; ++i)
        for (int j=0; j<len; ++j)
            out[i+j] += p[i] * q[j];
    return out;
}​


I can't remember if the polynomial class operators are move-optimised
> either (they should be).
>

​I don't think they are move optimized. All the function take lvalue
references​. Neither does this have a move constructor. I guess this class
needs a lot of work.

--
Lakshay

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [math] Efficient polynomial multiplication

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
BTW: A polynomial class working with std::array / boost::array would be
great! No allocation at all...

polynomial<float,3> f {1,2,3}, g {4,5,6};
polynomial<float,5> h = f * g;
auto i = h * g;
etc...

Mike...


Am 17.07.2017 um 20:53 schrieb John Maddock via Boost:

>
>> Looking at the data, I'm wondering why is boost's implementation so slow
>> for polynomials of lower degree? I could not see any obvious reason by
>> looking at the source.
>
> I would guess memory allocation: if you're multiplying into already
> allocated arrays and don't have to dynamically allocate memory for the
> result of the multiplication, then that should be a lot quicker.  I
> can't remember if the polynomial class operators are move-optimised
> either (they should be).
>
> John.
>
> ---
> This email has been checked for viruses by AVG.
> http://www.avg.com
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [math] Efficient polynomial multiplication

Boost - Dev mailing list
> BTW: A polynomial class working with std::array / boost::array would be
> great! No allocation at all...
>

Maybe I did not understand this properly but I disagree that using
std::array/boost::array will significantly reduce memory allocations. In my
opinion, it is the implementation which determines the number of memory
allocations. You can have the same number of allocations with vector.

Also, you would need to know the sizes of vectors at the compile time if
arrays are to be used. Wouldn't this be too restrictive?

--
Lakshay

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [math] Efficient polynomial multiplication

Boost - Dev mailing list
Hi Lakshay,

>> BTW: A polynomial class working with std::array / boost::array would be
>> great! No allocation at all...
>>
> ​[…]
> Also, you would need to know the sizes of vectors at the compile time if
> arrays are to be used. Wouldn't this be too restrictive?

in my experience (scientist), low order polynomials are much more frequently used than polynomials of order >500. So it might be worthwhile to improve the low order performance, too.

Concerning the std::array/boost::array, ideally you want to provide a library that can handle both dynamic and static arrays. Let's say I am user of your library, and I happen to know the order of my polynomial at compile time. Then I would like to rest assured that the library can handle and optimise this case.

The Eigen library and my proposed library https://github.com/HDembinski/histogram <https://github.com/HDembinski/histogram> and follow this approach, they transparently work with both static and dynamic arrays/histograms.

Best regards,
Hans

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Loading...