The Department of Applied Mathematics weekly seminar is given by scholars and researchers working in applied mathematics, broadly interpreted.
Title: Local growth behavior of Gaussian elimination with partial and complete pivoting
Abstract: 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 small Gaussian perturbations. 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.