A condition number theorem for underdetermined polynomial systems

Dégot, Jérôme

doi:10.1090/S0025-5718-00-00934-0

A condition number theorem for underdetermined polynomial systems
HTML articles powered by AMS MathViewer

by Jérôme Dégot PDF

Math. Comp. 70 (2001), 329-335 Request permission

Abstract:

The condition number of a numerical problem measures the sensitivity of the answer to small changes in the input. In their study of the complexity of Bézout’s theorem, M. Shub and S. Smale prove that the condition number of a polynomial system is equal to the inverse of the distance from this polynomial system to the nearest ill-conditioned one. Here we explain how this result can be extended to underdetermined systems of polynomials (that is with less equations than unknowns).

References

Bernard Beauzamy and Jérôme Dégot, Differential identities, Trans. Amer. Math. Soc. 347 (1995), no. 7, 2607–2619. MR 1277095, DOI 10.1090/S0002-9947-1995-1277095-1
Jean-Pierre Dedieu, Approximate solutions of numerical problems, condition number analysis and condition number theorem, The mathematics of numerical analysis (Park City, UT, 1995) Lectures in Appl. Math., vol. 32, Amer. Math. Soc., Providence, RI, 1996, pp. 263–283. MR 1421339, DOI 10.1007/bf02562881
James Weldon Demmel, On condition numbers and the distance to the nearest ill-posed problem, Numer. Math. 51 (1987), no. 3, 251–289. MR 895087, DOI 10.1007/BF01400115
C. Eckart, G. Young, The approximation of one matrix by another of lower rank, Psychometrika 1, (1936), pp 211-218.
Bruce Reznick, An inequality for products of polynomials, Proc. Amer. Math. Soc. 117 (1993), no. 4, 1063–1073. MR 1119265, DOI 10.1090/S0002-9939-1993-1119265-2
Michael Shub and Steve Smale, Complexity of Bézout’s theorem. I. Geometric aspects, J. Amer. Math. Soc. 6 (1993), no. 2, 459–501. MR 1175980, DOI 10.1090/S0894-0347-1993-1175980-4