Numerical Schubert calculus via the Littlewood-Richardson homotopy algorithm

Authors:
Anton Leykin, Abraham Martín del Campo, Frank Sottile, Ravi Vakil and Jan Verschelde

Journal:
Math. Comp. **90** (2021), 1407-1433

MSC (2020):
Primary 14N15, 65H10

DOI:
https://doi.org/10.1090/mcom/3579

Published electronically:
February 4, 2021

MathSciNet review:
4232229

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We develop the Littlewood-Richardson homotopy algorithm, which uses numerical continuation to compute solutions to Schubert problems on Grassmannians and is based on the geometric Littlewood-Richardson rule. One key ingredient of this algorithm is our new optimal formulation of Schubert problems in local Stiefel coordinates as systems of equations. Our implementation can solve problem instances with tens of thousands of solutions.

- Guy Bresler, Dustin Cartwright, and David Tse,
*Feasibility of interference alignment for the MIMO interference channel*, IEEE Trans. Inform. Theory**60**(2014), no. 9, 5573–5586. MR**3252407**, DOI 10.1109/TIT.2014.2338857 - C.I. Byrnes,
*Pole assignment by output feedback*, Three decades of mathematical systems theory, 1989, pp. 31–78. - A. Eremenko and A. Gabrielov,
*Pole placement static output feedback for generic linear systems*, SIAM J. Control Optim.**41**(2002), no. 1, 303–312. MR**1920166**, DOI 10.1137/S0363012901391913 - William Fulton,
*Young tableaux*, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, Cambridge, 1997. With applications to representation theory and geometry. MR**1464693** - Luis D. García-Puente, Nickolas Hein, Christopher Hillar, Abraham Martín del Campo, James Ruffo, Frank Sottile, and Zach Teitler,
*The secant conjecture in the real Schubert calculus*, Exp. Math.**21**(2012), no. 3, 252–265. MR**2988578**, DOI 10.1080/10586458.2012.661323 - D.R. Grayson and M.E. Stillman,
*Macaulay2, a software system for research in algebraic geometry*. - Jonathan D. Hauenstein, Nickolas Hein, and Frank Sottile,
*A primal-dual formulation for certifiable computations in Schubert calculus*, Found. Comput. Math.**16**(2016), no. 4, 941–963. MR**3529130**, DOI 10.1007/s10208-015-9270-z - Jon D. Hauenstein, Mohab Safey El Din, Éric Schost, and Thi Xuan Vu,
*Solving determinantal systems using homotopy techniques*, J. Symbolic Comput.**104**(2021), 754–804. MR**4180147**, DOI 10.1016/j.jsc.2020.09.008 - Nickolas Hein, Christopher J. Hillar, and Frank Sottile,
*Lower bounds in real Schubert calculus*, São Paulo J. Math. Sci.**7**(2013), no. 1, 33–58. MR**3234560**, DOI 10.11606/issn.2316-9028.v7i1p33-58 - Nickolas Hein and Frank Sottile,
*A lifted square formulation for certifiable Schubert calculus*. part 3, J. Symbolic Comput.**79**(2017), no. part 3, 594–608. MR**3563100**, DOI 10.1016/j.jsc.2016.07.021 - Birkett Huber, Frank Sottile, and Bernd Sturmfels,
*Numerical Schubert calculus*, J. Symbolic Comput.**26**(1998), no. 6, 767–788. Symbolic numeric algebra for polynomials. MR**1662035**, DOI 10.1006/jsco.1998.0239 - Birkett Huber and Jan Verschelde,
*Pieri homotopies for problems in enumerative geometry applied to pole placement in linear systems control*, SIAM J. Control Optim.**38**(2000), no. 4, 1265–1287. MR**1760069**, DOI 10.1137/S036301299935657X - S.W. Kim, C.J. Boo, S. Kim, and H.-C. Kim,
*Stable controller design of MIMO systems in real Grassmann space*, International J. of Control, Automation and Systems**10**(2012), no. 2, 213–226., DOI 10.1007/s12555-012-0202-2 - Steven L. Kleiman,
*The transversality of a general translate*, Compositio Math.**28**(1974), 287–297. MR**360616** - S. L. Kleiman and Dan Laksov,
*Schubert calculus*, Amer. Math. Monthly**79**(1972), 1061–1082. MR**323796**, DOI 10.2307/2317421 - Anton Leykin,
*Numerical algebraic geometry*, J. Softw. Algebra Geom.**3**(2011), 5–10. MR**2881262**, DOI 10.2140/jsag.2011.3.5 - A. Leykin, A. Martín del Campo, F. Sottile, R. Vakil, and J. Verschelde,
*Software for Numerical Schubert Calculus*, 2021. - Anton Leykin and Frank Sottile,
*Galois groups of Schubert problems via homotopy computation*, Math. Comp.**78**(2009), no. 267, 1749–1765. MR**2501073**, DOI 10.1090/S0025-5718-09-02239-X - T. Y. Li, Tim Sauer, and J. A. Yorke,
*The cheater’s homotopy: an efficient procedure for solving systems of polynomial equations*, SIAM J. Numer. Anal.**26**(1989), no. 5, 1241–1251. MR**1014884**, DOI 10.1137/0726069 - T. Y. Li, Xiaoshen Wang, and Mengnien Wu,
*Numerical Schubert calculus by the Pieri homotopy algorithm*, SIAM J. Numer. Anal.**40**(2002), no. 2, 578–600. MR**1921670**, DOI 10.1137/S003614290139175X - A. Martín del Campo, F. Sottile, and R. Williams,
*Classification of Schubert Galois groups in Gr(4,9)*, arXiv:1902.06809 (2019). - Abraham Martín del Campo and Frank Sottile,
*Experimentation in the Schubert calculus*, Schubert calculus—Osaka 2012, Adv. Stud. Pure Math., vol. 71, Math. Soc. Japan, [Tokyo], 2016, pp. 295–335. MR**3644828**, DOI 10.2969/aspm/07110295 - Alexander Morgan,
*Solving polynomial systems using continuation for engineering and scientific problems*, Classics in Applied Mathematics, vol. 57, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2009. Reprint of the 1987 original [ MR1049872]; Pages 304–534: computer programs section, also available as a separate file online. MR**3396207**, DOI 10.1137/1.9780898719031.pt1 - Alexander P. Morgan and Andrew J. Sommese,
*Coefficient-parameter polynomial continuation*, Appl. Math. Comput.**29**(1989), no. 2, 123–160. MR**977815**, DOI 10.1016/0096-3003(89)90099-4 - Frank Sottile,
*Pieri’s formula via explicit rational equivalence*, Canad. J. Math.**49**(1997), no. 6, 1281–1298. MR**1611668**, DOI 10.4153/CJM-1997-063-7 - Frank Sottile,
*Real Schubert calculus: polynomial systems and a conjecture of Shapiro and Shapiro*, Experiment. Math.**9**(2000), no. 2, 161–182. MR**1780204** - Frank Sottile,
*Real solutions to equations from geometry*, University Lecture Series, vol. 57, American Mathematical Society, Providence, RI, 2011. MR**2830310**, DOI 10.1090/ulect/057 - F. Sottile, R. Vakil, and J. Verschelde,
*Solving Schubert problems with Littlewood-Richardson homotopies*, ISSAC 2010—Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, 2010, pp. 179–186., DOI 10.1145/1837934.1837971 - Frank Sottile and Jacob White,
*Double transitivity of Galois groups in Schubert calculus of Grassmannians*, Algebr. Geom.**2**(2015), no. 4, 422–445. MR**3403235**, DOI 10.14231/AG-2015-018 - Ravi Vakil,
*A geometric Littlewood-Richardson rule*, Ann. of Math. (2)**164**(2006), no. 2, 371–421. Appendix A written with A. Knutson. MR**2247964**, DOI 10.4007/annals.2006.164.371 - Ravi Vakil,
*Schubert induction*, Ann. of Math. (2)**164**(2006), no. 2, 489–512. MR**2247966**, DOI 10.4007/annals.2006.164.489 - J. Verschelde,
*Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation*, ACM Transactions on Mathematical Software**25**(1999), no. 2, 251–276. - Jan Verschelde,
*Numerical evidence for a conjecture in real algebraic geometry*, Experiment. Math.**9**(2000), no. 2, 183–196. MR**1780205** - J. Verschelde,
*Moderizing PHCpack through phcpy*, Proceedings of the 6th european conference on python in science (euroscipy 2013), 2014, pp. 71–76. - J. Verschelde and Y. Wang,
*Computing feedback laws for linear systems with a parallel Pieri homotopy*, Proceedings of the 2004 international conference on parallel processing workshops, 2004, pp. 222–229.

