Linear Equations

From Algorithm Wiki
Jump to navigation Jump to search

Problem Description

a system of linear equations (or linear system) is a collection of one or

more linear equations involving the same set of variables.

Bounds Chart

Linear system of equationsBoundsChart.png

Step Chart

350px

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic [Gaussian-Jordan Elimination (-150)]

[Cholesky (1940)]

Aasen's method (1971)

Quadratic Conjugate Gradient (1952)

Levinson–Durbin recursion (1947)

Bareiss Algorithm (1969)

Bjorck-Pereyra (1970)

nlogn
Linear
logn Harrow (Quantum) (2009)