Department of Mathematics,
University of California San Diego
****************************
Math 278B: Mathematics of Information, Data, and Signals
John Peca-Medlin
UCSD
Global and local growth behavior of GEPP and GECP
Abstract:
Gaussian elimination (GE) remains one of the most used dense linear solvers. In the error analysis of GE with selected pivoting strategies on well-conditioned systems, the analysis can be reduced to studying the behavior of the growth factor, which represents the largest entry encountered at each step of the elimination process. 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 very recently 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 and upper bounds on worst-case GECP growth provided by Bisain, Edelman, and Urschel in the last 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.
March 14, 2025
11:00 AM
APM 2402
Research Areas
Mathematics of Information, Data, and Signals****************************