New answers tagged algebraic-complexity
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
algebraic-complexity × 83cc.complexity-theory × 47
arithmetic-circuits × 15
ds.algorithms × 14
polynomials × 13
permanent × 10
determinant × 10
algebra × 9
circuit-complexity × 8
reference-request × 7
lower-bounds × 5
nt.number-theory × 5
linear-algebra × 3
big-picture × 3
matrix-product × 3
graph-theory × 2
graph-algorithms × 2
co.combinatorics × 2
complexity-classes × 2
time-complexity × 2
cr.crypto-security × 2
matrices × 2
graph-isomorphism × 2
polynomial-time × 2
p-vs-np × 2