IMA Postdoc Seminar (November 17, 2009)

Speaker: Maki, Kara (IMA)

Title: Experimental determination of the likelihood of catastrophic instability in Gaussian elimination.

Abstract: The growth factor of a matrix quantifies the amount of potential error growth when a linear system is solved by Gaussian elimination with partial pivoting. While the growth factor has a maximum of $2^{n-1}$ for an $n \times n$ matrix, experience suggests the occurrence of matrices with exponentially large growth factors is extremely rare. To add computational evidence, we implemented a multicanonical Monte Carlo method to explore the tails of growth factor probability distributions for random matrices. .