Workshops

Application 8: Parallelization of the Mixed Cell Computation

65
reads

Tsung-Lin Lee

2013-03-29
11:35:00 - 12:00:00

101 , Mathematics Research Center Building (ori. New Math. Bldg.)



When the polyhedral homotopy method is used in locating all the isolated zeros of polynomial systems, the process of enumerating all the fine mixed cells in a fine mixed subdivision of the support plays a vitally important role. This process could consume a large part of the computation and therefore dominates the efficiency of the polyhedral homotopy method. Our algorithm in MixedVol-2.0 for enumerating mixed cells is highly serial. Recently we reformulated the original algorithm, making it much more fine-grained and scalable in parallel computation. Remarkably, very high speed-ups were achieved in our numerical results, and we are now able to compute the mixed cells for very large systems.