Wilkinson's bus: weak condition numbers, with an application to singular polynomial eigenproblems

DOI10.1007/S10208-020-09455-YzbMATH Open1455.65056arXiv1905.05466OpenAlexW3011046458MaRDI QIDQ827005FDOQ827005

Vanni Noferini, Martin Lotz

Publication date: 6 January 2021

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Abstract: We propose a new approach to the theory of conditioning for numerical analysis problems for which both classical and stochastic perturbation theory 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 have infinite classical and 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.

Full work available at URL: https://arxiv.org/abs/1905.05466

Recommendations

• Singular quadratic eigenvalue problems: linearization and weak condition numbers
• On condition numbers of polynomial eigenvalue problems
• scientific article; zbMATH DE number 1210851
• The Probability That a Numerical Analysis Problem is Difficult
• A comparison of eigenvalue condition numbers for matrix polynomials

zbMATH Keywords

condition numberpolynomial eigenvalue problemsingular matrix polynomialstochastic perturbation theoryweak condition number

Mathematics Subject Classification ID

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

Cites Work

• Functions of Matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• How to generate random matrices from the classical compact groups
• Condition
• Minimal Bases of Rational Vector Spaces, with Applications to Multivariable Linear Systems
• Statistical Ensembles of Complex, Quaternion, and Real Matrices
• The Threefold Way. Algebraic Structure of Symmetry Groups and Ensembles in Quantum Mechanics
• The computation of Kronecker's canonical form of a singular pencil
• Eigenvalues and Condition Numbers of Random Matrices
• Title not available (Why is that?)
• Numerical Inverting of Matrices of High Order. II
• Title not available (Why is that?)
• Perturbation theory for homogeneous polynomial eigenvalue problems
• Backward error and condition of polynomial eigenvalue problems
• The fundamental theorem of algebra and complexity theory
• Ill-Conditioned Eigensystems and the Computation of the Jordan Canonical Form
• Title not available (Why is that?)
• Matrix Polynomials
• Numerical inverting of matrices of high order
• The Probability That a Numerical Analysis Problem is Difficult
• On condition numbers and the distance to the nearest ill-posed problem
• An Algorithm for Generalized Matrix Eigenvalue Problems
• ROUNDING-OFF ERRORS IN MATRIX PROCESSES
• The behavior of the complete eigenstructure of a polynomial matrix under a generic rational transformation
• Random matrix theory
• Perturbation theory for matrix equations
• Stochastic perturbations and smooth condition numbers
• Numerical methods for the computation of the confluent and Gauss hypergeometric functions
• Structured eigenvalue condition numbers and linearizations for matrix polynomials
• Complexity theory of numerical linear algebra
• Average-case complexity without the black swans
• Average condition number for solving linear equations
• The real polynomial eigenvalue problem is well conditioned on the average
• Root polynomials and their role in the theory of matrix polynomials
• Generic complete eigenstructures for sets of matrix polynomials with bounded rank and degree
• Title not available (Why is that?)
• The Polynomial Eigenvalue Problem is Well Conditioned for Random Inputs
• Stochastic Perturbation Theory
• Sensitivity Analysis of Nonlinear Eigenproblems
• Solving Singular Generalized Eigenvalue Problems by a Rank-Completing Perturbation
• A New Approach to Probabilistic Rounding Error Analysis
• First order spectral perturbation theory of square singular matrix polynomials

Cited In (13)

• On computing root polynomials and minimal bases of matrix pencils
• Solving Singular Generalized Eigenvalue Problems. Part II: Projection and Augmentation
• Analysis of eigenvalue condition numbers for a class of randomized numerical methods for singular matrix pencils
• The limit empirical spectral distribution of Gaussian monic complex matrix polynomials
• The \(\mathbb{DL}(P)\) vector space of pencils for singular matrix polynomials
• The limit empirical spectral distribution of complex matrix polynomials
• Invertible bases and root vectors for analytic matrix-valued functions
• A Riemannian optimization method to compute the nearest singular pencil
• Singular quadratic eigenvalue problems: linearization and weak condition numbers
• Title not available (Why is that?)
• A Theory of Quantum Subspace Diagonalization
• Root vectors of polynomial and rational matrices: theory and computation
• Randomized Joint Diagonalization of Symmetric Matrices

Uses Software

• mctoolbox
• mftoolbox

This page was built for publication: Wilkinson's bus: weak condition numbers, with an application to singular polynomial eigenproblems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q827005)