search

jannikmi / multivar_horner

python package implementing a multivariate Horner scheme for efficiently evaluating multivariate polynomials
https://multivar-horner.readthedocs.io/en/latest/
MIT License
27 stars 3 forks source link

Improve Optimal Factorisation Heuristic #5

Open jannikmi opened 5 years ago

jannikmi commented 5 years ago

Optimal Horner Factorisation A* search: The current heuristic to estimate the minimal number of required operations (lower bound) is to optimistic. This often causes every possible factorisation to be evaluated. For larger polynomials this makes this algorithm infeasible. -> Make the heuristic more accurate.

Attention: Tradeoff between accuracy of heuristic (how many factorisations are being skipped) and the time required to compute the heuristic for every node (is it cheaper to just try a factorisation?)

jannikmi commented 5 years ago

cf. heuristics proposed in

[2] M. Kojima, “Efficient evaluation of polynomials and their partial derivatives in homotopy continuation methods”, Journal of the Operations Research Society of Japan, vol. 51, no. 1, pp. 29–54, 2008.