PA=LU decomposition (w/ Partial Pivoting)

[sid9221]

I'm have a little trouble understanding PA=LU, I have no problems with A=LU but can't seem to figure out the Permutation matrix.

So I have summarised the process I am using let me know where it can be improved.

Step 1: Using Gaussian Elimination with partial pivoting reduce A to form a matrix U.

Step 2: The matrix L is formed by the "negative of the row reduction multiples" eg: R2=R2-(3/4)R3 then -(3/4) is an element in the the matrix L.

Now here is the first problem, as with the A=LU decomposition do these multiples remain fixed in place or do they also permute around depending on row interchanges ?

eg: say R2=R2-(3/4)R3 is the first operation than (-3/4) should go in the position of Row 2, Column 1. But, later if I need to interchange R2 with say R4 (for partial pivoting) will this effect the position of (-3/4) in the matrix L ?

Step 3: Now that you have matrix L and U, form the matrix P with the row interchanges during the process of pivoting.

For example: If during pivoting R1<->R4 and R4<->R3 than

\begin{bmatrix}<br /> 1 &amp; 0 &amp; 0 &amp; 0\\ <br /> 0 &amp; 1 &amp; 0 &amp; 0\\ <br /> 0 &amp; 0 &amp; 1 &amp; 0\\ <br /> 0 &amp; 0 &amp; 0 &amp; 1<br /> \end{bmatrix}

becomes(R1<->R4)

\begin{bmatrix}<br /> 0&amp; 0 &amp; 0 &amp; 1\\ <br /> 0 &amp; 1 &amp; 0 &amp; 0\\ <br /> 0 &amp; 0 &amp; 1 &amp; 0\\ <br /> 1 &amp; 0 &amp; 0 &amp; 0<br /> \end{bmatrix}

and finally (R4<->R3)

\begin{bmatrix}<br /> 0&amp; 0 &amp; 0 &amp; 1\\ <br /> 0 &amp; 1 &amp; 0 &amp; 0\\ <br /> 1 &amp; 0 &amp; 0 &amp; 0\\ <br /> 0 &amp; 0 &amp; 1 &amp; 0<br /> \end{bmatrix}

The lecture notes I have are extremely complicated and involve L inverse theory which makes my head hurt and I can't find any useful resources online.

 

[AlephZero]

Conceptually this is straighforward. You decide how to permute all the rows of the matrix somehow, then you do the row interchanges to form P and the matrix product PA, then you factorize PA.

In practice, you don't do it like that. You start by selecting the first row of the permuted matrix PA, then you do the first step of the LU decomposition to "eliminate" the first variable.

That gives you the first column of L, the first row of U, and a matrix A' of size n-1 that contains the "partly processed" numbers from A.

Next, you select the second row to process, based on the numbers in A'. You interchange the rows of A', and you also retrospectively interchange the same rows in the first column of L. You don't do anything to the first row of U.

You then eliminate the second variable, giving the first 2 columns of L, the first 2 rows of U, and a matrix A''of size n-2.

Then you select the third row, and retrospectively permute the first 2 columns of L, and so on.