Difference between revisions of "Linear Equations"

From Algorithm Wiki
Jump to navigation Jump to search
 
Line 1: Line 1:
== Problem Description==
== Problem Description==
a system of linear equations (or linear system) is a collection of one or
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.
more linear equations involving the same set of variables.
 
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 ==
== Bounds Chart ==

Latest revision as of 13:43, 15 September 2021

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)