Mixed cell computation in HOM4ps (Q507160)

In numerical algebraic geometry, polynomial systems are solved by tracking solutions along a homotopy from an easy to solve start system to a desired system. To limit the number of paths to be tracked, \textit{B. Huber} and \textit{B. Sturmfels} [Math. Comput. 64, No. 212, 1541--1555 (1995; Zbl 0849.65030)] have defined polyhedral homotopies that exploit the sparsity of many systems in science and engineering. A main bottleneck in their method is the enumeration of so called mixed cells of a certain Minkowski sum. The present paper discusses many improvements to the enumeration of mixed cells. The most significant advance is probably the reformulation of the problem as graph traversal which can be parallelized efficiently. This yields great improvements in this bottleneck step of polyhedral homotopies. The paper also discusses various technical details of an implementation such as memory management. These improvements have been implemented by the autors in their software Hom4PS version 3.