Numerical Evidence for a Conjecture in Real Algebraic Geometry

REFERENCES

• Allgower , E. L. and Georg , K. 1990 . Numerical continuation methods: an introduction Berlin : Springer. . [Allgower and Georg 1990], Springer Ser. Comput. Math. 13
   Google Scholar
• Allgower , E. L. and Georg , K. 1997 . “Numerical path following”. ” . In Handbook of numerical analysis, V: Techniques of scientific computing (Part 2) Edited by: Ciarlet , P. G. and Lions , J. L. 3 – 207 . Amsterdam : North-Holland. . [Allgower and Georg 1997]
   Google Scholar
• Ando , T. 1987 . “Totally positive matrices” . Linear Algebra Appl. , 90 : 165 – 219 . [Ando 1987]
   Web of Science ®Google Scholar
• Bernshteìn , D. N. 1975 . “The number of roots of a system of equations” . Funktsional. Anal. i Prilozhen. , 9 ( 3 ) : 1 – 4 . [Bernshteìn 1975], In Russian; translated in Functional Anal. Appl, 9:3 (1975), 183–185
   Google Scholar
• Bharucha-Reid , A. T. and Sambandham , M. 1986 . Random polynomials Orlando , FL : Academic Press Inc. . [Bharucha-Reid and Sambandham 1986]
   Google Scholar
• Blum , L. , Cucker , F. , Shub , M. and Smale , S. 1998 . Complexity and real computation New York : Springer. . [Blum et al. 1998]
   Google Scholar
• Brockett , R. W. and Byrnes , C. I. 1981 . “Multivariable Nyquist criteria, root loci, and pole placement: a geometric viewpoint” . IEEE Trans. Automat. Control , 26 ( 1 ) : 271 – 284 . [Brockett and Byrnes 1981]
   Web of Science ®Google Scholar
• Byrnes , C. I. 1989 . “Pole assignment by output feedback”. ” . In Three decades of mathematical system theory Edited by: Nijmacher , H. and Schumacher , J. M. 31 – 78 . Berlin : Springer. . [Byrnes 1989], Lecture Notes in Control and Inform. Sci. 135
   Google Scholar
• Cox , D. , Little , J. and O'Shea , D. 1997 . Ideals, varieties, and algorithms: An introduction to computational algebraic geometry and commutative algebra, , 2nd ed. New York : Undergraduate Texts in Math., Springer. . [Cox et al. 1997]
   Google Scholar
• Cox , D. , Little , J. and O'Shea , D. 1998 . Using algebraic geometry New York : Springer. . [Cox et al. 1998], Graduate Texts in Math. 185
   Google Scholar
• Cucker , F. and Roy , M.-F. 1990 . “A theorem on random polynomials and some consequences in average complexity” . J. Symbolic Comput. , 10 ( 5 ) : 405 – 409 . [Cucker and Roy 1990]
   Web of Science ®Google Scholar
• Dedieu , J. P. and Shub , M. 2000 . “Newton's method for overdetermined systems of equations” . Math. Comp. , 69 ( 231 ) : 1099 – 1115 . [Dedieu and Shub 2000]
   Web of Science ®Google Scholar
• Edelman , A. , Arias , T. A. and Smith , S. T. 1999 . “The geometry of algorithms with orthogonality constraints” . SIAM J. Matrix Anal. Appl. , 20 ( 2 ) : 303 – 353 . [Edelman et al. 1999]
   Web of Science ®Google Scholar
• Eisenbud , D. 1995 . Commutative algebra with a view toward algebraic geometry New York : Springer. . [Eisenbud 1995], Graduate Texts in Math. 150
   Google Scholar
• Faugère , J.-C. , Rouillier , F. and Zimmerman , P. 1998 . [Faugère et al. 1998], Personal communication
   Google Scholar
• Fulton , W. 1997 . Young tableaux Cambridge : Cambridge University Press. . [Fulton 1997], London Math. Soc. Student Texts 35
   Google Scholar
• Gerald , C. F. 1978 . Applied numerical analysis, , 2nd ed. Reading , MA : Addison-Wesley. . [Gerald 1978]
   Google Scholar
• Golub , G. H. and Van Loan , C. F. 1996 . Matrix computations, , 3rd ed. Baltimore : Johns Hopkins Univ. Press. . [Golub and Van Loan 1996]
   Google Scholar
