4 ms·
Many problems require lots of huge matrix multiplications—think simulations of physical systems, i.e. weather systems or molecular interactions, or numerical op
by skosch 6y ago
Many problems require lots of huge matrix multiplications—think simulations of physical systems, i.e. weather systems or molecular interactions, or numerical optimization.
- TJSomething 6y agoAdditionally, many problems are can be converted to matrix operations, like graph algorithms. Note that matrix multiplication takes O(n^2) time with a quantum computer, but O(n^2.807) time on a classical computer.
- gnu-nobody 6y ago> but O(n^2.807) time on a classical computer Optimizing matrix multiplication for classical computers is an open research problem, and according to wikipedia there are algorithms with O(n^2.37) running time. Also according to wikipedia, it is not proven that matrix multiplication can't be done in O(n^2).
- infogulch 6y agoAh yes, we may as well add NP-completeness to this thread.