New answers tagged linear-algebra
1
vote
Accepted
Complexity of matrix diagonalization
Reducing to a tridiagonal matrix takes $O(n^3)$ independent of $\epsilon$. I believe the fastest algorithm after that is divide and conquer, which I believe is $O(n^2 \log(1/\epsilon))$, for a total ...
Top 50 recent answers are included
Related Tags
linear-algebra × 212ds.algorithms × 59
matrices × 51
cc.complexity-theory × 43
reference-request × 20
graph-theory × 15
linear-programming × 15
matrix-product × 15
optimization × 13
time-complexity × 12
co.combinatorics × 10
approximation-algorithms × 8
quantum-computing × 8
coding-theory × 8
computational-geometry × 8
spectral-graph-theory × 8
na.numerical-analysis × 8
np-hardness × 7
dc.parallel-comp × 7
sparse-matrix × 7
graph-algorithms × 6
circuit-complexity × 6
randomized-algorithms × 6
boolean-matrix × 6
finite-fields × 6