Non-Definite, Symmetric Matrix (Linear System)

From Algorithm Wiki
Jump to navigation Jump to search


In this case, we restrict $A$ to be non-definite and symmetric.

Related Problems

Generalizations: General Linear System

Related: Sparse Linear System, Positive Definite, Hermitian Matrix, Toeplitz Matrix, Vandermonde Matrix


$n$: number of variables and number of equations

$m$: number of nonzero entries in matrix

$k$: ratio between largest and smallest eigenvalues

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Gaussian-Jordan Elimination -150 $O(n^{3})$ $O(n^{2})$ Exact Deterministic
Aasen's method 1971 $O(n^{3})$ $O(n^{2})$ total Exact Deterministic Time

Time Complexity Graph

Linear System - Non-Definite, Symmetric Matrix - Time.png