Gaussian Elimination - Pseudocode

Pseudocode

As explained above, Gaussian elimination writes a given m × n matrix A uniquely as a product of an invertible m × m matrix S and a row-echelon matrix T. Here, S is the product of the matrices corresponding to the row operations performed.

The formal algorithm to compute from follows. We write for the entry in row, column in matrix with 1 being the first index. The transformation is performed "in place", meaning that the original matrix is lost and successively replaced by .

for k = 1 ... m: Find pivot for column k: i_max := argmax (i = k ... m, abs(A)) if A = 0 error "Matrix is singular!" swap rows(k, i_max) Do for all rows below pivot: for i = k + 1 ... m: Do for all remaining elements in current row: for j = k + 1 ... n: A := A - A * (A / A) Fill lower triangular matrix with zeros: A := 0

This algorithm differs slightly from the one discussed earlier, because before eliminating a variable, it first exchanges rows to move the entry with the largest absolute value to the "pivot position". Such "partial pivoting" improves the numerical stability of the algorithm (see also pivot element); some variants are also in use.

Upon completion of this procedure the augmented matrix will be in row-echelon form and may be solved by back-substitution.

With the increasing popularity of multi-core processors, programmers now exploit thread-level parallel Gaussian elimination algorithms to increase the speed of computing. The shared-memory programming model (as opposed to the message exchange model) pseudocode is listed below.

// Note this code sample has been mangled (missing attr init/scope? bad gauss indentation?)... // What is original source? Can we get valid C or else simplified pseudo code instead of this hybrid? void parallel(int num_threads,int matrix_dimension) { int i; for(i=0;ibarrier_mutex)); mybarrier->cur_count++; if(mybarrier->cur_count!=num_thread) pthread_cond_wait(&(mybarrier->barrier_cond),&(mybarrier->barrier_mutex)); else { mybarrier->cur_count=0; pthread_cond_broadcast(&(mybarrier->barrier_cond)); } pthread_mutex_unlock(&(mybarrier->barrier_mutex)); }