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.
Added later: Implementation details
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.