# Tag Info

Accepted

• 1,324

### Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix

I know this is a really old question, but it seems like this recent paper https://arxiv.org/abs/1912.08805 improves the runtime to $O(n^\omega)$, down from $O(n^3)$.
• 136
Accepted

### What is the computational complexity of sin and cos for floating point inputs?

$\def\tc{\mathrm{TC}^0}\DeclareMathOperator\len{len}$Since there were no other takers, let me expand the comments above. The fundamental fact here is that approximations of basic arithmetic operations,...
• 14.7k

### Cost of Numerically Solving a System of P polynomials, each of V variables, and degree D to a Specific Accuracy

If the coefficients are roots of rational numbers, then they are in particular algebraic numbers. This means that you can encode the coefficients as additional polynomial constraints. So overall, you'...
• 5,246

• 23.5k
1 vote

### Multiple independent random number streams

It was already mentioned that it is important to use independent streams. Which is not guaranteed if you, e.g., use the naive approach of just seeding each of your PRNG with a different number. ...
1 vote

### Complexity of Finding the Eigendecomposition of a Matrix

See the intro of https://arxiv.org/abs/1912.08805 for a discussion of the literature around this problem. In short: O(n^3) has been known for symmetric matrices since the 60's, but was not known in ...
1 vote

### Complexity of Finding the Eigendecomposition of a Matrix

This is an old question but some important literature seems to have been missed. There are algorithms for which we have stronger theoretical support. For example, there are iterations based on the ...

Only top scored, non community-wiki answers of a minimum length are eligible