{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T09:19:34Z","timestamp":1777367974047,"version":"3.51.4"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,3,10]],"date-time":"2020-03-10T00:00:00Z","timestamp":1583798400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,3,10]],"date-time":"2020-03-10T00:00:00Z","timestamp":1583798400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002666","name":"Aalto University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002666","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose a new approach to the theory of conditioning for numerical analysis problems for which both classical and stochastic perturbation theories fail to predict the observed accuracy of computed solutions. To motivate our ideas, we present examples of problems that are discontinuous at a given input and even have infinite stochastic condition number, but where the solution is still computed to machine precision without relying on structured algorithms. Stimulated by the failure of classical and stochastic perturbation theory in capturing such phenomena, we define and analyse a weak worst-case and a weak stochastic condition number. This new theory is a more powerful predictor of the accuracy of computations than existing tools, especially when the worst-case and the expected sensitivity of a problem to perturbations of the input is not finite. We apply our analysis to the computation of simple eigenvalues of matrix polynomials, including the more difficult case of singular matrix polynomials. In addition, we show how the weak condition numbers can be estimated in practice.<\/jats:p>","DOI":"10.1007\/s10208-020-09455-y","type":"journal-article","created":{"date-parts":[[2020,3,10]],"date-time":"2020-03-10T20:02:43Z","timestamp":1583870563000},"page":"1439-1473","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Wilkinson\u2019s Bus: Weak Condition Numbers, with an Application to Singular Polynomial Eigenproblems"],"prefix":"10.1007","volume":"20","author":[{"given":"Martin","family":"Lotz","sequence":"first","affiliation":[]},{"given":"Vanni","family":"Noferini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,3,10]]},"reference":[{"issue":"9","key":"9455_CR1","doi-asserted-by":"publisher","first-page":"2193","DOI":"10.1016\/j.laa.2011.04.020","volume":"435","author":"B Adhikari","year":"2011","unstructured":"B.\u00a0Adhikari, R.\u00a0Alam, and D.\u00a0Kressner. Structured eigenvalue condition numbers and linearizations for matrix polynomials. Linear algebra and its applications, 435(9):2193\u20132221, 2011.","journal-title":"Linear algebra and its applications"},{"issue":"2","key":"9455_CR2","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1137\/17M1153236","volume":"40","author":"R Alam","year":"2019","unstructured":"R.\u00a0Alam and S.\u00a0Safique Ahmad. Sensitivity analysis of nonlinear eigenproblems. SIAM Journal on Matrix Analysis and Applications, 40(2):672\u2013695, 2019.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"9455_CR3","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/j.jco.2016.12.002","volume":"41","author":"D Amelunxen","year":"2017","unstructured":"D.\u00a0Amelunxen and M.\u00a0Lotz. Average-case complexity without the black swans. Journal of Complexity, 41:82\u2013101, 2017.","journal-title":"Journal of Complexity"},{"issue":"2","key":"9455_CR4","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/j.jco.2010.01.003","volume":"26","author":"D Armentano","year":"2010","unstructured":"D.\u00a0Armentano. Stochastic perturbations and smooth condition numbers. Journal of Complexity, 26(2):161\u2013171, 2010.","journal-title":"Journal of Complexity"},{"issue":"1","key":"9455_CR5","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1137\/17M1139941","volume":"40","author":"D Armentano","year":"2019","unstructured":"D.\u00a0Armentano and C.\u00a0Beltr\u00e1n. The polynomial eigenvalue problem is well conditioned for random inputs. SIAM Journal on Matrix Analysis and Applications, 40(1):175\u2013193, 2019.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"9455_CR6","first-page":"1","volume":"31","author":"K Ball","year":"1997","unstructured":"K.\u00a0Ball. An elementary introduction to modern convex geometry. Flavors of geometry, 31:1\u201358, 1997.","journal-title":"Flavors of geometry"},{"key":"9455_CR7","doi-asserted-by":"crossref","unstructured":"K.\u00a0Beltr\u00e1n, C.and\u00a0Kozhasov. The real polynomial eigenvalue problem is well conditioned on the average. Foundations of Computational Mathematics, May 2019.","DOI":"10.1007\/s10208-019-09414-2"},{"key":"9455_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and Real Computation","author":"L Blum","year":"1998","unstructured":"L.\u00a0Blum, F.\u00a0Cucker, M.\u00a0Schub, and S.\u00a0Smale. Complexity and Real Computation. Springer-Verlag, New York, NY, USA, 1998."},{"key":"9455_CR9","first-page":"403","volume":"5","author":"L Boltzmann","year":"1881","unstructured":"L.\u00a0Boltzmann. Referat \u00fcber die Abhandlung von J.C. Maxwell: \u201c\u00dcber Boltzmann\u2019s Theorem betreffend die mittlere Verteilung der lebendige Kraft in einem System materieller Punkte\u201d. Wied. Ann. Beibl\u00e4tter, 5:403\u2013417, 1881.","journal-title":"Wied. Ann. Beibl\u00e4tter"},{"key":"9455_CR10","unstructured":"F.\u00a0Bornemann. Private communication, 2018."},{"key":"9455_CR11","doi-asserted-by":"crossref","unstructured":"S.\u00a0Boucheron, G.\u00a0Lugosi, and P.\u00a0Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"9455_CR12","unstructured":"P.\u00a0B\u00fcrgisser. Smoothed analysis of condition numbers. In Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II\u2013IV: Invited Lectures, pages 2609\u20132633. World Scientific, 2010."},{"key":"9455_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38896-5","volume-title":"Condition. The Geometry of Numerical Algorithms","author":"P B\u00fcrgisser","year":"2013","unstructured":"P.\u00a0B\u00fcrgisser and F.\u00a0Cucker. Condition.The Geometry of Numerical Algorihtms. Springer, Berlin-Heidelberg, Germany, 2013."},{"issue":"4","key":"9455_CR14","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1016\/j.laa.2009.10.003","volume":"432","author":"F De Ter\u00e1n","year":"2010","unstructured":"F.\u00a0De\u00a0Ter\u00e1n and F.\u00a0M. Dopico. First order spectral perturbation theory of square singular matrix polynomials. Linear Algebra and its Applications, 432(4):892\u2013910, 2010.","journal-title":"Linear Algebra and its Applications"},{"issue":"1\u20133","key":"9455_CR15","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0024-3795(01)00423-2","volume":"358","author":"J-P Dedieu","year":"2003","unstructured":"J.-P. Dedieu and F.\u00a0Tisseur. Perturbation theory for homogeneous polynomial eigenvalue problems. Linear algebra and its applications, 358(1-3):71\u201394, 2003.","journal-title":"Linear algebra and its applications"},{"key":"9455_CR16","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01400115","volume":"51","author":"J Demmel","year":"1987","unstructured":"J.\u00a0Demmel. On condition numbers and the distance to the nearest ill-posed problem. Numer. Math., 51:251\u2013289, 1987.","journal-title":"Numer. Math."},{"key":"9455_CR17","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1090\/S0025-5718-1988-0929546-7","volume":"50","author":"J Demmel","year":"1988","unstructured":"J.\u00a0Demmel. The probability that a numerical analysis problem is difficult. Math. Comp., 50:449\u2013480, 1988.","journal-title":"Math. Comp."},{"key":"9455_CR18","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/j.laa.2017.09.007","volume":"535","author":"A Dmytryshyn","year":"2017","unstructured":"A.\u00a0Dmytryshyn and F.\u00a0M. Dopico. Generic complete eigenstructures for sets of matrix polynomials with bounded rank and degree. Linear Algebra and its Applications, 535:213\u2013230, 2017.","journal-title":"Linear Algebra and its Applications"},{"key":"9455_CR19","unstructured":"F.\u00a0Dopico and V.\u00a0Noferini. Root polynomials and their role in the theory of matrix polynomials. Submitted to Linear Algebra Appl., 2018."},{"issue":"6","key":"9455_CR20","doi-asserted-by":"publisher","first-page":"1199","DOI":"10.1063\/1.1703863","volume":"3","author":"FJ Dyson","year":"1962","unstructured":"F.\u00a0J. Dyson. The threefold way. algebraic structure of symmetry groups and ensembles in quantum mechanics. Journal of Mathematical Physics, 3(6):1199\u20131215, 1962.","journal-title":"Journal of Mathematical Physics"},{"key":"9455_CR21","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1137\/0609045","volume":"9","author":"A Edelman","year":"1988","unstructured":"A.\u00a0Edelman. Eigenvalues and condition numbers of random matrices. SIAM J. of Matrix Anal. and Applic., 9:543\u2013556, 1988.","journal-title":"SIAM J. of Matrix Anal. and Applic."},{"key":"9455_CR22","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1017\/S0962492904000236","volume":"14","author":"A Edelman","year":"2005","unstructured":"A.\u00a0Edelman and N.\u00a0R. Rao. Random matrix theory. Acta Numerica, 14:233\u2013297, 2005.","journal-title":"Acta Numerica"},{"key":"9455_CR23","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1137\/0313029","volume":"13","author":"G Forney Jr","year":"1975","unstructured":"G.\u00a0Forney\u00a0Jr. Minimal bases of rational vector spaces, with applications to multivariable linear systems. SIAM J. Control, 13:493\u2013520, 1975.","journal-title":"SIAM J. Control"},{"key":"9455_CR24","doi-asserted-by":"crossref","unstructured":"P.\u00a0J. Forrester. Log-gases and random matrices (LMS-34). Princeton University Press, 2010.","DOI":"10.1515\/9781400835416"},{"issue":"3","key":"9455_CR25","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1063\/1.1704292","volume":"6","author":"J Ginibre","year":"1965","unstructured":"J.\u00a0Ginibre. Statistical ensembles of complex, quaternion, and real matrices. Journal of Mathematical Physics, 6(3):440\u2013449, 1965.","journal-title":"Journal of Mathematical Physics"},{"key":"9455_CR26","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719024","volume-title":"Matrix Polynomials","author":"I Gohberg","year":"2009","unstructured":"I.\u00a0Gohberg, P.\u00a0Lancaster, and L.\u00a0Rodman. Matrix Polynomials. SIAM, Philadelphia, USA, 2009."},{"issue":"2","key":"9455_CR27","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1090\/S0002-9939-1951-0041539-X","volume":"2","author":"HH Goldstine","year":"1951","unstructured":"H.\u00a0H. Goldstine and J.\u00a0Von\u00a0Neumann. Numerical inverting of matrices of high order. II. Proceedings of the American Mathematical Society, 2(2):188\u2013202, 1951.","journal-title":"Proceedings of the American Mathematical Society"},{"issue":"4","key":"9455_CR28","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1137\/1018113","volume":"18","author":"GH Golub","year":"1976","unstructured":"G.\u00a0H. Golub and J.\u00a0H. Wilkinson. Ill-conditioned eigensystems and the computation of the jordan canonical form. SIAM Rev., 18(4):578\u2013619, 1976.","journal-title":"SIAM Rev."},{"key":"9455_CR29","volume-title":"Accuracy and stability of numerical algorithms","author":"NJ Higham","year":"1996","unstructured":"N.\u00a0J. Higham. Accuracy and stability of numerical algorithms. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, USA, 1996."},{"key":"9455_CR30","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717778","volume-title":"Functions of Matrices: Theory and Computation","author":"NJ Higham","year":"2008","unstructured":"N.\u00a0J. Higham. Functions of Matrices: Theory and Computation. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008."},{"key":"9455_CR31","unstructured":"N.\u00a0J. Higham and T.\u00a0Mary. A new approach to probabilistic rounding error analysis. 2018."},{"key":"9455_CR32","unstructured":"M.\u00a0Hochstenbach, C.\u00a0Mehl, and B.\u00a0Plestenjak. Solving singular generalized eigenvalue problems by a rank-completing perturbation. Preprint 03-2018, TU Berlin, Berlin, 2018."},{"key":"9455_CR33","unstructured":"M.\u00a0Konstantinov, D.\u00a0W. Gu, V.\u00a0Mehrmann, and P.\u00a0Petkov. Perturbation theory for matrix equations, volume\u00a09. Gulf Professional Publishing, 2003."},{"issue":"2\u20133","key":"9455_CR34","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0377-0427(88)90402-5","volume":"22","author":"E Kostlan","year":"1988","unstructured":"E.\u00a0Kostlan. Complexity theory of numerical linear algebra. Journal of Computational and Applied Mathematics, 22(2-3):219\u2013230, 1988.","journal-title":"Journal of Computational and Applied Mathematics"},{"issue":"5","key":"9455_CR35","first-page":"592","volume":"54","author":"F Mezzadri","year":"2007","unstructured":"F.\u00a0Mezzadri. How to generate random matrices from the classical compact groups. Notices of the American Mathematical Society, 54(5):592 \u2013 604, 5 2007.","journal-title":"Notices of the American Mathematical Society"},{"issue":"2","key":"9455_CR36","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1137\/0710024","volume":"10","author":"CB Moler","year":"1973","unstructured":"C.\u00a0B. Moler and G.\u00a0W. Stewart. An algorithm for generalized matrix eigenvalue problems. SIAM J. Numer. Anal., 10(2):241\u2013256, 1973.","journal-title":"SIAM J. Numer. Anal."},{"key":"9455_CR37","first-page":"607","volume":"22","author":"V Noferini","year":"2012","unstructured":"V.\u00a0Noferini. The behaviour of the complete eigenstructure of a polynomial matrix under a generic rational transformation. Electr. J. Lin. Algebra, 22:607\u2013624, 2012.","journal-title":"Electr. J. Lin. Algebra"},{"key":"9455_CR38","unstructured":"J.\u00a0W. Pearson. Computation of hypergeometric functions. Master\u2019s thesis, Oxford University, 2009."},{"issue":"3","key":"9455_CR39","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1007\/s11075-016-0173-0","volume":"74","author":"JW Pearson","year":"2017","unstructured":"J.\u00a0W. Pearson, S.\u00a0Olver, and M.\u00a0A. Porter. Numerical methods for the computation of the confluent and gauss hypergeometric functions. Numerical Algorithms, 74(3):821\u2013866, 2017.","journal-title":"Numerical Algorithms"},{"issue":"1","key":"9455_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1981-14858-8","volume":"4","author":"S Smale","year":"1981","unstructured":"S.\u00a0Smale. The fundamental theorem of algebra and complexity theory. Bulletin of the American Mathematical Society, 4(1):1\u201336, 1981.","journal-title":"Bulletin of the American Mathematical Society"},{"issue":"4","key":"9455_CR41","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1137\/1032121","volume":"32","author":"GW Stewart","year":"1990","unstructured":"G.\u00a0W. Stewart. Stochastic perturbation theory. SIAM review, 32(4):579\u2013610, 1990.","journal-title":"SIAM review"},{"issue":"1\u20133","key":"9455_CR42","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/S0024-3795(99)00063-4","volume":"309","author":"F Tisseur","year":"2000","unstructured":"F.\u00a0Tisseur. Backward error and condition of polynomial eigenvalue problems. Linear Algebra and its Applications, 309(1-3):339\u2013361, 2000.","journal-title":"Linear Algebra and its Applications"},{"issue":"9","key":"9455_CR43","first-page":"1","volume":"45","author":"LN Trefethen","year":"2012","unstructured":"L.\u00a0N. Trefethen. The smart money\u2019s on numerical analysts. SIAM News, 45(9):1\u20135, 2012.","journal-title":"SIAM News"},{"key":"9455_CR44","doi-asserted-by":"crossref","unstructured":"L.\u00a0N. Trefethen and D.\u00a0Bau. Numerical Linear Algebra. SIAM, 1997.","DOI":"10.1137\/1.9780898719574"},{"key":"9455_CR45","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1093\/qjmam\/1.1.287","volume":"1","author":"A Turing","year":"1948","unstructured":"A.\u00a0Turing. Rounding-off errors in matrix processes. Quart. J. Mech. Appl. Math., 1:287\u2013308, 1948.","journal-title":"Quart. J. Mech. Appl. Math."},{"key":"9455_CR46","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0024-3795(79)90035-1","volume":"27","author":"P Van Dooren","year":"1979","unstructured":"P.\u00a0Van\u00a0Dooren. The computation of Kronecker\u2019s canonical form of a singular pencil. Linear Algebra and its Applications, 27:103\u2013140, 1979.","journal-title":"Linear Algebra and its Applications"},{"key":"9455_CR47","doi-asserted-by":"publisher","first-page":"1021","DOI":"10.1090\/S0002-9904-1947-08909-6","volume":"53","author":"J von Neumann","year":"1947","unstructured":"J.\u00a0von Neumann and H.\u00a0Goldstine. Numerical inverting matrices of high order. Bulleting of the AMS, 53:1021\u20131099, 1947.","journal-title":"Bulleting of the AMS"},{"key":"9455_CR48","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0024-3795(86)90266-1","volume":"83","author":"N Weiss","year":"1986","unstructured":"N.\u00a0Weiss, G.\u00a0Wasilkowski, H.\u00a0Wo\u017aniakowski, and M.\u00a0Shub. Average condition number for solving linear equations. Linear Algebra and Its Applications, 83:79\u2013102, 1986.","journal-title":"Linear Algebra and Its Applications"},{"issue":"9","key":"9455_CR49","doi-asserted-by":"publisher","first-page":"563","DOI":"10.2307\/2304460","volume":"55","author":"JG Wendel","year":"1948","unstructured":"J.\u00a0G. Wendel. Note on the gamma function. The American Mathematical Monthly, 55(9):563\u2013564, 1948.","journal-title":"The American Mathematical Monthly"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-020-09455-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-020-09455-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-020-09455-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,10]],"date-time":"2021-03-10T00:31:13Z","timestamp":1615336273000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-020-09455-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,10]]},"references-count":49,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["9455"],"URL":"https:\/\/doi.org\/10.1007\/s10208-020-09455-y","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,10]]},"assertion":[{"value":"28 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}