Parallelization of triangular decompositions: techniques and implementation (Q2674015)

One of the well-known tools for solving polynomial systems is triangular decomposition which provides a finite set of regular chains. This kind of decomposition proceeds in an incremental manner by solving the equations one after the other and this may yield a splitting of the quasi-component of a regular chain. Thus, here the construction looks like a tree and one can complete each branch independently. The natural question that may arise is how we can use parallelization techniques for this computation. This question has been addressed in [\textit{M. Moreno Maza} and \textit{Y. Xie} [``Component-level parallelization of triangular decompositions'', in: Proceedings of the 2007 international workshop on Parallel symbolic computation, PASCO 2007. New York, NY: Association for Computing Machinery (ACM). 69--77 (2007; \url{doi:10.1145/1278177.1278189})]. In this paper the authors consider four different and related schemes in low and high levels to exploit parallelism in triangular decomposition algorithms. It is worth noting that a splitting is dependent on the geometry of the input polynomial system, and this may cause a problem for the parallelization (this point has been taken into account in the paper). The implementation (written in C/C++ in as a part of the BPAS library) of these algorithms and experimentation on thousands of polynomial systems show examples with even more than 10 times of speed-up.