Gauss-Jordan Exclusion vs. LU Decomposition

Question

The Black Book presents the 3rd edition of Numerical Recipes, the Gauss-Jordan algorithm for solving a system of linear equations. Immediately after this, this is the section devoted to calculating the LU decomposition and then to using this solution for solving a system of linear equations (see LUdcmp :: solve on page 53). Unfortunately, the book does not explain why someone prefers one method to another. Are these two approaches equivalent or are there reasons to prefer one method to another for a particular situation?

Answer 1

The advantages of using LU decomposition are that it can be reused to compute multiple solutions.

For example, if you want to solve the equation

Ax = b 

for constant A and many different b , then you only need to calculate the decomposition of LU A once, and it can be reused for each b . However, with the elimination of the Gauss-Jordan, you will have to redo all the work for each b

The reason this happens faster is because the Gaussian-Jordanian exception scales as O (n ^ 3), but the substitution step of the LU decomposition method only scales as O (n ^ 2). Therefore, for the LU case, you only need to perform one step O (n ^ 3) for each b .

A reasonable set of notes on this subject can be found here.

Answer 2

In fact, Gauss-Jordan is much faster than LU. Make some C code and you won’t understand, because you will use less code and less for loops in Gauss-Jordan than LU.