# LU decomposition with pivoting

I have to solve system of linear algebraic equations AX=B, where A is two-dimensional matrix and all elements of main diagonal are equal to zero.

How to solve this problem? Iterational methods are not applied in this case.

One way is LU Decomposition method with reordering rows of A to get entries in main diagonal are not zero using permutation matrix. How to quickly reorder rows of matrix or find permutation matrix?

Note that matrix is very big and I have to write programm to solve SLAE in C# language, so I do not need any matlab or mathematica functions. Thanks!

-
Not sure if this belongs here or over at cs.stackexchange.com... – tomasz Dec 25 '12 at 11:08
What do you mean with two-dimensional matrix? Normally one would interpret that as a $2\times2$ matrix, but this seems to contradict "matrix is very big". Do you just means that the matrix can be written in a two-dimensional layout? This is true for all matrices, so if you mean that just drop the phrase. – Marc van Leeuwen Dec 25 '12 at 11:58
@MarcvanLeeuwen It may be a misuse of terminology, as I have seen the term 'matrix' applied to higher dimensional arrays of data in the computational sciences. – Daryl Dec 25 '12 at 21:41
I mean usual two-dimensional matrix nxn, with n > 500000. like this 3.bp.blogspot.com/_264sc_gncA4/SiEOApq5oaI/AAAAAAAAAVE/… – Nurlan Dec 27 '12 at 8:15

Hint Use an array, p[] to hold the row permutations. The permutation vector

p =[ 3,2,1,4,5,6]


indicates that the row corresponding to row 1 of the permuted matrix is row 3 of the original matrix, and row 3 corresponds to row 1. I.e. row 1 and 3 have been swapped.

Then use p to index into the rows of your permuted matrix matrix A. i.e. if you want to update the i'th row, you would index as

A[p[i]][...] = ...


This effectifely swaps the two rows, with you only interchanging 2 numbers, rather than the entire two rows.

The same idea can be used for full pivotting, where the columns are permuted also.

Initially the p array is initialised as an unpermuted matrix, e.g.

p = [1,2,3,4,5,6];


If the algorithm then requires you to swap rows 1 and 3, interchange the row indices in positions 1 and 3. e.g.

p = [3,2,1,4,5,6];


If you then have to swap rows 2 and 3, interchange the row indices in positions 2 and 3. e.g.

p = [3,1,2,4,5,6];


The array p holds the indices into the rows of the matrix A. Instead of swapping the entire rows of A, by using p as a row index to A, you can swap entire rows with a single swap, rather than $n$ swaps which are required to swap the entire rows.

-
I asked about how to permute array rows, in your case how do you create permutation vector p = [3,2,1,4,5,6]? Why not p = [3,4,5,2,1,3] for example? – Nurlan Dec 27 '12 at 8:17
@NurlanKenzhebekov See my edit with implementation details. – Daryl Dec 27 '12 at 10:43