Analysis of eigenvalue condition numbers for a class of randomized numerical methods for singular matrix pencils

Area of Science:

• Numerical Analysis
• Linear Algebra
• Computational Mathematics

Background:

• Solving generalized eigenvalue problems with singular matrix pencils is numerically challenging due to discontinuous eigenvalues.
• Traditional methods involve extracting the regular part via staircase form before applying solvers like the QZ algorithm.
• Recent research explores randomized modifications to transform singular pencils into regular ones.

Purpose of the Study:

• To analyze three randomized methods (Hochstenbach, Mehl, Plestenjak) for transforming singular matrix pencils into regular ones.
• To evaluate the numerical stability and condition numbers of the transformed pencils.
• To compare the efficacy of real versus complex random matrices in these transformations.

Main Methods:

• Analysis of three randomized modification techniques: modification, projection, and augmentation.
• Utilizing normal rank to ensure finite eigenvalues are preserved.
• Comparison of eigenvalue condition numbers of transformed pencils with original $$-weak condition numbers.
• Investigation of the impact of real versus complex random matrices on numerical stability.

Main Results:

• The analyzed randomized methods transform singular pencils into regular ones without altering finite eigenvalues.
• Transformed pencils exhibit eigenvalue condition numbers comparable to the original $$-weak condition numbers, indicating favorable numerical stability.
• Complex random matrices are preferable for numerical stability, even with real pencils and eigenvalues.
• Sharp left tail bounds for products of generalized beta and Kumaraswamy distributed random variables were derived.

Conclusions:

• Randomized modifications offer a numerically stable alternative for solving generalized eigenvalue problems with singular matrix pencils.
• The $$-weak eigenvalue condition number is a reliable indicator for detecting simple finite eigenvalues.
• Employing complex random matrices improves the numerical stability of these methods for real-valued problems.