Gaussian Elimination with Pivoting is P-Complete
Stephen A. Vavasis · SIAM Journal on Discrete Mathematics · 1989
Gaussian elimination with partial pivoting is the standard numerical algorithm for solving unstructured linear systems. Here it is shown that Gaussian elimination with partial pivoting or complete pivoting is log-space complete for P. This provides theoretical evidence that these algorithms cannot be efficiently implemented on a highly parallel computer with a large number of processors. Since other algorithms for linear systems that are efficient on parallel computers are already known, this suggests that elimination-based approaches should not be pursued in a parallel environment with many processors.