# LU factorization algorithm always fails.

I'm trying to implement LU factorization in openCL but I'm struggling to get my sequential algorithm working properly.

I implemented a sequential algorithm that works perfectly. Next I wanted to implement pivoting to enhance my precision. This is where I'm stuck. I can't figure out how to do it exactly. As a check for my calculations I use this website. From what I understand about pivoting is that each time you will swap rows such that the element with the biggest value in the pivot column is in the pivot position. Great.

So what I do in pseudocode for an $$M\times M$$ matrix, $$A$$ is the following:

for each pivot index: 0 -> M:
* Swap the current row with the row that has the biggest value in column M.
* Swap the same row indices in P.
* Calculate the new value for each element.
* Recur


So as an example I took this input matrix:

239.000000      522.000000      287.000000      615.000000
373.000000       70.000000      816.000000      646.000000
766.000000      940.000000      482.000000      397.000000
347.000000       45.000000      909.000000      594.000000


We can clearly see that we have to swap row 0 with row 2, which results in the following matrix:

766.000000      940.000000      482.000000      397.000000
373.000000       70.000000      816.000000      646.000000
239.000000      522.000000      287.000000      615.000000
347.000000       45.000000      909.000000      594.000000


Now, when we do 1 iteration of decomposition we get the following result:

766.000000      940.000000      482.000000      397.000000
0.000000     -387.728485      581.292419      452.682770
0.000000      228.710175      136.610962      491.131866
0.000000     -380.822449      690.652710      414.157959


Up to this point it matches with what the website gives me. So next iteration, we can see that row 2 now has the maximum value in the pivot column (228.710175) so we swap row 1 and 2, resulting in this matrix:

766.000000      940.000000      482.000000      397.000000
0.000000      228.710175      136.610962      491.131866
0.000000     -387.728485      581.292419      452.682770
0.000000     -380.822449      690.652710      414.157959


And this is where it goes wrong. When I look at the result on the website I see this matrix:

 766.000  940.000  482.000  397.000
0.000 -387.728  581.292  452.683
0.000    0.000  479.499  758.157
0.000    0.000    0.000 -219.747


It appears to be that they did not swap any rows in the second iteration. I have tried to test if PA = LU with my solution but it's wrong. Could anyone tell me what I am doing wrong?

• The pivot should be selected with the maximal absolute value. The point of pivoting is not to have positive diagonal elements in the $U$-factor, but the avoid dividing by small numbers in the absolute value which can lead to excessive magnitude growth of the entries in the $U$-factor. Oct 30, 2014 at 14:05