Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices

Title: Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices

Research Question: How likely is it for a slight random perturbation of a matrix to have large condition numbers or large growth factors under Gaussian elimination without pivoting?

Methodology: The authors use smoothed analysis, a hybrid of worst-case and average-case analyses, to measure the maximum over inputs of the expected value of a measure of the performance of an algorithm on slight random perturbations of that input. They specifically focus on Gaussian elimination without pivoting.

Results: They prove that it is unlikely for a perturbation of an arbitrary matrix to have large condition numbers or large growth factors. This leads to the conclusion that the smoothed precision necessary for Gaussian elimination is logarithmic. They also obtain similar results for perturbations that affect only the non-zero and diagonal entries of symmetric matrices.

Implications: These results provide a smoothed analysis of Gaussian elimination without pivoting, which is a widely used algorithm in practice despite having poor worst-case performance. This could potentially improve the understanding and performance of this algorithm in real-world scenarios. The results also suggest further research directions and provide counter-examples to help refine the methodology.

Link to Article: https://arxiv.org/abs/0310022v4 Authors: arXiv ID: 0310022v4