ALKO

Gaussian Elimination with Partial Pivoting

Overview

Gaussian elimination with partial pivoting (GEPP) is an algorithm used to solve systems of linear equations.

Visualization

22
11
00
44
33
11
22
11
33
A
x=x =
44
66
88
b
Input size n=3n=3:
22
11
00
44
33
11
22
11
33
AA
x=x =
44
66
88
bb
Step 0/30

Pseudocode

Algorithm Gaussian Elimination with Partial Pivoting
1:
procedure GEPP(A,b)(A, b)
2:
for i←1 to ni\gets 1\text{ to }n do
3:
ARGMAXk(A(k,i))\underset{k}{\textbf{\scriptsize ARGMAX}}(A_{(k, i)})
4:
if k≠ik\ne i then
5:
SWAP(Ai,Ak)\textbf{\scriptsize SWAP}(A_{i}, A_{k})
6:
SWAP(bi,bk)\textbf{\scriptsize SWAP}(b_{i}, b_{k})
7:
for j←i+1 to nj\gets i+1\text{ to }n do
8:
m  ←A(j,i)A(i,i)m\; \gets \frac{A_{(j, i)}}{A_{(i, i)}}
9:
Aj←Aj−mAiA_{j} \gets A_{j} - mA_{i}
10:
bj  ←bj−mbib_{j}\,\, \gets b_{j} - mb_{i}
11:
for i←n to 1i\gets n\text{ to }1 do
12:
for j←i−1 to 1j\gets i-1\text{ to }1 do
13:
m  ←A(j,i)A(i,i)m\; \gets \frac{A_{(j, i)}}{A_{(i, i)}}
14:
Aj←Aj−mAiA_{j} \gets A_{j} - m A_{i}
15:
bj  ←bj−mbib_{j}\,\, \gets b_{j} - m b_{i}
16:
for i←1 to ni\gets 1\text{ to }n do
17:
m        ←1A(i,i)m\;\;\;\; \gets \frac{1}{A_{(i, i)}}
18:
A(i,i)←mA(i,i)A_{(i, i)} \gets mA_{(i,i)}
19:
bi         ←mbib_{i}\;\;\;\;\, \gets mb_{i}

Time Complexity

The worst case for insertion sort is an array that is sorted in reverse order (ie. [3,2,1][3, 2, 1]). In this case, the algorithm will have to make 1+2+…+n−1=n(n−1)2=O(n2)1 + 2 + \ldots + n-1 = \frac{n(n-1)}{2} = O(n^2) comparisons and swaps.