Skip to main content
MathOverflow

Return to Answer

corrected statement about finding optimal factorisations due to recent findings
Source Link
jannikmi
jannikmi
  • 71
  • 1
  • 2

I implemented this in Python: multivar_horner

You can look at the approach used there and port it to Fortran.

NOTE: ToIn contrast to the best of my knowledgeone dimensional case there is no known algorithm for finding the optimal horner factorisationare multiple possible Horner factorisations of a multivariate polynomialpolynomials. The best oneOne can do isallow a search over the possible factorisations to find a minimal representation as described HERE. In most cases however it suffices to use a clever heuristic to find a single "good" factorisationsfactorisation. I implemented amultivar_horner implements the greedy heuristic similar to the one described in the paper "Greedy Algorithms for Optimizing Multivariate Horner Schemes".

The authors of some related publications (including the above mentioned) claim to have an implementation of their proposed algorithms, but I was not able to find any publicly available ones.

I implemented this in Python: multivar_horner

You can look at the approach used there and port it to Fortran.

NOTE: To the best of my knowledge there is no known algorithm for finding the optimal horner factorisation of a multivariate polynomial. The best one can do is to use a clever heuristic to find "good" factorisations. I implemented a greedy heuristic similar to the one described in the paper "Greedy Algorithms for Optimizing Multivariate Horner Schemes".

The authors of some related publications (including the above mentioned) claim to have an implementation of their proposed algorithms, but I was not able to find any publicly available ones.

I implemented this in Python: multivar_horner

You can look at the approach used there and port it to Fortran.

NOTE: In contrast to the one dimensional case there are multiple possible Horner factorisations of multivariate polynomials. One can allow a search over the possible factorisations to find a minimal representation as described HERE. In most cases however it suffices to use a heuristic to find a single "good" factorisation. multivar_horner implements the greedy heuristic described in "Greedy Algorithms for Optimizing Multivariate Horner Schemes".

The authors of some related publications (including the above mentioned) claim to have an implementation of their proposed algorithms, but I was not able to find any publicly available ones.

Source Link
jannikmi
jannikmi
  • 71
  • 1
  • 2

I implemented this in Python: multivar_horner

You can look at the approach used there and port it to Fortran.

NOTE: To the best of my knowledge there is no known algorithm for finding the optimal horner factorisation of a multivariate polynomial. The best one can do is to use a clever heuristic to find "good" factorisations. I implemented a greedy heuristic similar to the one described in the paper "Greedy Algorithms for Optimizing Multivariate Horner Schemes".

The authors of some related publications (including the above mentioned) claim to have an implementation of their proposed algorithms, but I was not able to find any publicly available ones.