Timeline for efficient way to compute the inversion of the following matrix
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 22, 2011 at 2:24 | comment | added | Brian Borchers | Strassen's algorithm (and other similar "faster than O(n^3)" algorithms simply haven't proven to be useful in practice, even for fairly large (e.g. 10000 by 10000 matrix times 10000 by 10000 matrix) matrix-matrix multiplies. This is mostly because memory bandwidth and access times rather than flops are the real driving factor in matrix multiplication times. In this case, you'd definitely want to take advantage of the sparsity of X in doing the matrix multiplications. | |
| Mar 22, 2011 at 0:32 | comment | added | Vít Tuček | Matrix multiplication can be done faster than $O(n^3)$ even for dense matrices; for example there are implementations of Strassen multiplication faster than naive one for $n>200$. On the other hand, you're multiplying (possibly) dense matrix by a sparse matrix. So there may be faster multiplication algorithm still. | |
| Mar 21, 2011 at 14:09 | history | answered | Brian Borchers | CC BY-SA 2.5 |