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

File:Linear system of equationsStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
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)

logn Harrow (Quantum) (2009)