• Huber , B. and Sturmfels , B. 1995 . “A polyhedral method for solving sparse polynomial systems” . Math. Comp. , 64 ( 212 ) : 1541 – 1555 . [Huber and Sturmfels 1995]
   Web of Science ®Google Scholar
• Huber , B. and Verschelde , J. 1998 . “Polyhedral end games for polynomial continuation” . Numer. Algorithms , 18 ( 1 ) : 91 – 108 . [Huber and Verschelde 1998]
   Web of Science ®Google Scholar
• Huber , B. and Verschelde , J. 2000 . “Pieri homotopies for problems in enumerative geometry applied to pole placement in linear systems control” . SIAM J. Control Optim. , 38 ( 4 ) : 1265 – 1287 . [Huber and Verschelde 2000]
   Web of Science ®Google Scholar
• Huber , B. , Sottile , F. and Sturmfels , B. 1998 . “Numerical Schubert calculus” . J. Symbolic Comput. , 26 ( 6 ) : 767 – 788 . [Huber et al. 1998]
   Web of Science ®Google Scholar
• Kailath , T. 1980 . Linear systems Englewood Cliffs , NJ : Prentice-Hall Inc. . [Kailath 1980]
   Google Scholar
• Kushnirenko , A. G. 1976 . “Newton poly-topes and the Bézout theorem” . Funktsional. Anal, I Prilozhen. , 10 ( 3 ) : 82 – 83 . [Kushnirenko 1976], In Russian; translated in Functional Anal. Appl. 10:3 (1976), 233–235
   Google Scholar
• Li , T. Y. 1997 . “Numerical solution of multivariate polynomial systems by homotopy continuation methods”. ” . In Acta numerica, 1997 399 – 436 . Cambridge : Cambridge Univ. Press. . [Li 1997]
   Google Scholar
• Li , T. Y. and Wang , X. S. 1992 . “Nonlinear homotopies for solving deficient polynomial systems with parameters” . SIAM J. Numer. Anal. , 29 ( 4 ) : 1104 – 1118 . [Li and Wang 1992]
   Web of Science ®Google Scholar
• Li , T. Y. , Sauer , T. and Yorke , J. A. 1989 . “The cheater's homotopy: an efficient procedure for solving systems of polynomial equations” . SIAM J. Numer. Anal. , 26 ( 5 ) : 1241 – 1251 . [Li et al. 1989]
   Web of Science ®Google Scholar
• Loewner , C. 1955 . “On totally positive matrices” . Math. Z. , 63 : 338 – 340 . [Loewner 1955]
   Google Scholar
• Morgan , A. 1987 . Solving polynomial systems using continuation for engineering and scientific problems Englewood Cliffs , NJ : Prentice-Hall Inc. . [Morgan 1987]
   Google Scholar
• Morgan , A. and Sommese , A. 1987 . “A homotopy for solving general polynomial systems that respects m-homogeneous structures” . Appl. Math. Comput. , 24 ( 2 ) : 101 – 113 . [Morgan and Sommese 1987]
   Web of Science ®Google Scholar
