Why Local Search Excels in Expression Simplification
This work addresses a bottleneck in High Energy Physics by enabling faster numerical integration, reducing computation time from weeks to hours, though it is incremental as it builds on prior methods like MCTS.
The paper tackles the problem of simplifying large expressions for numerical integration in High Energy Physics by showing that Stochastic Local Search (SLS) is effective in finding Horner schemes, achieving results similar or better than MCTS while being at least 10 times faster and speeding up integrations by a factor of 24.
Simplifying expressions is important to make numerical integration of large expressions from High Energy Physics tractable. To this end, Horner's method can be used. Finding suitable Horner schemes is assumed to be hard, due to the lack of local heuristics. Recently, MCTS was reported to be able to find near optimal schemes. However, several parameters had to be fine-tuned manually. In this work, we investigate the state space properties of Horner schemes and find that the domain is relatively flat and contains only a few local minima. As a result, the Horner space is appropriate to be explored by Stochastic Local Search (SLS), which has only two parameters: the number of iterations (computation time) and the neighborhood structure. We found a suitable neighborhood structure, leaving only the allowed computation time as a parameter. We performed a range of experiments. The results obtained by SLS are similar or better than those obtained by MCTS. Furthermore, we show that SLS obtains the good results at least 10 times faster. Using SLS, we can speed up numerical integration of many real-world large expressions by at least a factor of 24. For High Energy Physics this means that numerical integrations that took weeks can now be done in hours.