Re:Dijkstra’s algorithm and the Fibonacci heap
by jjoonathan on Sunday July 06, 2014 @07:33AM
(#7994275)
Are those matrices dense? It's an important qualifier. My corner of the computational world (finite-element related code) very frequently gets to millions of rows and columns but with only O(N) nonzero entries (where N is #rows which is approximately #cols too).
Matrices can be everything between dense and extremely sparse, depending on the application (sometimes you have a structured matrix and can use sparse methods to reduce it to a dense system of much smaller size). But yes, dense matrices with thousands of rows do occur. The applications where Strassen's asymptotically fast multiplication algorithm really helps are certainly rare compared to overall uses of linear algebra, but they do "strictly" exist.
Strassen multiplication usually starts to win over classical multiplication already for matrices with a few hundred rows (in special circumstances, it is even superior for 2x2 matrices). The Coppersmith–Winograd algorithm, on the other hand, is probably "strictly of theoretical interest" for the time being...
Re:Dijkstra’s algorithm and the Fibonacci heap
by techas on Sunday July 06, 2014 @10:25PM
(#7996691)
Spectral methods [1] are FE-like methods with non-zero basis functions over the whole domain. Indeed they produce full matrices.
[1] http://en.wikipedia.org/wiki/Spectral_method
Re:Dijkstra’s algorithm and the Fibonacci heap
by ajtulloch on Monday July 07, 2014 @12:17AM
(#7997055)
For a simple application in finance, consider a portfolio with n stocks. Then finding various statistics around
- expected portfolio mean & variance
- optimizing mean-variance subject to a risk budget (following Markowitz portfolio theory), etc.
would all entail operating on the n×n covariance matrix, which is typically dense. If your universe is the Russell 1000, S&P 500, etc, then n will be significantly larger than 250.
Re:Dijkstra’s algorithm and the Fibonacci heap
by taeric on Sunday July 06, 2014 @09:47AM
(#7994507)
I actually just recently read that section. Was curious how accurate it was. Was also curious if I could take a stab at implementing one of the algorithms he touches on.
And yes, I was thinking that it was the "sparse" nature of typical large matrices that makes them impractical.
(250 is peanut-sized in cryptography, number theory or computer algebra, and asymptotically fast matrix multiplication is very much useful in practice in those domains.)