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.