Positive Definite, Hermitian Matrix (Linear System)

From Algorithm Wiki
Revision as of 14:41, 15 February 2023 by Admin (talk | contribs)
Jump to navigation Jump to search

Description

In this case, we restrict $A$ to be positive definite and hermitian (or symmetric, if $A$ is real-valued).

Related Problems

Generalizations: General Linear System

Related: Sparse Linear System, Non-Definite, Symmetric Matrix, Toeplitz Matrix, Vandermonde Matrix

Parameters

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
Cholesky 1940 $O(n^{3})$ $O(n^{2})$ Exact Deterministic

Time Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Time-Space Tradeoff

Error creating thumbnail: Unable to save thumbnail to destination