What are the advantages of solving a system of linear equations with the LR algorithm? And why shouldn't I always use Gaussian elimination?

Question

I was recently introduced to the LR algorithm to solve systems of linear equations.

What I don't really get is, why this method of solving is more effective for different RHS (right hand sides) of equations than the normal Gaussian elimination?

Thanks in advance :)

Answer 1

Having computed $A = LR$ where $L$ is lower and $R$ is upper triangular, you can solve

$$ Ax = b \Leftrightarrow L(Rx) = b \Leftrightarrow \begin{cases} Ly &=& b \\ Rx &=& y \end{cases} $$

which is equivalent to solving two triangular systems. If $A$ is $n \times n$, the cost of computing the LR decomposition is $O(n^3)$ and the cost of computing the solution to $LRx = b$ is $O(n^2)$ since the systems involved are triangular.

If you have a sequence of systems of the form $A x = b^{(i)}$ for different right-hand sides $b^{(i)}$, then you can compute the LR factorization once for the first system and re-use it to solve subsequent linear systems in time $O(n^2)$ each. On the other hand, using Gauss elimination from scratch will take $O(n^3)$ time for each subsequent system.