Why are there so few zero-dimensional polynomial system solvers and is this because there is no real market for them?

Question

My questions involve the quotes below from wikipedia regarding solving polynomial systems, which given the size of the market for Big Data & Predictive Analysis applications I find puzzling:

"This exponential behavior makes solving polynomial systems difficult and explains why there are few solvers that are able to automatically solve systems with Bézout's bound higher than, say 25"

"There are at least three software packages which can solve zero-dimensional systems automatically"

http://en.wikipedia.org/wiki/System_of_polynomial_equations:

Questions:

1) Why are there so few automatic zero-dimensional solvers?

2) Are they just too hard to build?

3) Or is there no market for such a sophisticated solution?

4) Or is the market "cornered": i.e. are the handful of packages in 1) doing the job well enough that there's no need or demand for anything better?

5) Also, would there be a demand for solvers that could push past a Bézout's bound of 25?

Answer 1

Not 100% in-field but I'll try an answer.

1) Why are there so few automatic zero-dimensional solvers?

As the Wikipedia page says, the problem is intrinsically difficult and slow to solve. Ill-conditioning of the roots and of the qualitative results (dimension, number and multiplicity of zeros...) is also often an issue. As a result, people do not use often high-degree polynomial systems in modelling; linear methods can be made to work better in practice. This reduces a lot the demand.

2) Are they just too hard to build?

They are hard, but that is not the main issue. Lots of problems such as solving PDEs or simulating protein folding are hard, too, but they seem to have much more "market".

3) Or is there no market for such a sophisticated solution?

There is some market, for instance applications in algebraic geometry, but as far as I know they are mostly within mathematics.

4) Or is the market "cornered": i.e. are the handful of packages in 1) doing the job well enough that there's no need or demand for anything better?

I am not extremely familiar with all these packages, but for what I have used them they seem to work reasonably well. The main issue is the intrinsic difficulty of the problem: exponential problem is exponential. It's difficult to do a good job when there are $2^{20}$ solutions, and they are ill-conditioned.

5) Also, would there be a demand for solvers that could push past a Bézout's bound of 25?

Do you mean "would they publish well" or "would I be able to sell them to industries"? I think they would publish well if they work; for industry, I think not immediately.

Answer 2

Also not my field, but...

1) Define "few"? There are many available, already for homotopy methods. See http://www.issac-conference.org/2010/assets/SoftwareDemos/VerscheldeFinal.pdf

"RELATED SOFTWARE: Homotopy continuation methods for polynomial systems are implemented in various computer programs, listed in alphabetic order: Bertini [1, 2], CONSOL [14], HOM4PS-2.0 [9], HomLab [18, Appendix C], NAG4M2 [10], PHoM [8], POLSYS PLP [26], and POLSYS GLP [20]. Both POL-SYS PLP and POLSYS GLP are part of the development of HOMPACK [24, 25]. Polyhedral homotopies need mixed volumes, computed by DEMiCs [13], Mixvol [4], and MixedVol [5]."

As Wikipedia noted, Maple has (at least) two solving methods. Mathematica also has some.

2) They are perhaps not easy to build (problems with numerical errors, tracing homotopy paths), but this is not the critical factor.

3) One of the main "markets" is robotics. You can note that some of the notable authors in the field (Wampler most obviously) have jobs either directly in or related to (such as part-time consultant) the car industry.

See also (Wampler and Sommese) http://dx.doi.org/10.1017/S0962492911000067

"While systems of polynomial equations arise in fields as diverse as mathematical finance, astrophysics, quantum mechanics, and biology, perhaps no other application field is as intensively focused on such equations as rigid-body kinematics. This article reviews recent progress in numerical algebraic geometry, a set of methods for finding the solutions of systems of polynomial equations that relies primarily on homotopy methods, also known as polynomial continuation. Topics from kinematics are used to illustrate the applicability of the methods. High among these topics are questions concerning robot motion."

The slides of Verschelde's 2003 talk also have some applications listed. http://homepages.math.uic.edu/~jan/Talks/cimpa_first.pdf

4) The market is not cornered, in particular methods that exploit sparsity are of high interest. For instance, in the Math Reviews of Li's 2003 survey, it is noted that half the 100 pages are involved with sparsity. http://www.ams.org/mathscinet-getitem?mr=2009773

"More than half of this almost 100 page survey is devoted to the exploitation of sparsity, as most applications give rise to polynomials which have fewer monomials with nonzero coefficients than general polynomials of the same degree. Quite often, sparse systems then also have far fewer roots compared to systems of general polynomials of the same degree. Any homotopy continuation method which is based only on degree bounds will likely have to trace far too many diverging paths to find all solutions of a sparse polynomial system."

See also Section 10 of the above Wampler and Sommese paper, for the types of improvements that are being made (or would like to be seen).

5) Yes, though Wikipedia's information here ("25") is not exactly reliable. For instance, see section 8 of the aforementioned Wampler and Sommese paper (http://dx.doi.org/10.1017/S0962492911000067):

"To put some of this in perspective, consider a sequence of polynomial systems arising from discretizing the Lotka–Volterra population model that is presented in Hauenstein et al. (2011). HOM4PS-2.0 and PHCpack both implement the polyhedral homotopy method for solving sparse polynomial systems, while Bertini implements regeneration (discussed in Section 10.2) for solving such systems (Hauenstein et al. 2011). For these systems, the number of solutions over C is the number of paths tracked by the polyhedral homotopy method. Even so, the polyhedral homotopy becomes impractical as the number of variables increases due to the computational complexity of computing a start system via the mixed volume. For example, consider solving the n = 24, 32, and 40 variable instances of the Lotka–Volterra model using a single core running 64-bit Linux. Here the number of non-singular isolated solutions equals $\sqrt{2^n}$ (which equals the mixed volume). For the 24 variable system, PHCpack took over 18 days while HOM4PS-2.0 and Bertini both took around 10 minutes. For the 32 variable system, PHCpack failed to solve the system in 45 days, HOM4PS-2.0 took over 3 days and Bertini took roughly 5 hours. For the 40 variable system, PHCpack and HOM4PS-2.0 both failed to solve the system in 45 days, but Bertini solved the system in under a week. Since regeneration is parallelizable, we also solved the 32 and 40 variable systems using 64 cores (8 nodes each having dual 2.33 GH Xeon 5410 quad-core processors). In parallel, Bertini took less than 8 minutes and 4 hours to solve the 32 and 40 variable polynomial systems, respectively."

In this example, Bertini thus found $\sqrt{2^{40}}$ isolated solutions, somewhat larger than the Wikipedia bound of 25. Of course the system should be "special" (likely meaning sparse in some sense) to deal with a large Bezout (or mixed volume) number, but many interesting systems do have particular properties. (The same is true for Gr\"obner basis methods, that the generic behavior might not be very relevant to any specific given instance.) I don't know if by "automatic" you want to be able to solve generic systems of a given Bezout number efficiently, probably that is a different question.