Positive Definite, Hermitian Matrix: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(3 intermediate revisions by the same user not shown)
Line 12: Line 12:
== Parameters ==  
== Parameters ==  


n: number of variables and number of equations
$n$: number of variables and number of equations


m: number of nonzero entries in matrix
$m$: number of nonzero entries in matrix


k: ratio between largest and smallest eigenvalues
$k$: ratio between largest and smallest eigenvalues


== Table of Algorithms ==  
== Table of Algorithms ==  
Line 26: Line 26:
|-
|-


| [[Gaussian-Jordan Elimination (General Linear System; Positive Definite, Hermitian Matrix; Non-Definite, Symmetric Matrix; Toeplitz Matrix; Vandermonde Matrix Linear System)|Gaussian-Jordan Elimination]] || -150 || $O(n^{3})$ || $O(n^{2})$ || Exact || Deterministic || 
|-
| [[Cholesky (Positive Definite, Hermitian Matrix Linear System)|Cholesky]] || 1940 || $O(n^{3})$ || $O(n^{2})$ || Exact || Deterministic ||   
| [[Cholesky (Positive Definite, Hermitian Matrix Linear System)|Cholesky]] || 1940 || $O(n^{3})$ || $O(n^{2})$ || Exact || Deterministic ||   
|-
|-
|}
|}


== Time Complexity graph ==  
== Time Complexity Graph ==  


[[File:Linear System - Positive Definite, Hermitian Matrix - Time.png|1000px]]
[[File:Linear System - Positive Definite, Hermitian Matrix - Time.png|1000px]]


== Space Complexity graph ==  
== Space Complexity Graph ==  


[[File:Linear System - Positive Definite, Hermitian Matrix - Space.png|1000px]]
[[File:Linear System - Positive Definite, Hermitian Matrix - Space.png|1000px]]


== Pareto Decades graph ==  
== Time-Space Tradeoff ==  


[[File:Linear System - Positive Definite, Hermitian Matrix - Pareto Frontier.png|1000px]]
[[File:Linear System - Positive Definite, Hermitian Matrix - Pareto Frontier.png|1000px]]

Latest revision as of 08:18, 10 April 2023

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

Linear System - Positive Definite, Hermitian Matrix - Time.png

Space Complexity Graph

Linear System - Positive Definite, Hermitian Matrix - Space.png

Time-Space Tradeoff

Linear System - Positive Definite, Hermitian Matrix - Pareto Frontier.png