×

Pseudozeros of multivariate polynomials. (English) Zbl 1017.65047

The authors present precise results on the pseudozeros of multivariate polynomials based on a general concept that the pseudozero set of a system \(f\) of polynomials in \(n\) complex variables is the subset of \({\mathbb C}^n\) which is the union of the zeros-sets of all polynomial systems \(g\) that are near to \(f\) in a suitable sense. The authors also show that in many cases the pseudozero set is a semialgebraic set. Several examples for illustrating the general theory are illustrated. Some algorithmic ideas for solving multivariate polynomials are proposed as well.

MSC:

65H05 Numerical computation of solutions to single equations
14P10 Semialgebraic sets and related spaces
13P05 Polynomials, factorization in commutative rings
12Y05 Computational aspects of field theory and polynomials (MSC2010)
26C10 Real polynomials: location of zeros
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)

Software:

mctoolbox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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. · Zbl 0872.68036
[2] 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. · Zbl 0912.14023
[3] 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. · Zbl 0846.65020
[4] R. M. Corless, P. M. Gianni, B. M. Trager, and S. M. Watt, The singular value decomposition for polynomial systems, ISAAC , ACM Press, 1995, pp. 96-103. · Zbl 0920.65034
[5] 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. · Zbl 0756.13017
[6] David Cox, John Little, and Donal O’Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer-Verlag, New York, 1998. · Zbl 0920.13026
[7] 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). · Zbl 0352.65023 · doi:10.1007/BF01389312
[8] Alan Edelman and H. Murakami, Polynomial roots from companion matrix eigenvalues, Math. Comp. 64 (1995), no. 210, 763 – 776. · Zbl 0833.65041
[9] 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. · Zbl 0709.65011 · doi:10.1016/0167-8396(88)90005-2
[10] Gerd Fischer, Complex analytic geometry, Lecture Notes in Mathematics, Vol. 538, Springer-Verlag, Berlin-New York, 1976. · Zbl 0343.32002
[11] 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. · Zbl 0409.65026 · doi:10.1007/BF01582106
[12] Gene H. Golub , Studies in numerical analysis, MAA Studies in Mathematics, vol. 24, Mathematical Association of America, Washington, DC, 1984.
[13] I. M. Gel\(^{\prime}\)fand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1994. · Zbl 0827.14036
[14] Nicholas J. Higham, Accuracy and stability of numerical algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. · Zbl 0847.65010
[15] M. A. Hitz and E. Kaltofen, Efficient algorithms for computing the nearest polynomial with constrained roots, ISAAC , ACM Press, 1998, pp. 236-243. CMP 2001:07 · Zbl 0917.65045
[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 , ACM Press, 1999, pp. 205-212.
[17] 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. · Zbl 0762.14001
[18] 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. · Zbl 0886.65054 · doi:10.1017/S0962492900002749
[19] Dinesh Manocha and John F. Canny, Multipolynomial resultant algorithms, J. Symbolic Comput. 15 (1993), no. 2, 99 – 122. · Zbl 0778.13023 · doi:10.1006/jsco.1993.1009
[20] Hideyuki Matsumura, Commutative algebra, 2nd ed., Mathematics Lecture Note Series, vol. 56, Benjamin/Cummings Publishing Co., Inc., Reading, Mass., 1980. · Zbl 0441.13001
[21] Bruce Randall Donald, Deepak Kapur, and Joseph L. Mundy , Symbolic and numerical computation for artificial intelligence, Computational Mathematics and Applications, Academic Press, Ltd., London, 1992. · Zbl 0811.68053
[22] Ronald G. Mosier, Root neighborhoods of a polynomial, Math. Comp. 47 (1986), no. 175, 265 – 273. · Zbl 0598.65023
[23] B. Mourrain and H. Prieto, A framework for symbolic and numeric computations, INRIA, Rapport de recherche 4013 (2000).
[24] David Mumford, The red book of varieties and schemes, Lecture Notes in Mathematics, vol. 1358, Springer-Verlag, Berlin, 1988. · Zbl 0658.14001
[25] Arnold Neumaier, Interval methods for systems of equations, Encyclopedia of Mathematics and its Applications, vol. 37, Cambridge University Press, Cambridge, 1990. · Zbl 0715.65030
[26] 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. · Zbl 0133.08603 · doi:10.1007/BF01386090
[27] H. J. Stetter, The nearest polynomial with a given zero, and similar problems, SIGSAM Bull. 33 (1999), no. 4, 2-4. · Zbl 1097.65524
[28] Hans J. Stetter, Polynomials with coefficients of limited accuracy, Computer algebra in scientific computing — CASC’99 (Munich), Springer, Berlin, 1999, pp. 409 – 430. · Zbl 1072.65509
[29] -, Condition analysis of overdetermined algebraic problems, Computer algebra in scientific computing, CASC 2000 , Springer, 2000, pp. 345-365. · Zbl 0976.65050
[30] G. W. Stewart, Afternotes goes to graduate school, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. Lectures on advanced numerical analysis. · Zbl 0898.65001
[31] Kim-Chuan Toh and Lloyd N. Trefethen, Pseudozeros of polynomials and pseudospectra of companion matrices, Numer. Math. 68 (1994), no. 3, 403 – 425. · Zbl 0808.65053 · doi:10.1007/s002110050069
[32] J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. · Zbl 1041.65502
[33] H. Zhang, Numerical condition of polynomials in different forms, Electronic Transactions on Numerical Analysis 12 (2001), 66-87. · Zbl 0974.65046
[34] Walter Zulehner, A simple homotopy method for determining all isolated solutions to polynomial systems, Math. Comp. 50 (1988), no. 181, 167 – 177. · Zbl 0637.65045
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.