Knuth's DP 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