search

jonathf / numpoly

Numpy compatible polynomial representation
https://numpoly.readthedocs.io
BSD 2-Clause "Simplified" License
12 stars 5 forks source link

``prod`` implementation #47

Open jonathf opened 4 years ago

jonathf commented 4 years ago

Current implementation uses multiply repeatedly along axis. This can likely be done much more efficiently with dedicated code.

Somewhat the same problem as issue #46, but a lot more book keeping.

tt-aiken commented 1 year ago

Any ideas on the best way to go about resolving this? I'm happy to try out some approaches! As it's written, the _prod function makes executing chaospy.generate_expansion() prohibitively time-consuming above about 3,000 polynomials with a time complexity of about n_polynomials^3.

jonathf commented 1 year ago

The lowest hanging fruit for this is to update nu.mul to do convolution which reduces O(N^2) to O(N log N).

3 brown 1 blue has an excellent intro video on the topic and how FFT can be used to in polynomial multiplication: https://www.youtube.com/watch?v=KuXjwB4LzSA If you can get that to work, it will be a impressive win.

The much higher hanging fruit is to get rid of the for-loop/recursive style code and instead try to formulate the problem in such a way that it exploits numpys fast array operations. I have vague idea of how that is done, but not sure if it is possible or not.