Mathematics of Computation

Author(s): Anton Leykin; Frank Sottile.
Journal: Math. Comp. 78 (2009), 1749-1765.
MSC (2000): Primary 14N15, 65H20
Posted: February 25, 2009
Retrieve article in: PDF

Abstract: Numerical homotopy continuation of solutions to polynomial equations is the foundation for numerical algebraic geometry, whose development has been driven by applications of mathematics. We use numerical homotopy continuation to investigate the problem in pure mathematics of determining Galois groups in the Schubert calculus. For example, we show by direct computation that the Galois group of the Schubert problem of 3-planes in $\mathbb{C}^8$ meeting 15 fixed 5-planes non-trivially is the full symmetric group $S_{6006}$ .

1.: Daniel J. Bates, Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler, Bertini: Software for numerical algebraic geometry, Available at http:// www.nd.edu/˜sommese/ bertini.
2.: Daniel J. Bates, Andrew J. Peterson, Chrisand Sommese, and Charles W. Wampler, Numerical computation of the genus of an irreducible curve within an algebraic set, 2007.
3.: S. Billey and R. Vakil, Intersections of Schubert varieties and other permutation array schemes, Algorithms in Algebraic Geometry (A. Dickenstein, F.-O. Schreyer, and A. J. Sommese, eds.), IMA Volumes in Mathematics and its Applications, vol. 146, Springer, New York, 2007, pp. 21-54. MR 2397936
4.: C. I. Byrnes, Pole assignment by output feedback, Three Decades of Mathematical Systems Theory (H. Nijmeijer and J. M. Schumacher, eds.), Lecture Notes in Control and Inform. Sci., vol. 135, Springer-Verlag, Berlin, 1989, pp. 31-78. MR 1025786 (90k:93001)
5.: Wm. Fulton, Young tableaux, Cambridge University Press, Cambridge, 1997, With applications to representation theory and geometry. MR 1464693 (99f:05119)
6.: The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.4.9, 2006.
7.: Ewgenij Gawrilow and Michael Joswig, Polymake: A framework for analyzing convex polytopes, Polytopes--combinatorics and computation (Oberwolfach, 1997), DMV Sem., vol. 29, Birkhäuser, Basel, 2000, pp. 43-73. MR 1785292 (2001f:52033)
8.: J. Harris, Galois groups of enumerative problems, Duke Math. J. 46 (1979), 685-724. MR 552521 (80m:14038)
9.: B. Huber, F. Sottile, and B. Sturmfels, Numerical Schubert calculus, J. Symbolic Comput. 26 (1998), no. 6, 767-788. MR 1662035 (2000i:14079)
10.: B. Huber and J. 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 (electronic). MR 1760069 (2001g:93039)
11.: C. Jordan (ed.), Traité des substitutions, Gauthier-Villars, Paris, 1870.
12.: R. Baker Kearfott and Zhaoyun Xing, An interval step control for continuation methods, SIAM J. Numer. Anal. 31 (1994), no. 3, 892-914. MR 1275119 (94m:65076)
13.: S. Kleiman, The transversality of a general translate, Compositio Math. 28 (1974), 287-297. MR 0360616 (50:13063)
14.: S. Kleiman and D. Laksov, Schubert calculus, Amer. Math. Monthly 79 (1972), 1061-1082. MR 0323796 (48:2152)
15.: T. Lee, T.Y. Li, and C. Tsai, Hom4ps-2.0: A software package for solving polynomial systems by the polyhedral homotopy continuation method, Available at http://www.math.msu.edu/˜li/Software.htm, 2007.
16.: A. Leykin and F. Sottile, Galois groups of Schubert problems, 2007, www.math.tamu. edu/˜sottile/stories/Galois.
17.: A. Leykin and J. Verschelde, Interfacing with the numerical homotopy algorithms in PHCpack, Proceedings of ICMS 2006 (Nobuki Takayama and Andres Iglesias, eds.), Lecture Notes in Computer Sci., no. 4151, Springer, Berlin, 2006, pp. 354-360. MR 2387182
18.: A. Leykin, J. Verschelde, and Z. Yang, Parallel homotopy algorithms to solve polynomial systems, Proceedings of ICMS 2006 (Nobuki Takayama and Andres Iglesias, eds.), Lecture Notes in Computer Sci., no. 4151, Springer, Berlin, 2006, pp. 225-234. MR 2387173
19.: T.-Y. Li, personal communication.
20.: 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 (90m:65105)
21.: J. Ruffo, Y. Sivan, E. Soprunova, and F. Sottile, Experimentation and conjectures in the real Schubert calculus for flag manifolds, Experiment. Math. 15 (2006), no. 2, 199-221. MR 2253007 (2007g:14066)
22.: H. Schubert, Anzahl-Bestimmungen für lineare Räume. Beliebiger Dimension, Acta. Math. 8 (1886), 97-118. MR 1554694
23.: -, Losüng des Charakteristiken-Problems für lineare Räume. Beliebiger Dimension, Mittheil. Math. Ges. Hamburg (1886), 135-155, (dated 1885).
24.: M. Shub and S. Smale, Complexity of Bézout's Theorem. I: Geometric Aspects, J. American Mathematical Society 6 (1993), no. 2, 459-501. MR 1175980 (93k:65045)
25.: A. Sommese, J. Verschelde, and C. Wampler, Introduction to numerical algebraic geometry, Graduate School on Systems of Polynomial Equations: From Algebraic Geometry to Industrial Applications. 14-25 July 2003, Buenos Aires, Argentina (A. Dickenstein and I. Emiris, eds.), INRIA, 2003, A revised collection of the course notes is scheduled to be published by Springer-Verlag, pp. 229-247. MR 2161992
26.: A. Sommese and C. Wampler, The numerical solution of systems of polynomials. Arising in engineering and science, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2005. MR 2160078 (2007a:14065)
27.: F. Sottile, Pieri's formula via explicit rational equivalence, Canad. J. Math. 49 (1997), no. 6, 1281-1298. MR 1611668 (2000b:14070)
28.: -, Some real and unreal enumerative geometry for flag manifolds, Michigan Math. J. 48 (2000), 573-592, Dedicated to William Fulton on the occasion of his 60th birthday. MR 1786506 (2002d:14085)
29.: -, Elementary transversality in the Schubert calculus in any characteristic, Michigan Math. J. 51 (2003), no. 3, 651-666. MR 2021013 (2004i:14065)
30.: Richard P. Stanley, Some combinatorial aspects of the Schubert calculus, Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976), Lecture Notes in Math., Vol. 579, Springer, Berlin, 1977, pp. 217-251. MR 0465880 (57:5766)
31.: R. Vakil, A geometric Littlewood-Richardson rule, Ann. of Math. (2) 164 (2006), no. 2, 371-421, Appendix A written with A. Knutson. MR 2247964 (2007f:05184)
32.: -, Schubert induction, Ann. of Math. (2) 164 (2006), no. 2, 489-512. MR 2247966 (2007j:14082)
33.: J. Verschelde, Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Softw. 25 (1999), no. 2, 251-276, Software available at http://www.math.uic.edu/˜jan.

Anton Leykin
Affiliation: Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, 851 S. Morgan Street (M/C 249), Chicago, Illinois 60607-7045
Email: leykin@math.uic.edu

Frank Sottile
Affiliation: Department of Mathematics, Texas A&M University, College Station, Texas 77843
Email: sottile@math.tamu.edu

DOI: 10.1090/S0025-5718-09-02239-X
PII: S 0025-5718(09)02239-X
Keywords: Polynomial homotopy continuation, Schubert problem, Galois group
Received by editor(s): February 22, 2008
Received by editor(s) in revised form: June 14, 2008
Posted: February 25, 2009
Additional Notes: The authors were supported by the Institute for Mathematics and its Applications and Sottile by NSF grants CAREER DMS-0538734 and DMS-0701050
Copyright of article: Copyright 2009, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS