Solving Ax=b; when to use LU decomposition?

  • #1

Main Question or Discussion Point

I want to solve the linear equation below:

[tex]Ax = b[/tex]


For this purpose, I'm writing a C++ code. I have written both routines for decomposing A matrix to L and U matrices, and for calculating inverse of A matrix.

I may multiply both sides with A-1:

[tex]Ax = b[/tex]
[tex]A^{-1}Ax = A^{-1}b[/tex]
[tex]x = A^{-1}b[/tex]

Or, I can use LU decomposition:

[tex]Ax = b[/tex]
[tex]A = LU[/tex]
[tex]Ax = LUx = Ly = b[/tex]
[tex]Solve\,\,\,\,\, Ly = b\,\,\,\,\, for\,\,\,\,\, y[/tex]
[tex]Solve\,\,\,\,\, Ux = y\,\,\,\,\, for\,\,\,\,\, x[/tex]


LU decomposition method is said to be faster. But, I'm not sure if these rumors are true for all cases. I have a feeling that the first method (matrix inversion method) would be faster for smaller A matrices.

My question is, how do I prefer which method to use?
 

Answers and Replies

  • #2
AlephZero
Science Advisor
Homework Helper
6,994
291
LU decomposition method is said to be faster. But, I'm not sure if these rumors are true for all cases.
It is faster for any matrix of order greater than 1x1. Well, to be fair, you can write special code for a 2x2 matrix, but the amount of computation is so tiny that it's hardly worth the bother, unless you need to solve 100 million sets of 2x2 equations (and there are numerical applications that DO need to do that sort of thing.)

For at least 999 algorithms out of 1000, finding the explicit inverse of a matrix is not the fastest way, though "beginners" are often tempted to just "translate" math equations containing an inverse matrices into a programming language.

Actually, a fast and reliable way to calculate the inverse of an NxN matrix is to first find the LU decomposition, and then solve N sets of equations where the "b" vectors have one 1 and the other terms all zero, to find the columns of the inverse matrix one at a time. That is already more work than solving one set of equations using LU decomposition.
 
  • #3
Thank you for your guidance. I will stick to LU decomposition.


Actually, a fast and reliable way to calculate the inverse of an NxN matrix is to first find the LU decomposition, and then solve N sets of equations where the "b" vectors have one 1 and the other terms all zero, to find the columns of the inverse matrix one at a time. That is already more work than solving one set of equations using LU decomposition.
This is an interesting information.
I didn't understand what b vector to choose for calculating the inverse of A. Can you please a b vector and explain the method to find the inverse of A matrix?
 
  • #4
I like Serena
Homework Helper
6,577
176
Did you consider how robust the algorithms are?
An important concern is usually to minimize the result of rounding errors.
This is especially important when the matrix is close to singular.
 
  • #5
SteamKing
Staff Emeritus
Science Advisor
Homework Helper
12,798
1,666
To calculate the inverse of matrix A (n x n), the b matrix is equal to the n x n Identity Matrix (only 1s on the main diagonal, all zeros elsewhere).
 
  • #6
To calculate the inverse of matrix A (n x n), the b matrix is equal to the n x n Identity Matrix (only 1s on the main diagonal, all zeros elsewhere).

In the Ax=b equation I'm working with, A is a square matrix, x and b are column vectors.

Like this:
lineq.png


So, how do I make the b vector an nxn identity matrix?
 
  • #7
HallsofIvy
Science Advisor
Homework Helper
41,805
932
solve N sets of equations where the "b" vectors have one 1 and the other terms all zero, to find the columns of the inverse matrix one at a time.
I didn't understand what b vector to choose for calculating the inverse of A. Can you please a b vector and explain the method to find the inverse of A matrix?
AlephZero told you that. For, say, a 4 by 4 matrix, use
[tex]\begin{bmatrix}1 \\ 0 \\ 0 \\ 0\end{bmatrix}[/tex], [tex]\begin{bmatrix}0 \\ 1 \\ 0 \\ 0\end{bmatrix}[/tex], [tex]\begin{bmatrix}0 \\ 0 \\ 1 \\ 0\end{bmatrix}[/tex], and [tex]\begin{bmatrix}0 \\ 0 \\ 0 \\ 1\end{bmatrix}[/tex]
 
  • #8
Hmm. I will substitute columns of the identity matrix for b vector for n times to find n different x vectors. Next, I will merge these x vectors to form the inverse of the A matrix. Did I understand it right?
 
  • #9
lurflurf
Homework Helper
2,426
126
^Yes that is right.
The LU decomposition is basically free, so even when it does not help it cannot hurt. Computing the inverse is best avoided if possible, both for speed and stability.
 

Related Threads on Solving Ax=b; when to use LU decomposition?

  • Last Post
Replies
1
Views
9K
  • Last Post
Replies
3
Views
2K
Replies
1
Views
4K
Replies
1
Views
795
  • Last Post
Replies
2
Views
3K
Replies
2
Views
1K
Replies
1
Views
851
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
8
Views
3K
Top