Of monodromy, parallelization, and numerical hell

In a previous blog post, we described a software package that exploits the monodromy action for solving polynomial systems in a parametric family. We’re happy to report that the original paper accompanying this package is now published in the IMA Journal of Numerical Analysis. In this paper, we laid out the basic framework for monodromy solvers and highlight potential strengths of this approach, both by analyzing its complexity (conditional on strong randomness assumptions!) and testing our package against other solvers.

In this post, we will describe the sequel to this paper, presented at ISSAC 2018.

Many of the celebrated approaches to numerically solving polynomial systems employ a methodology in which a start system and a target system are both fixed. Numerical solutions to the target system are realized by numerical continuation along a fixed number of solution paths. This paradigm is ripe for speeeding up via parallel computing.

d95617f56808f8846b319ccdd130b61d

In the cartoon above, H(t) denotes a homotopy connecting the solutions between two fictitious polynomial systems. For two solution paths to be tracked, zero communication is needed from the two path trackers. Thus, four parallel processors result in a perfect speedup. This phenomenon is known as embarrassing parallelism.

With monodromy solvers, one structural property of systems we wish to exploit is lack of sharpness in the number of paths needed to find all solutions. For instance, the homotopy M(t) in the image above has two diverging solution paths. In some sense, an optimal homotopy for the system M(1) would track only two paths. The goal of our monodromy approach is essentially to produce an optimal start system for a given family of systems. However, such a start system may not be easily accessible by deterministic calculation. Our approach is fundamentally randomized—for a family with generically d solutions, we allow for

O \big(|G| \cdot d \big)

path-tracking steps, where |G| measures the size of an underlying data structure we call the homotopy graph. Our desired output is a generic system with d solutions. In our parlance, we may visualize the homotopy graph connecting some systems in the parameter space and a solution graph of size |G| \cdot d lying above it.

out

In reality, our goal is to track as few paths along the homotopy graph as possible. With this goal in mind, we may observe that devising a scheduling algorithm for a parallel incarnation of monodromy is not a trivial task. One of our main contributions is a description of such an algorithm and numerous simulations indicating its potential to provide substantial speedups. If you’re curious, check out the paper or the accompanying github repository.

Another factor complicating the aforementioned scheduling algorithm: in reality, path-tracking can fail. In theory, paths in the parameter space which are suitably randomized will avoid the locus of ill-conditioned systems with probability 1. In reality, the core numerics may be unable (or simply unwilling) to distinguish nearly-singular systems from those that truly are. We may imagine, in the worlds inhabited by our graphs, several scattered regions of numerical hell, as depicted below.

segment-homotopy-2points-inflamed-1

In the ISSAC paper, we consider a simplified model of path-tracking failures, and describe its implications for the scheduling algorithm as well as robustness of our approach to a few failures—namely, if our graph is a clique as in two images above, we may tolerate a certain number of failures and still expect to produce the correct number of solutions, under suitable randomness assumptions.

One final word on randomness assumptions—despite being demonstrably false, they turn out to be useful in practice. For a different, but related, perspective, check out this nice lecture on sampling in numerical algebraic geometry.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s