Positive Definite, Hermitian Matrix (Linear System)

From Algorithm Wiki
Revision as of 10:18, 15 February 2023 by Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Positive Definite, Hermitian Matrix (Linear System)}} == 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 == <pre>n: number of variables and number of equations m: number of nonzero e...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
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

Pareto Decades graph

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