CODEWITHSUNDEEP
algorithmlinear-algebra
Tyler Durden
Tyler Durden

Reputation: 11562

Gauss-Jordan Elimination versus LU Decomposition

In the "black book", Numerical Recipes 3rd edition, the Gauss-Jordan algorithm for solving a system of linear equations is given. Directly afterwards is a section on computing an LU decomposition and then subsequently using that to solve a system of linear equations (see LUdcmp::solve on p. 53). Unfortunately, the book does not explain why one would prefer one method to another. Are the two approaches equivalent, or are there reasons to prefer one method to the other for particular situation?

Upvotes: 6

Views: 4063

Answers (2)

euraad
euraad

Reputation: 2856

In reality, Gauss-Jordan is much faster than LU. Do some C-code and you will undetstand because you will use less code and less for-loops in Gauss-Jordan than LU.

Upvotes: 1

Simon Gibbons
Simon Gibbons

Reputation: 7194

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

For example if you want to solve the equation

Ax = b

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

The reason this is faster is because Gauss-Jordan elimination 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 would only have to do the expensive O(n^3) step once for each b.

A reasonable set of notes on exactly this can be found here

Upvotes: 8

Related Questions