Improving multivariate Horner schemes with Monte Carlo tree search
arXiv:1207.7079 · doi:10.1016/j.cpc.2013.05.008
Abstract
Optimizing the cost of evaluating a polynomial is a classic problem in computer science. For polynomials in one variable, Horner's method provides a scheme for producing a computationally efficient form. For multivariate polynomials it is possible to generalize Horner's method, but this leaves freedom in the order of the variables. Traditionally, greedy schemes like most-occurring variable first are used. This simple textbook algorithm has given remarkably efficient results. Finding better algorithms has proved difficult. In trying to improve upon the greedy scheme we have implemented Monte Carlo tree search, a recent search method from the field of artificial intelligence. This results in better Horner schemes and reduces the cost of evaluating polynomials, sometimes by factors up to two.
5 pages
Cited by in corpus (8)
- Monte Carlo Tree Search: A Review of Recent Modifications and Applications
- Performance analysis of a 240 thread tournament level MCTS Go program on the Intel Xeon Phi
- HEPGAME and the Simplification of Expressions
- Structured Parallel Programming for Monte Carlo Tree Search
- Learning a performance metric of Buchberger's algorithm
- Pseudoscalar Higgs boson decay to three parton amplitudes at NNLO to higher orders in the dimensional regulator
- Ensemble UCT Needs High Exploitation
- Scaling Monte Carlo Tree Search on Intel Xeon Phi