Gauss-Jordan using stacks and list

Question

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.

Answer 1

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.

Answer 2

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.

• Serialization, caching, and multi-threading:

  • If your matrix is huge, you might only need to work with part of it at a time, or part of it in different threads. An array-of-arrays allows you to access the relevant parts without serializing/loading/passing the entire thing.

A few bloggers have noted that arrays-of-arrays can be more performant in C#. This can be counter-intuitive as they're more general structures than multi-dimensional arrays, but apparently real-world implementations can have arrays-of-arrays be faster even when their extra functionality isn't used.