Join Zoom Meeting
https://nus-sg.zoom.us/j/6124909748?pwd=TDFJYitzZ3ZSeUZUcTBEWnhTZWtSUT09
Meeting ID: 612 490 9748
Passcode: 007151
Abstract: The Gaussian Elimination with Partial Pivoting (GEPP) is a classical algorithm for solving systems of linear equations. Although the worst-case loss of precision in GEPP due to roundoff errors is known to be very significant, empirical evidence suggests that for a typical coefficient matrix, GEPP is numerically stable. Until recently, this phenomenon has received little theoretical justification. We make a progress on this problem by showing that, given the random $n\times n$ standard Gaussian coefficient matrix, the {\it growth factor} of the Gaussian Elimination with Partial Pivoting is at most polynomially large in $n$ with probability close to one. This implies that with high probability the GEPP results only in logarithmic (in $n$) loss of bits of precision, which improves an earlier estimate of Sankar of order $O(\log^2 n)$. This is joint work with Han Huang.