Numerical Schubert calculus via the Littlewood-Richardson homotopy algorithm

Leykin, Anton; Martín del Campo, Abraham; Sottile, Frank; Vakil, Ravi; Verschelde, Jan

doi:10.1090/mcom/3579

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;

Math. Comp. 90 (2021), 1407-1433

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

Published electronically: February 4, 2021

HTML | PDF

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