×

Numerical evidence for a conjecture in real algebraic geometry. (English) Zbl 1054.14080

Summary: Homotopies provide computational evidence for a challenging instance of a conjecture about whether all solutions are real. By a homotopy we mean a family of polynomial systems that describes algebraically the geometric transition from an easier configuration in special position into the general configuration for the problem we want to solve. The solutions to our problem lie at the end of the solution paths we trace with numerical continuation methods starting at the solutions of the easier, special problem. The numerical difficulties are overcome if we work in the true synthetic spirit of the Schubert calculus, selecting the numerically most favorable equations to represent the geometric problem. Since a well-conditioned polynomial system allows perturbations on the input data without destroying the reality of the solutions we obtain not just one instance, but a whole manifold of systems that satisfy the conjecture. Also an instance that involves totally positive matrices has been verified. The optimality of the solving procedure is a promising first step towards the development of numerically stable algorithms for the pole placement problem in linear systems theory.

MSC:

14Q15 Computational aspects of higher-dimensional varieties
65H10 Numerical computation of solutions to systems of equations
14P05 Real algebraic sets
14M15 Grassmannians, Schubert varieties, flag manifolds
PDF BibTeX XML Cite
Full Text: DOI Euclid EuDML

References:

[1] Allgower E. L., Numerical continuation methods: an introduction (1990) · Zbl 0717.65030
[2] Allgower E. L., Handbook of numerical analysis, V: Techniques of scientific computing (Part 2) pp 3– (1997)
[3] Ando T., Linear Algebra Appl. 90 pp 165– (1987) · Zbl 0613.15014
[4] Bernshteìn D. N., Funktsional. Anal. i Prilozhen. 9 (3) pp 1– (1975)
[5] Bharucha-Reid A. T., Random polynomials (1986)
[6] Blum L., Complexity and real computation (1998)
[7] Brockett R. W., IEEE Trans. Automat. Control 26 (1) pp 271– (1981) · Zbl 0462.93026
[8] Byrnes C. I., Three decades of mathematical system theory pp 31– (1989)
[9] Cox D., Ideals, varieties, and algorithms: An introduction to computational algebraic geometry and commutative algebra,, 2. ed. (1997)
[10] Cox D., Using algebraic geometry (1998) · Zbl 0920.13026
[11] Cucker F., J. Symbolic Comput. 10 (5) pp 405– (1990) · Zbl 0725.12007
[12] Dedieu J. P., Math. Comp. 69 (231) pp 1099– (2000) · Zbl 0949.65061
[13] Edelman A., SIAM J. Matrix Anal. Appl. 20 (2) pp 303– (1999) · Zbl 0928.65050
[14] Eisenbud D., Commutative algebra with a view toward algebraic geometry (1995) · Zbl 0819.13001
[15] Faugère, J.C., Rouillier, F. and Zimmerman, P. 1998. [Faugère et al. 1998], Personal communication
[16] Fulton W., Young tableaux (1997)
[17] Gerald C. F., Applied numerical analysis,, 2. ed. (1978)
[18] Golub G. H., Matrix computations,, 3. ed. (1996) · Zbl 0865.65009
[19] Huber B., Math. Comp. 64 (212) pp 1541– (1995)
[20] Huber B., Numer. Algorithms 18 (1) pp 91– (1998) · Zbl 0933.65057
[21] Huber B., SIAM J. Control Optim. 38 (4) pp 1265– (2000) · Zbl 0955.14038
[22] Huber B., J. Symbolic Comput. 26 (6) pp 767– (1998) · Zbl 1064.14508
[23] Kailath T., Linear systems (1980) · Zbl 0454.93001
[24] Kushnirenko A. G., Funktsional. Anal, I Prilozhen. 10 (3) pp 82– (1976)
[25] Li T. Y., Acta numerica, 1997 pp 399– (1997)
[26] Li T. Y., SIAM J. Numer. Anal. 29 (4) pp 1104– (1992) · Zbl 0763.65037
[27] Li T. Y., SIAM J. Numer. Anal. 26 (5) pp 1241– (1989) · Zbl 0689.65032
[28] Loewner C., Math. Z. 63 pp 338– (1955) · Zbl 0068.25004
[29] Morgan A., Solving polynomial systems using continuation for engineering and scientific problems (1987) · Zbl 0733.65031
[30] Morgan A., Appl. Math. Comput. 24 (2) pp 101– (1987) · Zbl 0635.65057
[31] Morgan A. P., Appl. Math. Comput. 29 (2) pp 123– (1989) · Zbl 0664.65049
[32] Rosenthal J., SIAM J. Control Optim. 32 (1) pp 279– (1994) · Zbl 0797.93018
[33] Rosenthal J., IEEE Trans. Automat. Control 42 (9) pp 1257– (1997) · Zbl 0890.93016
[34] Rosenthal J., Systems Control Lett. 33 (2) pp 73– (1998) · Zbl 0902.93036
[35] Rosenthal J., Open problems in mathematical systems and control theory pp 181– (1999)
[36] Schubert H., Math. Ann. 38 pp 588– (1891)
[37] Sottile F., Electron. Res. Announc. Amer. Math. Soc. 5 pp 35– (1999) · Zbl 0921.14037
[38] Sottile F., J. Amer. Math. Soc. 13 (2) pp 333– (2000) · Zbl 0946.14035
[39] Sottile F., Experiment. Math. 9 (2) pp 161– (2000) · Zbl 0997.14016
[40] Stetter H. J., ”Numerical polynomial algebra” (1998) · Zbl 1058.65054
[41] Sturmfels B., Algorithms in invariant theory (1993) · Zbl 0802.13002
[42] Sturmfels B., Gröbner bases and convex polytopes (1996) · Zbl 0856.13020
[43] Sturmfels B., Amer. Math. Monthly 105 (10) pp 907– (1998) · Zbl 0988.52021
[44] Verschelde J., ACM Trans. Math. Software 25 (2) pp 251– (1999) · Zbl 0961.65047
[45] Verschelde J., SIAM J. Numer. Anal. 31 (3) pp 915– (1994) · Zbl 0809.65048
[46] Verschelde J., Discrete Comput. Geom. 16 (1) pp 69– (1996) · Zbl 0854.68111
[47] Wampler C. W., Appl. Math. Comput. 51 (2) pp 143– (1992) · Zbl 0759.65023
[48] Wampler C. W., ASME J. of Mechanical Design 112 (1) pp 59– (1990)
[49] Wampler C. W., ASME J. of Mechanical Design 114 (1) pp 153– (1992)
[50] Whitney A. M., J. Analyse Math. 2 pp 88– (1952) · Zbl 0049.17104
[51] Yakoubsohn J.-C., J. Complexity 15 (2) pp 239– (1999) · Zbl 0944.65061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.