{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T16:13:06Z","timestamp":1776787986282,"version":"3.51.2"},"reference-count":46,"publisher":"American Mathematical Society (AMS)","issue":"263","license":[{"start":{"date-parts":[[2009,1,30]],"date-time":"2009-01-30T00:00:00Z","timestamp":1233273600000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    We prove a general theorem providing smoothed analysis estimates for conic condition numbers of problems of numerical analysis. Our probability estimates depend only on geometric invariants of the corresponding sets of ill-posed inputs. Several applications to linear and polynomial equation solving show that the estimates obtained in this way are easy to derive and quite accurate. The main theorem is based on a volume estimate of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"epsilon\">\n                        <mml:semantics>\n                          <mml:mi>\n                            \u03b5\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\varepsilon<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -tubular neighborhoods around a real algebraic subvariety of a sphere, intersected with a spherical disk of radius\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"sigma\">\n                        <mml:semantics>\n                          <mml:mi>\n                            \u03c3\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\sigma<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . Besides\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"epsilon\">\n                        <mml:semantics>\n                          <mml:mi>\n                            \u03b5\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\varepsilon<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    and\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"sigma\">\n                        <mml:semantics>\n                          <mml:mi>\n                            \u03c3\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\sigma<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , this bound depends only on the dimension of the sphere and on the degree of the defining equations.\n                  <\/p>","DOI":"10.1090\/s0025-5718-08-02060-7","type":"journal-article","created":{"date-parts":[[2008,4,22]],"date-time":"2008-04-22T17:24:54Z","timestamp":1208885094000},"page":"1559-1583","source":"Crossref","is-referenced-by-count":27,"title":["The probability that a slightly perturbed numerical analysis problem is difficult"],"prefix":"10.1090","volume":"77","author":[{"given":"Peter","family":"B\u00fcrgisser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felipe","family":"Cucker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Lotz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2008,1,30]]},"reference":[{"issue":"1","key":"1","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s10208-005-0176-2","article-title":"Estimates on the distribution of the condition number of singular matrices","volume":"7","author":"Beltr\u00e1n, C.","year":"2007","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"key":"2","series-title":"CMS Books in Mathematics\/Ouvrages de Math\\'{e}matiques de la SMC","isbn-type":"print","volume-title":"Generalized inverses","volume":"15","author":"Ben-Israel, Adi","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/0387002936","edition":"2"},{"key":"3","isbn-type":"print","first-page":"1","article-title":"Lectures on a theory of computation and complexity over the reals (or an arbitrary ring)","author":"Blum, Lenore","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0201509369"},{"key":"4","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and real computation","author":"Blum, Lenore","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/0387982817"},{"key":"5","series-title":"Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03718-8","volume-title":"Real algebraic geometry","volume":"36","author":"Bochnak, Jacek","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/3540646639"},{"issue":"2","key":"6","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.crma.2006.05.014","article-title":"General formulas for the smoothed analysis of condition numbers","volume":"343","author":"B\u00fcrgisser, Peter","year":"2006","journal-title":"C. R. Math. Acad. Sci. Paris","ISSN":"https:\/\/id.crossref.org\/issn\/1631-073X","issn-type":"print"},{"issue":"4","key":"7","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.matpur.2006.06.001","article-title":"Smoothed analysis of complex conic condition numbers","volume":"86","author":"B\u00fcrgisser, Peter","year":"2006","journal-title":"J. Math. Pures Appl. (9)","ISSN":"https:\/\/id.crossref.org\/issn\/0021-7824","issn-type":"print"},{"key":"8","unstructured":"S.L. Campbell and C.D. Meyer. Generalized Inverse of Linear Transformations. Pitman, 1979."},{"key":"9","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1512\/iumj.1967.16.16006","article-title":"On the kinematic formula in integral geometry","volume":"16","author":"Chern, Shiing-shen","year":"1966","journal-title":"J. Math. Mech."},{"issue":"3","key":"10","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/j.jco.2004.06.004","article-title":"A note on level-2 condition numbers","volume":"21","author":"Cheung, Dennis","year":"2005","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"1","key":"11","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1002\/nla.464","article-title":"Smoothed analysis of some condition numbers","volume":"13","author":"Cucker, F.","year":"2006","journal-title":"Numer. Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1070-5325","issn-type":"print"},{"issue":"3","key":"12","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01400115","article-title":"On condition numbers and the distance to the nearest ill-posed problem","volume":"51","author":"Demmel, James Weldon","year":"1987","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"182","key":"13","doi-asserted-by":"publisher","first-page":"449","DOI":"10.2307\/2008617","article-title":"The probability that a numerical analysis problem is difficult","volume":"50","author":"Demmel, James W.","year":"1988","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"14","unstructured":"J. Dunagan, D.A. Spielman, and S.-H. Teng. Smoothed analysis of Renegar\u2019s condition number for linear programming. Preprint available at \\url{http:\/\/theory.lcs.mit.edu\/ spielman}, 2003."},{"key":"15","doi-asserted-by":"crossref","unstructured":"C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika, 1:211\u2013218, 1936.","DOI":"10.1007\/BF02288367"},{"key":"16","series-title":"Johns Hopkins Series in the Mathematical Sciences","isbn-type":"print","volume-title":"Matrix computations","volume":"3","author":"Golub, Gene H.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0801837723","edition":"2"},{"key":"17","isbn-type":"print","volume-title":"Tubes","author":"Gray, Alfred","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0201156768"},{"issue":"509","key":"18","doi-asserted-by":"publisher","first-page":"vi+69","DOI":"10.1090\/memo\/0509","article-title":"The kinematic formula in Riemannian homogeneous spaces","volume":"106","author":"Howard, Ralph","year":"1993","journal-title":"Mem. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-9266","issn-type":"print"},{"key":"19","isbn-type":"print","first-page":"419","article-title":"On the distribution of roots of random polynomials","author":"Kostlan, E.","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/0387979328"},{"key":"20","doi-asserted-by":"publisher","first-page":"275","DOI":"10.2307\/2034050","article-title":"On the Betti numbers of real varieties","volume":"15","author":"Milnor, J.","year":"1964","journal-title":"Proc. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9939","issn-type":"print"},{"issue":"1","key":"21","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1287\/moor.12.1.121","article-title":"On the efficiency of Newton\u2019s method in approximating all zeros of a system of complex polynomials","volume":"12","author":"Renegar, J.","year":"1987","journal-title":"Math. Oper. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/0364-765X","issn-type":"print"},{"key":"22","series-title":"Encyclopedia of Mathematics and its Applications, Vol. 1","volume-title":"Integral geometry and geometric probability","author":"Santal\u00f3, Luis A.","year":"1976"},{"key":"23","series-title":"Die Grundlehren der mathematischen Wissenschaften, Band 213","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-96200-4","volume-title":"Basic algebraic geometry","author":"Shafarevich, I. R.","year":"1974"},{"issue":"2","key":"24","doi-asserted-by":"publisher","first-page":"459","DOI":"10.2307\/2152805","article-title":"Complexity of B\u00e9zout\u2019s theorem. I. Geometric aspects","volume":"6","author":"Shub, Michael","year":"1993","journal-title":"J. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0894-0347","issn-type":"print"},{"key":"25","isbn-type":"print","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-1-4612-2752-6_19","article-title":"Complexity of Bezout\u2019s theorem. II. Volumes and probabilities","author":"Shub, M.","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/0817636781"},{"issue":"1","key":"26","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1006\/jcom.1993.1002","article-title":"Complexity of Bezout\u2019s theorem. III. Condition number and packing","volume":"9","author":"Shub, Michael","year":"1993","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"1","key":"27","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(94)90122-8","article-title":"Complexity of Bezout\u2019s theorem. V. Polynomial time","volume":"133","author":"Shub, M.","year":"1994","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"issue":"1","key":"28","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1137\/0733008","article-title":"Complexity of Bezout\u2019s theorem. IV. Probability of success; extensions","volume":"33","author":"Shub, Michael","year":"1996","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"1","key":"29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1981-14858-8","article-title":"The fundamental theorem of algebra and complexity theory","volume":"4","author":"Smale, Steve","year":"1981","journal-title":"Bull. Amer. Math. Soc. (N.S.)","ISSN":"https:\/\/id.crossref.org\/issn\/0273-0979","issn-type":"print"},{"key":"30","isbn-type":"print","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1017\/S0962492900002774","article-title":"Complexity theory and numerical analysis","author":"Smale, Steve","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/0521591066"},{"key":"31","isbn-type":"print","first-page":"597","article-title":"Smoothed analysis of algorithms","author":"Spielman, Daniel A.","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/7040086905"},{"issue":"1-2","key":"32","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s10107-003-0448-9","article-title":"Smoothed analysis of termination of linear programming algorithms","volume":"97","author":"Spielman, Daniel A.","year":"2003","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"issue":"3","key":"33","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","article-title":"Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time","volume":"51","author":"Spielman, Daniel A.","year":"2004","journal-title":"J. ACM","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"key":"34","isbn-type":"print","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1017\/CBO9780511721571.010","article-title":"Smoothed analysis of algorithms and heuristics: progress and open questions","author":"Spielman, Daniel A.","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521681612"},{"key":"35","unstructured":"M. Spivak. A comprehensive introduction to differential geometry. Vol. I. Publish or Perish Inc., Wilmington, Del., second edition, 1979."},{"key":"36","unstructured":"M. Spivak. A comprehensive introduction to differential geometry. Vol. III. Publish or Perish Inc., Wilmington, Del., second edition, 1979."},{"key":"37","series-title":"Computer Science and Scientific Computing","isbn-type":"print","volume-title":"Matrix perturbation theory","author":"Stewart, G. W.","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0126702306"},{"key":"38","series-title":"Lehrb\\\"{u}cher und Monographien aus dem Gebiete der Exakten Wissenschaften, Mathematische Reihe, Band 48","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-5949-3","volume-title":"Differentialgeometrie und Faserb\\\"{u}ndel","author":"Sulanke, R.","year":"1972"},{"key":"39","series-title":"Undergraduate Texts in Mathematics","isbn-type":"print","volume-title":"Elementary topics in differential geometry","author":"Thorpe, John A.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0387903577"},{"key":"40","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1093\/qjmam\/1.1.287","article-title":"Rounding-off errors in matrix processes","volume":"1","author":"Turing, A. M.","year":"1948","journal-title":"Quart. J. Mech. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0033-5614","issn-type":"print"},{"key":"41","doi-asserted-by":"publisher","first-page":"1021","DOI":"10.1090\/S0002-9904-1947-08909-6","article-title":"Numerical inverting of matrices of high order","volume":"53","author":"von Neumann, John","year":"1947","journal-title":"Bull. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9904","issn-type":"print"},{"issue":"2","key":"42","doi-asserted-by":"publisher","first-page":"461","DOI":"10.2307\/2371513","article-title":"On the Volume of Tubes","volume":"61","author":"Weyl, Hermann","year":"1939","journal-title":"Amer. J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9327","issn-type":"print"},{"key":"43","unstructured":"H. Weyl. The Theory of Groups and Quantum Mechanics. Dover, New York, 1950."},{"key":"44","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/BF01402528","article-title":"Note on matrices with a very ill-conditioned eigenproblem","volume":"19","author":"Wilkinson, J. H.","year":"1972","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"1","key":"45","doi-asserted-by":"crossref","first-page":"177","DOI":"10.2140\/pjm.1993.159.177","article-title":"Volumes of tubular neighbourhoods of real algebraic varieties","volume":"159","author":"Wongkew, Richard","year":"1993","journal-title":"Pacific J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0030-8730","issn-type":"print"},{"issue":"1","key":"46","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.jco.2003.09.003","article-title":"Smoothed analysis of \ud835\udf05(\ud835\udc34)","volume":"20","author":"Wschebor, Mario","year":"2004","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2008-77-263\/S0025-5718-08-02060-7\/S0025-5718-08-02060-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2008-77-263\/S0025-5718-08-02060-7\/S0025-5718-08-02060-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:22:10Z","timestamp":1776784930000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2008-77-263\/S0025-5718-08-02060-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,30]]},"references-count":46,"journal-issue":{"issue":"263","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["S0025-5718-08-02060-7"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-08-02060-7","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2008,1,30]]}}}