# Gaussian Elimination

## 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