Finding Matrix Multiplication Algorithms with Classical Planning
Keywords:Applications and case studies of plannin and scheduling techniques, Classical planning techniques and analysis
AbstractMatrix multiplication is a fundamental operation of linear algebra, with applications ranging from quantum physics to artificial intelligence. Given its importance, enormous resources have been invested in the search for faster matrix multiplication algorithms. Recently, this search has been cast as a single-player game. By learning how to play this game efficiently, the newly-introduced AlphaTensor reinforcement learning agent is able to discover many new faster algorithms. In this paper, we show that finding matrix multiplication algorithms can also be cast as a classical planning problem. Based on this observation, we introduce a challenging benchmark suite for classical planning and evaluate state-of-the-art planning techniques on it. We analyze the strengths and limitations of different planning approaches in this domain and show that we can use classical planning to find lower bounds and concrete algorithms for matrix multiplication.
How to Cite
Speck, D., Höft, P., Gnad, D., & Seipp, J. (2023). Finding Matrix Multiplication Algorithms with Classical Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1), 411-416. https://doi.org/10.1609/icaps.v33i1.27220