Retrieve articles in *Mathematics of Computation*
with MSC (2020):
14N15,
65H10

Retrieve articles in all journals with MSC (2020): 14N15, 65H10

Additional Information

**Anton Leykin**

Affiliation:
School of Mathematics, Georgia Institute of Technology, 686 Cherry Street, Atlanta, Georgia 30332-0160

MR Author ID:
687160

ORCID:
0000-0002-9216-3514

Email:
leykin@math.gatech.edu

**Abraham Martín del Campo**

Affiliation:
Centro de Investigación en Matemáticas, A.C., Jalisco S/N, Col. Valenciana, 36023, Guanajuato, Gto. México

ORCID:
0000-0003-0369-0652

Email:
abraham.mc@cimat.mx

**Frank Sottile**

Affiliation:
Department of Mathematics, Texas A&M University, College Station, Texas 77843

MR Author ID:
355336

ORCID:
0000-0003-0087-7120

Email:
sottile@math.tamu.edu

**Ravi Vakil**

Affiliation:
Department of Mathematics, Stanford University, Stanford, California 94305

MR Author ID:
606760

ORCID:
0000-0001-8506-270X

Email:
vakil@math.stanford.edu

**Jan Verschelde**

Affiliation:
Deparment of Mathematics, Statisitics, and Computer Science, University of Illinois at Chicago, 851 South Morgan (M/C 249), Chicago, Illinois 60607

MR Author ID:
311807

Email:
jan@math.uic.edu

Keywords:
Schubert calculus,
Grassmannian,
Littlewood-Richardson rule,
numerical homotopy continuation

Received by editor(s):
April 17, 2018

Received by editor(s) in revised form:
July 3, 2020

Published electronically:
February 4, 2021

Additional Notes:
This project was supported by American Institute of Mathematics through their SQuaREs program. The work of the first author was supported in part by the National Science Foundation under grant DMS-1719968. The work of the second author was supported in part by CONACyT under grant Cátedra-1076. The work of the third author was supported in part by the National Science Foundation under grant DMS-1501370. The work of the fourth author was supported in part by the National Science Foundation under grant DMS-1500334. The work of the fifth author was supported in part by the National Science Foundation under grants ACI-1440534 and DMS-1854513

Article copyright:
© Copyright 2021
by the authors