Algorithms and Complexity Seminar

On the Parallelization of Polynomial System Solvers

Yuzhen Xie (Waterloo University)

Symbolic polynomial solvers involve sophisticated algorithms and are extremely time consuming when applied to large problems. Even worse, intermediate expressions can grow to enormous size and may halt the computation even if the result is of moderate size. Our goal is to develop a high-performance solver capable of exploiting clusters of multicores to tackle large problems that are out of reach today.

This talk addresses the challenges in parallelizing an algorithm (called Triade) for solving non-linear systems of equations symbolically. In a preliminary work, we have analyzed the parallelism of the "Triade" algorithm. By applying "modular methods" and "solving by decreasing order of dimension", multi- level parallelism can be obtained: coarse grained (component) level for tasks computing geometric objects in the solution sets, and medium/fine grained level for polynomial operations within each task. Our current project is to develop libraries in Cilk++ for parallel polynomial GCD/resultant, multiplication and division, etc., and based on which to realize a parallel solver capable of exploiting clusters of multicores. I would like to discuss our different implementation strategies on shared and distributed memory systems.

I am looking forward to your comments and suggestions.