3 ms·
The phrase "nearly linear time" come from the paper. However, the paper gives a better definition: When we refer to a nearly linear time SDD system solver we
by LukeShu 14y ago
The phrase "nearly linear time" come from the paper.
However, the paper gives a better definition:
When we refer to a nearly linear time SDD system solver we mean an an
algorithm that computes such a x in time O(mlog^c(n)logε⁻¹)
where m is the number of nonzero entries in A and c ≥ 0 ∈ ℝ is a
fixed constant.
- _delirium 14y agoThe term "nearly linear time" is fine. The next part of that sentence is where the problem arises: it suggests that the opposite of "nearly linear", and the status quo, is that running time "increase[s] exponentially". But the existing standard algorithms already scale polynomially, not exponentially.