Toeplitz Matrix (Linear System)

From Algorithm Wiki
Jump to navigation Jump to search


In this case, we restrict $A$ to be a Toeplitz matrix.

Related Problems

Generalizations: General Linear System

Related: Sparse Linear System, Positive Definite, Hermitian Matrix, Non-Definite, Symmetric 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
Levinson–Durbin recursion 1947 $O(n^{2})$ $O(n^{2})$ total Exact Deterministic Time
Bareiss Algorithm 1969 $O(n^{2})$ $O(n^{2})$ total Exact Deterministic Time

Time Complexity Graph

Linear System - Toeplitz Matrix - Time.png