Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Pseudozeros of multivariate polynomials

Authors: J. William Hoffman, James J. Madden and Hong Zhang
Journal: Math. Comp. 72 (2003), 975-1002
MSC (2000): Primary 65H10; Secondary 13P99, 14Q99, 14P10
Published electronically: May 15, 2002
MathSciNet review: 1954980
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The pseudozero set of a system $f$ of polynomials in $n$ complex variables is the subset of $\mathord{\bf 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 [Enhancements On Off] (What's this?)

  • 1. L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and real computation, Springer-Verlag, 1998. MR 99a:68070
  • 2. J. Bochnak, M. Coste, and M.-F. Roy, Real algebraic geometry, Ergebnisse der Mathematik, vol. 36, Springer - Verlag, 1998. MR 2000a:14067
  • 3. F. Chaitin-Chatelin and V. Frayssé, Lectures on finite precision computations, software-environments-tools, SIAM, Philadelphia, 1996. MR 97b:65059
  • 4. 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.
  • 5. D. Cox, J. Little, and D. O'Shea, Ideals, varieties, and algorithms, Undergraduate Texts in Mathematics, Springer-Verlag, 1992. MR 93j:13031
  • 6. -, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer - Verlag, 1998. MR 99h:13033
  • 7. F. J. Drexler, Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen, Numer. Math. 29 (1977), 45-58. MR 58:3392
  • 8. A. Edelman and H. Murakami, Polynomial roots from companion matrix eigenvalues, Mathematics of Computation. 64 (1995) 64 (1995), 763-776. MR 95f:65075
  • 9. R.T. Farouki and V.T. Rajan, On the numerical condition of polynomials in Bernstein form, Computer Aided Geometric Design 4 (1987), 191-216. MR 90f:65028
  • 10. G. Fischer, Complex analytic geometry, Lecture Notes in Mathematics, vol. 538, Springer - Verlag, 1976. MR 55:3291
  • 11. C. B. Garcia and W. I. Zangwill, Finding all solutions to polynomial systems and other systems of equations, Math. Program. 16 (1979), 159-176. MR 80f:65057
  • 12. W. Gautschi, Questions of numerical condition related to polynomials, G.H. Golub, ed., Studies in Numerical Analysis, MAA Studies in Math. 24 (1984), 140-177. MR 88i:65007
  • 13. I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants and multidimensional determinants, Birkhäuser, 1994. MR 95e:14045
  • 14. Nicholas J. Higham, Accuracy and stability of numerical algorithms, SIAM, 1996. MR 97a:65047
  • 15. 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. CMP 2001:07
  • 16. 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.
  • 17. S. Ji, J. Kollar, and B. Shiffman, A global Lojasiewicz inequality for algebraic varieties, Transactions of the Amer. Math. Soc. 329 (1992), 813-818. MR 92e:32007
  • 18. T. Y. Li, Numerical solution of multivariate polynomial systems by homotopy continuation methods, Acta Numerica 6 (1997), 399-436. MR 2000i:65084
  • 19. D. Manocha and J. F. Canny, Multipolynomial resultant algorithms, J. Symbolic Comput. 15 (1993), 99-122. MR 93m:68094
  • 20. H. Matsumura, Commutative algebra, Benjamin - Cummings, 1980. MR 82i:13003
  • 21. A. P. Morgan, Polynomial continuation and its relationship to the symbolic reduction of polynomial systems, Symbolic and Numerical Computation for Artificial Intelligence, B. Donald et al. eds. (1992), 23-45. MR 96c:68160
  • 22. R. Mosier, Root neighborhoods of a polynomial, Math. Comp. 47 (1986), 265-273. MR 87k:65056
  • 23. B. Mourrain and H. Prieto, A framework for symbolic and numeric computations, INRIA, Rapport de recherche 4013 (2000).
  • 24. D. Mumford, The red book of varieties and schemes, Lecture Notes in Mathematics, vol. 1358, Springer - Verlag, 1988. MR 89k:14001
  • 25. A. Neumaier, Interval methods for systems of equations, Cambridge U. Press, 1990. MR 92b:65004
  • 26. W. Oettli and W. Prager, Compatability of approximate solutions of linear equations with given error bounds for coefficients and right hand sides, Numer. Math. 6 (1964), 405-409. MR 29:5371
  • 27. H. J. Stetter, The nearest polynomial with a given zero, and similar problems, SIGSAM Bull. 33 (1999), no. 4, 2-4.
  • 28. -, Polynomials with coefficients of limited accuracy, Computer algebra in scientific computing (V. G. Ganzha, E. W. Mayr, and E. V. Vorozhtsov, eds.), Springer, 1999, pp. 409-430. MR 2001h:65063
  • 29. -, 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.
  • 30. G. W. Stewart, Afternotes on numerical analysis, SIAM, 1996. MR 98m:65004
  • 31. K. C. Toh and L. N. Trefethen, Pseudozeros of polynomials and pseudospectra of companion matrices, Numer. Math. 68 (1994), 403-425. MR 95m:65085
  • 32. J.H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Englewood Cliffs. N.J., 1963. MR 28:4661
  • 33. H. Zhang, Numerical condition of polynomials in different forms, Electronic Transactions on Numerical Analysis 12 (2001), 66-87.
  • 34. W. Zulehner, A simple homotopy method for determining all isolated solutions to polynomial systems, Math. Comp. 50 (1988), 167-177. MR 89b:65130

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65H10, 13P99, 14Q99, 14P10

Retrieve articles in all journals with MSC (2000): 65H10, 13P99, 14Q99, 14P10

Additional Information

J. William Hoffman
Affiliation: Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803

James J. Madden
Affiliation: Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803

Hong Zhang
Affiliation: Department of Computer Science, Illinois Institute of Technology, Chicago, Illinois 60616

Keywords: Multivariate polynomial, pseudozeros, semialgebraic set, algorithm
Received by editor(s): May 5, 2000
Received by editor(s) in revised form: April 24, 2001
Published electronically: May 15, 2002
Article copyright: © Copyright 2002 American Mathematical Society

American Mathematical Society