Global and Local growth behavior of Gaussian elimination with partial and complete pivoting
When
Where
Gaussian elimination (GE) remains one of the most used dense linear solvers. Error analysis of GE with selected pivoting strategies on well-conditioned systems can focus on studying the behavior of growth factors. Although exponential growth is possible with GE with partial pivoting (GEPP), growth tends to stay much smaller in practice. Support for this behavior was provided last year by Huang and Tikhomirov’s average-case analysis of GEPP, which showed GEPP growth stays at most polynomial with very high probability when using Gaussian matrices. Research on GE with complete pivoting (GECP) has also seen a lot of recent interest, with improvements to lower bounds on worst-case GECP growth provided by Edelman and Urschel earlier this year. I am interested in studying how GEPP and GECP behave on the same linear systems, with a focus on large growth systems and orthogonal matrices. One direction will explore when GECP is less stable than GEPP, which will lead to new empirical lower bounds on how much worse GECP can behave compared to GEPP in terms of growth. Another direction will include an empirical study on a family of exponential GEPP growth matrices whose polynomial behavior in small neighborhoods limits to the initial GECP growth factor.