Boman; Chen; Hendrickson; Toledo (Inexact Laplacian Solver SDD Systems Solvers)
Jump to navigation
Jump to search
Time Complexity
$O(n \log({1}/ϵ)$ )
Space Complexity
$O(n)$ words
(Derived: The preconditioners used have $O(n)$ non-zero entries)
Description
Maximum-weight-basis (MWB) preconditioners
Approximate?
Approximate
Approximation Factor: \epsilon
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
2004
Reference
https://onlinelibrary-wiley-com.ezproxy.canberra.edu.au/doi/abs/10.1002/nla.343