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.

Advertisements

Stillman’s conjecture and Gröbner bases

Start with linear forms f_1,\dots,f_k in infinitely many variables \{x_i\mid i>0\}. Fix the monomial order to be the graded reverse lexicographic (with x_1>x_2>\cdots). Then the reduced Gröbner basis (GB) for the input sequence f is equivalent to the row-reduced echelon form (RREF) of the k \times \infty matrix of the coefficients of f.

Suppose one makes a generic linear change of variables prior to computing GB (RREF). Then the dimension r of the subspace spanned by f determines the leading monomials of the GB (pivots in the RREF): \{x_1,\dots,x_r\}. Note that there is a finite number of outcomes as r  is at most k.

In full analogy to the above, stepping into the nonlinear land, [DLL] establishes that there is a finite number of generic initial ideals (gins) for the ideal \langle f_1,\dots,f_k \rangle for the homogeneous generators of fixed arbitrary degrees d_1,\dots,d_k (the linear case is d_1=\dots=d_k=1). Moreover, this remains true beyond polynomials: f may come from a big ring of formal power series of bounded degree.

The finiteness of the set of gins implies yet another proof of Stillman’s conjecture:

The projective dimension of an ideal generated by homogeneous forms of fixed degrees but in an arbitrary number of variables and in arbitrary characteristic is uniformly bounded.

Notably, unlike in the linear case, the characteristic of the field of coefficients may make a difference for the outcome (i.e., the set of possible gins). However, the union of these over all characteristics is still finite!

The following articles (listed chronologically) contain proofs of Stillman’s conjecture.

[AH]  Ananyan, Hochster. “Small subalgebras of polynomial rings and Stillman’s conjecture.”

[ESS]  Erman, Snowden, Sam. “Big polynomial rings and Stillman’s conjecture.”

[DLL]  Draisma, Lasoń, Leykin. “Stillman’s conjecture via generic initial ideals.”

IMG_20180328_075335-EFFECTS
Spring at Institut Mittag-Leffler

In principle, it is possible to use the bounds on the projective dimension given in [AH] for an effective approach to find all gins. One can also implement the algorithm of [DLL] on a computer. While the latter may seem more efficient than the former, neither approach may lead to computational results that surpass those obtained in special cases by humans.

(Disclaimer: the last statement represents the author’s opinion of the capabilities of humans and machines at the moment of writing.)

 

Littlewood-Richardson Homotopy

This work took (from the original idea to an implemented algorithm) about 20 years to complete!

22b-eps-converted-to-1

Start by playing Ravi Vakil’s checkerboard games to understand the geometric Littlewood-Richardson rule. Track involved cascades of homotopies on checkerboard varieties corresponding to one of the 10 moves like the one depicted and find solutions (i.e, find approximate numerical solutions explicitly!) to any instance of any Schubert problem on any Grassmannian.

 

 

Georgia Algebraic Geometry Symposium 2018

The Georgia Algebraic Geometry Symposium (sometimes known as GAGS) will take place in Georgia Tech on Feb 23-25, 2018, starting with registration and the first talk at 4:30pm on Feb 23 (Friday) and ending before lunch on Feb 25 (Sunday).

We have a great list of invited speakers:

Please register here: http://people.math.gatech.edu/~jrabinoff6/gags2018/

(Yes, even the local students should register! This will help us plan better!)

peaches

Note that Georgia Tech will also host the Meeting on Applied Algebraic Geometry on April 7-8, 2018:  https://sites.google.com/view/maag-2018

 

 

MAAG 2018: Meeting on Applied Algebraic Geometry

We are happy to announce that MAAG 2018 is a go! Moreover, the main day (Saturday April 7) will be followed by an informal Numerical Algebraic Geometry day (Sunday April 8).

MAAG2018

Find tentative schedule and a link to the registration form (registration is free if completed by March 1) at https://sites.google.com/view/maag-2018

By the way, this meeting has a short but rich history.

 

Beyond polyhedral homotopies

We forgot to post this here in the beginning of the summer… The paper outlines a very general framework for (an) algorithm(s) waiting to be implemented.

trop-two-circles

Beyond polyhedral homotopies
(Anton Leykin and  Josephine Yu)

Abstract: We present a new algorithmic framework which utilizes tropical geometry and homotopy continuation for solving systems of polynomial equations where some of the polynomials are generic elements in linear subspaces of the polynomial ring. This approach generalizes the polyhedral homotopies by Huber and Sturmfels. 

 

The short story of MAGA

The Meeting on Algebraic Geometry and its Applications was intended as a one-day meeting that attracts people in the South-East of the US. The first two incarnations — at Georgia Tech in 2015 and at Clemson in 2016 — gathered 25-30 participants each.

MAGA had a year off in 2017 due to a large international meeting scheduled in the same year at GT, but the meeting will run in 2018. There is also a plan to continue this as a regular annual event held in April in Atlanta.

hat

However, the world has changed a bit in the last couple of years and a lot of people associate the acronym MAGA… with something completely different. Therefore a question: what could be a new name/abbreviation?