×

Wilkinson’s bus: weak condition numbers, with an application to singular polynomial eigenproblems. (English) Zbl 1455.65056

Summary: 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.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F35 Numerical computation of matrix norms, conditioning, scaling
15A18 Eigenvalues, singular values, and eigenvectors
15B52 Random matrices (algebraic aspects)
60H99 Stochastic analysis

Software:

mctoolbox; mftoolbox
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adhikari, B.; Alam, R.; Kressner, D., Structured eigenvalue condition numbers and linearizations for matrix polynomials, Linear algebra and its applications, 435, 9, 2193-2221 (2011) · Zbl 1225.65043
[2] Alam, R.; Safique Ahmad, S., Sensitivity analysis of nonlinear eigenproblems, SIAM Journal on Matrix Analysis and Applications, 40, 2, 672-695 (2019) · Zbl 1420.65042
[3] Amelunxen, D.; Lotz, M., Average-case complexity without the black swans, Journal of Complexity, 41, 82-101 (2017) · Zbl 1416.68081
[4] Armentano, D., Stochastic perturbations and smooth condition numbers, Journal of Complexity, 26, 2, 161-171 (2010) · Zbl 1269.15003
[5] Armentano, D.; Beltrán, C., The polynomial eigenvalue problem is well conditioned for random inputs, SIAM Journal on Matrix Analysis and Applications, 40, 1, 175-193 (2019) · Zbl 1409.65021
[6] Ball, K., An elementary introduction to modern convex geometry, Flavors of geometry, 31, 1-58 (1997) · Zbl 0901.52002
[7] K. Beltrán, C.and Kozhasov. The real polynomial eigenvalue problem is well conditioned on the average. Foundations of Computational Mathematics, May 2019. · Zbl 1472.14068
[8] Blum, L.; Cucker, F.; Schub, M.; Smale, S., Complexity and Real Computation (1998), New York, NY, USA: Springer-Verlag, New York, NY, USA
[9] Boltzmann, L., Referat über die Abhandlung von J.C. Maxwell: “Über Boltzmann’s Theorem betreffend die mittlere Verteilung der lebendige Kraft in einem System materieller Punkte”, Wied. Ann. Beiblätter, 5, 403-417 (1881)
[10] F. Bornemann. Private communication, 2018.
[11] S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013. · Zbl 1279.60005
[12] P. Bürgisser. 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-IV: Invited Lectures, pages 2609-2633. World Scientific, 2010. · Zbl 1231.65095
[13] Bürgisser, P.; Cucker, F., Condition. The Geometry of Numerical Algorithms (2013), Berlin-Heidelberg, Germany: Springer, Berlin-Heidelberg, Germany · Zbl 1280.65041
[14] De Terán, F.; Dopico, FM, First order spectral perturbation theory of square singular matrix polynomials, Linear Algebra and its Applications, 432, 4, 892-910 (2010) · Zbl 1187.15013
[15] Dedieu, J-P; Tisseur, F., Perturbation theory for homogeneous polynomial eigenvalue problems, Linear algebra and its applications, 358, 1-3, 71-94 (2003) · Zbl 1087.65033
[16] Demmel, J., On condition numbers and the distance to the nearest ill-posed problem, Numer. Math., 51, 251-289 (1987) · Zbl 0597.65036
[17] Demmel, J., The probability that a numerical analysis problem is difficult, Math. Comp., 50, 449-480 (1988) · Zbl 0657.65066
[18] Dmytryshyn, A.; Dopico, FM, Generic complete eigenstructures for sets of matrix polynomials with bounded rank and degree, Linear Algebra and its Applications, 535, 213-230 (2017) · Zbl 1375.15013
[19] F. Dopico and V. Noferini. Root polynomials and their role in the theory of matrix polynomials. Submitted to Linear Algebra Appl., 2018. · Zbl 1439.15004
[20] Dyson, FJ, The threefold way. algebraic structure of symmetry groups and ensembles in quantum mechanics, Journal of Mathematical Physics, 3, 6, 1199-1215 (1962) · Zbl 0134.45703
[21] Edelman, A., Eigenvalues and condition numbers of random matrices, SIAM J. of Matrix Anal. and Applic., 9, 543-556 (1988) · Zbl 0678.15019
[22] Edelman, A.; Rao, NR, Random matrix theory, Acta Numerica, 14, 233-297 (2005) · Zbl 1162.15014
[23] Forney, G. Jr, Minimal bases of rational vector spaces, with applications to multivariable linear systems, SIAM J. Control, 13, 493-520 (1975) · Zbl 0269.93011
[24] P. J. Forrester. Log-gases and random matrices (LMS-34). Princeton University Press, 2010. · Zbl 1217.82003
[25] Ginibre, J., Statistical ensembles of complex, quaternion, and real matrices, Journal of Mathematical Physics, 6, 3, 440-449 (1965) · Zbl 0127.39304
[26] Gohberg, I.; Lancaster, P.; Rodman, L., Matrix Polynomials (2009), Philadelphia, USA: SIAM, Philadelphia, USA · Zbl 1170.15300
[27] Goldstine, HH; Von Neumann, J., Numerical inverting of matrices of high order. II, Proceedings of the American Mathematical Society, 2, 2, 188-202 (1951) · Zbl 0043.12301
[28] Golub, GH; Wilkinson, JH, Ill-conditioned eigensystems and the computation of the jordan canonical form, SIAM Rev., 18, 4, 578-619 (1976) · Zbl 0341.65027
[29] Higham, NJ, Accuracy and stability of numerical algorithms (1996), USA: Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, USA · Zbl 0847.65010
[30] Higham, NJ, Functions of Matrices: Theory and Computation (2008), Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 1167.15001
[31] N. J. Higham and T. Mary. A new approach to probabilistic rounding error analysis. 2018. · Zbl 07123205
[32] M. Hochstenbach, C. Mehl, and B. Plestenjak. Solving singular generalized eigenvalue problems by a rank-completing perturbation. Preprint 03-2018, TU Berlin, Berlin, 2018. · Zbl 1435.65056
[33] M. Konstantinov, D. W. Gu, V. Mehrmann, and P. Petkov. Perturbation theory for matrix equations, volume 9. Gulf Professional Publishing, 2003. · Zbl 1025.15017
[34] Kostlan, E., Complexity theory of numerical linear algebra, Journal of Computational and Applied Mathematics, 22, 2-3, 219-230 (1988) · Zbl 0645.65019
[35] Mezzadri, F., How to generate random matrices from the classical compact groups, Notices of the American Mathematical Society, 54, 5, 592-604, 5 (2007) · Zbl 1156.22004
[36] Moler, CB; Stewart, GW, An algorithm for generalized matrix eigenvalue problems, SIAM J. Numer. Anal., 10, 2, 241-256 (1973) · Zbl 0253.65019
[37] Noferini, V., The behaviour of the complete eigenstructure of a polynomial matrix under a generic rational transformation, Electr. J. Lin. Algebra, 22, 607-624 (2012) · Zbl 1250.15014
[38] J. W. Pearson. Computation of hypergeometric functions. Master’s thesis, Oxford University, 2009.
[39] Pearson, JW; Olver, S.; Porter, MA, Numerical methods for the computation of the confluent and gauss hypergeometric functions, Numerical Algorithms, 74, 3, 821-866 (2017) · Zbl 1360.33009
[40] Smale, S., The fundamental theorem of algebra and complexity theory, Bulletin of the American Mathematical Society, 4, 1, 1-36 (1981) · Zbl 0456.12012
[41] Stewart, GW, Stochastic perturbation theory, SIAM review, 32, 4, 579-610 (1990) · Zbl 0722.15002
[42] Tisseur, F., Backward error and condition of polynomial eigenvalue problems, Linear Algebra and its Applications, 309, 1-3, 339-361 (2000) · Zbl 0955.65027
[43] Trefethen, LN, The smart money’s on numerical analysts, SIAM News, 45, 9, 1-5 (2012)
[44] L. N. Trefethen and D. Bau. Numerical Linear Algebra. SIAM, 1997. · Zbl 0874.65013
[45] Turing, A., Rounding-off errors in matrix processes, Quart. J. Mech. Appl. Math., 1, 287-308 (1948) · Zbl 0033.28501
[46] Van Dooren, P., The computation of Kronecker’s canonical form of a singular pencil, Linear Algebra and its Applications, 27, 103-140 (1979) · Zbl 0416.65026
[47] von Neumann, J.; Goldstine, H., Numerical inverting matrices of high order, Bulleting of the AMS, 53, 1021-1099 (1947) · Zbl 0031.31402
[48] Weiss, N.; Wasilkowski, G.; Woźniakowski, H.; Shub, M., Average condition number for solving linear equations, Linear Algebra and Its Applications, 83, 79-102 (1986) · Zbl 0603.65025
[49] Wendel, JG, Note on the gamma function, The American Mathematical Monthly, 55, 9, 563-564 (1948)
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.