# Gauss-Jordan using stacks and list

I have a homework assignment in which I need to write an implementation of Gauss-Jordan with complete pivoting. Complete pivoting is a modification to the basic Gauss-Jordan algorithm in which rows and columns are swapped around pivots. This is done to minimize the numerical errors by avoiding operations with small floating-point values.

A common approach would be to use for loops for swapping rows, but it would cost $O(n)$ operations to move a row and $O(n)$ to move a column. Using stack and list could be faster.

So the question is, how can stacks and lists be used in an implementation of Gauss-Jordan to efficiently swap columns in a matrix $A$?

I can change rows using pointers, but I can't realize how to use those structures to move columns and do Gauss-Jordan.

EDIT: Sorry i was to tired when create this question, as i'm not from a english speaker native country, i made some mistakes. The questions is about swapping columns using lists and stack. I'm really sorry, i wasted almost week thinking about it.

What you want is called indirection. Instead of physically moving the rows/columns, you move their names.

Let's say I call row 1 r[0], and row 3 r[2], in a matrix A, which has size n by n. Initially, the rows are exactly as I call them, so we initialize r[i] = i for all i < n.

Now I want to swap the third (r[2]) and the fifth row (r[4]). I could move the elements in matrix A, but this would require n swaps. Instead, I can just swap r[2] and r[4]! This is just swapping one integer.

The tradeoff is that now we must read matrix A as A[r[i]][c[j]] (where c is the equivalent of r, but for columns) instead of A[i][j]. This is a bit slower.

Agree with orlp's answer, which correctly discusses the complete pivoting asked about in the question. This answer shows a common variant, partial pivoting, which only swaps rows (and not columns). This approach is often more efficient, but complete pivoting can offer more reliable results.

### The problem

The mathematical method that you're referring to, i.e. pivoting in Gauss-Jordan elimination, requires swapping rows in a matrix.

Naively, rows can be swapped by swapping each of their values one-at-a-time:

// Swap rows 1 and 3
int row_0 = 1;
int row_1 = 3;

for (int i=0; i < rowLength; ++i)
{
var temp = matrix[row_0, i];
matrix[row_0, i] = matrix[row_1, i];
matrix[row_1, i] = temp;
}


This gets you from

matrix[,] = {  1    2    3    4
5    6    7    8
9   10   11   12
13   14   15   16  }


to

matrix[,] = {  1    2    3    4
13   14   15   16
9   10   11   12
5    6    7    8 }


But, as you've said, that requires looping over each element in the rows to swap them, and you want something more efficient.

### The solution: Indirection

Instead of using a multi-dimensional array like matrix[,], you can use an array-of-arrays (also called a jagged array) like matrix[][].

row_0[] =   {  1    2    3    4  }
row_1[] =   {  5    6    7    8  }
row_2[] =   {  9   10   11   12  }
row_3[] =   { 13   14   15   16  }

matrix[] =  {        row_0
row_1
row_2
row_3       }


You can still access the array in pretty much the same manner as before; the notation just changes slightly:

//  Before, with multi-dimensional array:
matrix[2, 3]  == 7

//  After, with array-of-arrays:
matrix[2][3]  == 7


However swapping rows is a lot easier since you have an array that's literally just a collection of row indices. By swapping those row indices, you effectively swap those rows.

// Swap rows 1 and 3
int row_0 = 1;
int row_1 = 3;

var temp = matrix[row_0];
matrix[row_0] = matrix[row_1];
matrix[row_1] = temp;


This gives you the same switch without having to loop over each element in the row.

row_0[] =   {  1    2    3    4  }
row_1[] =   {  5    6    7    8  }
row_2[] =   {  9   10   11   12  }
row_3[] =   { 13   14   15   16  }

matrix[] =  {        row_0
row_3
row_2
row_1       }


### Performance

This change from a multi-dimensional array to array-of-arrays has a few effects on performance and implementation:

• Memory allocation:

• Multi-dimensional arrays are often allocated as one block of memory.

• Array-of-arrays can allocate $1$ block of memory for the array-of-arrays, then $n_{\text{rows}}$ for each subordinate array, for a total of $n_{\text{rows}}+1$ memory blocks.

• Row-swap operations:

• Multi-dimensional arrays can't just swap rows; the operation must be performed member-wise.

• Array-of-arrays can swap rows, as shown above.