Pseudozeros of multivariate polynomials

Hoffman, J.; Madden, James; Zhang, Hong

doi:10.1090/S0025-5718-02-01429-1

Pseudozeros of multivariate polynomials
HTML articles powered by AMS MathViewer

by J. William Hoffman, James J. Madden and Hong Zhang PDF

Math. Comp. 72 (2003), 975-1002 Request permission

Abstract:

The pseudozero set of a system $f$ of polynomials in $n$ complex variables is the subset of $\mathbf {C}^n$ which is the union of the zero-sets of all polynomial systems $g$ that are near to $f$ in a suitable sense. This concept is made precise, and general properties of pseudozero sets are established. In particular it is shown that in many cases of natural interest, the pseudozero set is a semialgebraic set. Also, estimates are given for the size of the projections of pseudozero sets in coordinate directions. Several examples are presented illustrating some of the general theory developed here. Finally, algorithmic ideas are proposed for solving multivariate polynomials.

References

Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale, Complexity and real computation, Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. MR 1479636, DOI 10.1007/978-1-4612-0701-6
Jacek Bochnak, Michel Coste, and Marie-Françoise Roy, Real algebraic geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 36, Springer-Verlag, Berlin, 1998. Translated from the 1987 French original; Revised by the authors. MR 1659509, DOI 10.1007/978-3-662-03718-8
Françoise Chaitin-Chatelin and Valérie Frayssé, Lectures on finite precision computations, Software, Environments, and Tools, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. With a foreword by Iain S. Duff. MR 1381897, DOI 10.1137/1.9780898719673
R. M. Corless, P. M. Gianni, B. M. Trager, and S. M. Watt, The singular value decomposition for polynomial systems, ISAAC (A. H. M. Levelt, ed.), ACM Press, 1995, pp. 96–103.
David Cox, John Little, and Donal O’Shea, Ideals, varieties, and algorithms, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1992. An introduction to computational algebraic geometry and commutative algebra. MR 1189133, DOI 10.1007/978-1-4757-2181-2
David Cox, John Little, and Donal O’Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer-Verlag, New York, 1998. MR 1639811, DOI 10.1007/978-1-4757-6911-1
Franz-Josef Drexler, Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen, Numer. Math. 29 (1977/78), no. 1, 45–58 (German, with English summary). MR 483386, DOI 10.1007/BF01389312
Alan Edelman and H. Murakami, Polynomial roots from companion matrix eigenvalues, Math. Comp. 64 (1995), no. 210, 763–776. MR 1262279, DOI 10.1090/S0025-5718-1995-1262279-2
R. T. Farouki and V. T. Rajan, On the numerical condition of algebraic curves and surfaces. I. Implicit equations, Comput. Aided Geom. Design 5 (1988), no. 3, 215–252. MR 959606, DOI 10.1016/0167-8396(88)90005-2
Gerd Fischer, Complex analytic geometry, Lecture Notes in Mathematics, Vol. 538, Springer-Verlag, Berlin-New York, 1976. MR 0430286, DOI 10.1007/BFb0080338
C. B. García and W. I. Zangwill, Finding all solutions to polynomial systems and other systems of equations, Math. Programming 16 (1979), no. 2, 159–176. MR 527572, DOI 10.1007/BF01582106
Gene H. Golub (ed.), Studies in numerical analysis, MAA Studies in Mathematics, vol. 24, Mathematical Association of America, Washington, DC, 1984. MR 925209
I. M. Gel′fand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1264417, DOI 10.1007/978-0-8176-4771-1
Nicholas J. Higham, Accuracy and stability of numerical algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1368629
M. A. Hitz and E. Kaltofen, Efficient algorithms for computing the nearest polynomial with constrained roots, ISAAC (O. Gloor, ed.), ACM Press, 1998, pp. 236–243.
M. A. Hitz, E. Kaltofen, and Y. N. Lakshman, Efficient algorithms for computing the nearest polynomial with a real root and related problems, ISAAC (S. Dooley, ed.), ACM Press, 1999, pp. 205–212.
Shanyu Ji, János Kollár, and Bernard Shiffman, A global Łojasiewicz inequality for algebraic varieties, Trans. Amer. Math. Soc. 329 (1992), no. 2, 813–818. MR 1046016, DOI 10.1090/S0002-9947-1992-1046016-6
T. Y. Li, Numerical solution of multivariate polynomial systems by homotopy continuation methods, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 399–436. MR 1489259, DOI 10.1017/S0962492900002749
Dinesh Manocha and John F. Canny, Multipolynomial resultant algorithms, J. Symbolic Comput. 15 (1993), no. 2, 99–122. MR 1218754, DOI 10.1006/jsco.1993.1009
Hideyuki Matsumura, Commutative algebra, 2nd ed., Mathematics Lecture Note Series, vol. 56, Benjamin/Cummings Publishing Co., Inc., Reading, Mass., 1980. MR 575344
Bruce Randall Donald, Deepak Kapur, and Joseph L. Mundy (eds.), Symbolic and numerical computation for artificial intelligence, Computational Mathematics and Applications, Academic Press, Ltd., London, 1992. MR 1345879
Ronald G. Mosier, Root neighborhoods of a polynomial, Math. Comp. 47 (1986), no. 175, 265–273. MR 842134, DOI 10.1090/S0025-5718-1986-0842134-4
B. Mourrain and H. Prieto, A framework for symbolic and numeric computations, INRIA, Rapport de recherche 4013 (2000).
David Mumford, The red book of varieties and schemes, Lecture Notes in Mathematics, vol. 1358, Springer-Verlag, Berlin, 1988. MR 971985, DOI 10.1007/978-3-662-21581-4
Arnold Neumaier, Interval methods for systems of equations, Encyclopedia of Mathematics and its Applications, vol. 37, Cambridge University Press, Cambridge, 1990. MR 1100928, DOI 10.1007/978-94-011-3330-2
W. Oettli and W. Prager, Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides, Numer. Math. 6 (1964), 405–409. MR 168106, DOI 10.1007/BF01386090
H. J. Stetter, The nearest polynomial with a given zero, and similar problems, SIGSAM Bull. 33 (1999), no. 4, 2–4.
Hans J. Stetter, Polynomials with coefficients of limited accuracy, Computer algebra in scientific computing—CASC’99 (Munich), Springer, Berlin, 1999, pp. 409–430. MR 1729639
—, Condition analysis of overdetermined algebraic problems, Computer algebra in scientific computing, CASC 2000 (V. G. Ganzha, E. W. Mayr, and E. V. Vorozhtsov, eds.), Springer, 2000, pp. 345–365.
G. W. Stewart, Afternotes goes to graduate school, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. Lectures on advanced numerical analysis. MR 1613128, DOI 10.1137/1.9781611971422
Kim-Chuan Toh and Lloyd N. Trefethen, Pseudozeros of polynomials and pseudospectra of companion matrices, Numer. Math. 68 (1994), no. 3, 403–425. MR 1313152, DOI 10.1007/s002110050069
J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
H. Zhang, Numerical condition of polynomials in different forms, Electronic Transactions on Numerical Analysis 12 (2001), 66–87.
Walter Zulehner, A simple homotopy method for determining all isolated solutions to polynomial systems, Math. Comp. 50 (1988), no. 181, 167–177. MR 917824, DOI 10.1090/S0025-5718-1988-0917824-7