• Morgan , A. P. and Sommese , A. J. 1989 . “Coefficient-parameter polynomial continuation” . Appl. Math. Comput. , 29 ( 2(11) : 123 – 160 . [Morgan and Sommese 1989], Errata in 51:2–3 (1992), 207
   Web of Science ®Google Scholar
• Rosenthal , J. 1994 . “On dynamic feedback compensation and compactification of systems” . SIAM J. Control Optim. , 32 ( 1 ) : 279 – 296 . [Rosenthal 1994]
   Web of Science ®Google Scholar
• Rosenthal , J. and Schumacher , J. M. 1997 . “Realization by inspection” . IEEE Trans. Automat. Control , 42 ( 9 ) : 1257 – 1263 . [Rosenthal and Schumacher 1997]
   Web of Science ®Google Scholar
• Rosenthal , J. and Sottile , F. 1998 . “Some remarks on real and complex output feedback” . Systems Control Lett. , 33 ( 2 ) : 73 – 80 . [Rosenthal and Sottile 1998], See http://www.nd.edu/~rosen/pole for a description of computational aspects of the paper
   Web of Science ®Google Scholar
• Rosenthal , J. and Willems , J. C. 1999 . “Open problems in the area of pole placement”. ” . In Open problems in mathematical systems and control theory Edited by: Blondel , V. D. 181 – 191 . London : Springer. . [Rosenthal and Willems 1999], Comm. and Control Engin. Series
   Google Scholar
• Schubert , H. 1891 . “Beziehungen zwischen den linearen Räumen auferlegbaren charakteristischen Bedingungen” . Math. Ann. , 38 : 588 – 602 . [Schubert 1891]
   Google Scholar
• Sottile , F. 1999 . “The special Schubert calculus is real” . Electron. Res. Announc. Amer. Math. Soc. , 5 : 35 – 39 . [Sottile 1999], See http://www.ams.org/era
   Google Scholar
• Sottile , F. 2000 . “Real rational curves in Grassmannians” . J. Amer. Math. Soc. , 13 ( 2 ) : 333 – 341 . [Sottile 2000a]
   Web of Science ®Google Scholar
• Sottile , F. 2000 . “Real Schubert calculus: polynomial systems and a conjecture of Shapiro and Shapiro” . Experiment. Math. , 9 ( 2 ) : 161 – 182 . [Sottile 2000b]
   Web of Science ®Google Scholar
• Stetter , H. J. 1998 . “Numerical polynomial algebra” [Stetter 1998], Technical report, Notes for the tutorial Interaction between Numerical Analysis and Computer Algebra, held at ISSAC'98, Rostock, Germany
   Google Scholar
• Sturmfels , B. 1993 . Algorithms in invariant theory Vienna : Springer. . [Sturmfels 1993]
   Google Scholar
• Sturmfels , B. 1996 . Gröbner bases and convex polytopes Providence , RI : Amer. Math. Soc. . [Sturmfels 1996], Univ. Lecture Ser. 8
   Google Scholar
• Sturmfels , B. 1998 . “Polynomial equations and convex polytopes” . Amer. Math. Monthly , 105 ( 10 ) : 907 – 922 . [Sturmfels 1998]
   Web of Science ®Google Scholar
• Verschelde , J. 1999 . Algorithm 795: PHC-pack: A general-purpose solver for polynomial systems by homotopy continuation” . ACM Trans. Math. Software , 25 ( 2 ) : 251 – 276 . [Verschelde 1999], See http://www.math.msu.edu/~jan
   Web of Science ®Google Scholar
• Verschelde , J. , Verlinden , P. and Cools , R. 1994 . “Homotopies exploiting Newton polytopes for solving sparse polynomial systems” . SIAM J. Numer. Anal. , 31 ( 3 ) : 915 – 930 . [Verschelde et al. 1994]
   Web of Science ®Google Scholar
• Verschelde , J. , Gatermann , K. and Cools , R. 1996 . “Mixed-volume computation by dynamic lifting applied to polynomial system solving” . Discrete Comput. Geom. , 16 ( 1 ) : 69 – 112 . [Verschelde et al. 1996]
   Web of Science ®Google Scholar
• Wampler , C. W. 1992 . “Bezout number calculations for multi-homogeneous polynomial systems” . Appl. Math. Comput. , 51 ( 2–3 ) : 143 – 157 . [Wampler 1992]
   Web of Science ®Google Scholar
• Wampler , C. W. , Morgan , A. P. and Sommese , A. J. 1990 . “Numerical continuation methods for solving polynomial systems arising in kinematics” . ASME J. of Mechanical Design , 112 ( 1 ) : 59 – 68 . [Wampler et al. 1990]
   Web of Science ®Google Scholar
• Wampler , C. W. , Morgan , A. P. and Sommese , A. J. 1992 . “Complete solution of the nine-point path synthesis problem for four-bar linkages” . ASME J. of Mechanical Design , 114 ( 1 ) : 153 – 159 . [Wampler et al. 1992]
   Web of Science ®Google Scholar
• Whitney , A. M. 1952 . “A reduction theorem for totally positive matrices” . J. Analyse Math. , 2 : 88 – 92 . [Whitney 1952]
   Google Scholar
• Yakoubsohn , J.-C. 1999 . “Finding zeros of analytic functions: α-theory for secant type methods” . J. Complexity , 15 ( 2 ) : 239 – 281 . [Yakoubsohn 1999]
   Web of Science ®Google Scholar