## Numerical Schubert calculus via the Littlewood-Richardson homotopy algorithm

HTML articles powered by AMS MathViewer

- by
Anton Leykin, Abraham Martín del Campo, Frank Sottile, Ravi Vakil and Jan Verschelde
**HTML**| PDF - Math. Comp.
**90**(2021), 1407-1433

## 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.## References

- 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.

## 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
- 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
- © Copyright 2021 by the authors
- Journal: Math. Comp.
**90**(2021), 1407-1433 - MSC (2020): Primary 14N15, 65H10
- DOI: https://doi.org/10.1090/mcom/3579
- MathSciNet review: 4232229