Solving multivariate systems of polynomial equations is an important problem both as a subroutine in many problems and in its own right. Currently, the most efficient solvers are the Grobner-basis solvers, which include the XL algorithmi¾ź[6], as well as F$$_4$$i¾ź[9] and F$$_5$$i¾ź[10] algorithms. The F$$_4$$ is an advanced algorithm for computing Grobner bases. However, the algorithm has exponential space complexity and does not provide much flexibility in terms of controlling memory usage. This poses a serious challenge when we want to use it to solve instances of sizes of practical interest.#R##N##R##N#In this paper, we address the issue of memory usage by proposing a variant of F$$_4$$ algorithm called YAGS Yet Another Grobner-basis Solver. YAGS uses less memory than the original algorithm and runs at comparable speed with F$$_4$$. Furthermore, YAGS runs even faster than F$$_4$$ when solving dense polynomial systems. In other words, the proposed algorithm can reach better time-memory compromise via deliberately designed techniques to control its memory usage and efficiency. We have implemented a prototype of YAGS and conducted an extensive set of experiments with it. The experiment results demonstrate that the proposed modification does achieve lower time-memory products than the original F$$_4$$ over a broad set of parameters and problem sizes.
['Yun-Ju Huang', 'Wei-Chih Hong', 'Chen-Mou Cheng', 'Jiun-Ming Chen', 'Bo-Yin Yang']
A Memory Efficient Variant of an Implementation of the F$$_4$$ Algorithm for Computing Gröbner Bases