Linear Equations

From Algorithm Wiki
Revision as of 13:43, 15 September 2021 by Yashsherry (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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


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)