View source for Lemke–Howson Algorithm

== Algorithm Details ==
Year : -150

Family : [[SDD Systems Solvers]]

Authors : Carl Friedrich Gauss

Paper Link : NA

Time Complexity :

== Problem Statement ==

In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used to compute the rank of a matrix, the determinant of a square matrix, and the inverse of an invertible matrix. 

== PseudoCode == 
 1 h := 1 /* Initialization of the pivot row */
 2 k := 1 /* Initialization of the pivot column */
 3 
 4 while h ≤ m and k ≤ n:
 5     /* Find the k-th pivot: */
 6     i_max := argmax (i = h ... m, abs(A[i, k]))
 7     if A[i_max, k] = 0
 8         /* No pivot in this column, pass to next column */
 9         k := k+1
 10     else
 11          swap rows(h, i_max)
 12          /* Do for all rows below pivot: */
 13          for i = h + 1 ... m:
 14              f := A[i, k] / A[h, k]
 15              /* Fill with zeros the lower part of pivot column: */
 16              A[i, k] := 0
 17              /* Do for all remaining elements in current row: */
 18              for j = k + 1 ... n:
 19                  A[i, j] := A[i, j] - A[h, j] * f
 20          /* Increase pivot row and column */
 21          h := h + 1
 22          k := k + 1

== Applications ==

Gaussian-elimination-based algorithm for mesh-connected processors

Scheduling Algorithms for Parallel Gaussian Elimination

Recover Generator Polynomials of Convolutional Codes


== Implementations ==

Python : https://gist.github.com/j9ac9k/6b5cd12aa9d2e5aa861f942b786293b4

C++ Library : https://github.com/nomemory/neat-matrix-library