Parallelization of Faugere's improved F4 algorithm
Yashodhan Karandikar, Prakrati Agrawal, Habeeb Syed, Jojumon Kavalan · 2012
Solving systems of multi-variate polynomial equations is a well known problem in mathematics. Faugere proposed the F4 algorithm to solve systems of polynomial equations via Groebner basis computations. His later version of this algorithm (F5) improved performance and enabled solution to complex systems. However, memory and compute requirements of these algorithms are prohibitive and limit the size of the problems that can be solved. This dictates the need to have a multi-node MPI-based parallel implementation of F4. In this paper, we discuss some of the issues in parallelization of this algorithm. We discuss our MPI-pthread based hybrid approach to parallelization. Finally, we present some results and limitations of our approach to parallelization of F4.