LU Decomposition (LUD)

Input

An $n \times n$ matrix $A$ with entries over the rationals.

Problem

Find a numerically stable LU decomposition of $A$.

Status

Open (Greenlaw, Hoover and Ruzzo [2]).

Remarks

Vavasis shows that the LU decomposition arising from Gaussian elimination with partial pivoting is $\P$-complete [1], see GEPP. The problem here is to find another method for constructing a LU decomposition in $\NC$. This question is important because one often solves the same system of equations multiple times. Having the LU decomposition means the solution for different vectors can easily be obtained via back substitution.