Linear Equations

From Algorithm Wiki
Jump to navigation Jump to search

Problem Description

A linear equation is an equation that is written for two different variables. This equation will be a linear combination of these two variables, and a constant can be present. Surprisingly, when any linear equation is plotted on a graph, it will necessarily produce a straight line - hence the name: Linear equations.

A linear equation can be written in different ways. Any simple equation in x and y can be termed as a linear equation if it follows a certain set of rules. For example, the highest (and the only) degree of both - x and y - variables in the equation should be 1. Other than that, constants (zero degree variables) can be there.

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)