Mathematics of Computation

Author(s): J. William Hoffman; James J. Madden; Hong Zhang.
Journal: Math. Comp. 72 (2003), 975-1002.
MSC (2000): Primary 65H10; Secondary 13P99, 14Q99, 14P10
Posted: May 15, 2002
Retrieve article in: PDF DVI PostScript

Abstract: The pseudozero set of a system

of polynomials in

complex variables is the subset of $\mathord{\bf C}^n$ which is the union of the zero-sets of all polynomial systems

that are near to

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.

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

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

J. William Hoffman
Affiliation: Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803
Email: hoffman@math.lsu.edu

James J. Madden
Affiliation: Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803
Email: madden@math.lsu.edu

			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 2008, American Mathematical Society Privacy Statement		Search the AMS