10 ms·
Limits on Matrix Multiplication
- deleted 8y ago[deleted]
- salty_biscuits 8y agoI hope it is 2. That would be surprising.
- dan-robertson 8y agoI’m not sure it would be surprising if it’s 2. Many people believe it is 2, or at least can be less than 2+epsilon for any epsilon > 0. I would however be impressed if it were constructively proven to be 2
- coherentpony 8y agoAnd the constant wasn't so huge as to be impractical.
- utopcell 8y agoThey show that it has to be strictly greater than 2.
- marcelluspye 8y agoThey showed the current methods couldn't bring it to 2. There could be another approach which gets it lower.
- std_throwaway 8y agoIt seems that not very many mathematicians are working on optimizing this problem but matrix multiplication used every day by many people and companies. Did we already exhaust economics of scale on this one?
- dan-robertson 8y agoWell most matrix multiplications tend to be small matrices (eg 4x4) and the time complexity of multiplying 4x4 matrices is O(1). These are actively optimised in the practical, hand-written assembly and new hardware, sense. If one has to multiply very large matrices then the goal is usually not so much to optimise matrix multiplication in general but to optimise the multiplication of the subset of matrices one is interested in. In these situations one cares about eg density and symmetry and choice of basis. There is a lot of information in a large random matrix and there is typically less information in an interesting large matrix. Therefore the goal is to skip the work required by all the entropy one does not have
- goldenkey 8y agoExtremely good explanation. But even regular matrixes are thought to be multiplyable at O(n^2). Right now we are a little higher than that, I think O(n^2.2). It's crazy that we can't find min complexity algorithm yet. The low complexity will be due to symmetries in pure uncorrelated matrixes.. which is clearly symmetry in multiplication itself or just numbers themselves. Someone will eventually find it.
- dan-robertson 8y agoIt’s about O(n^2.37). The entire article is about this number.
- deleted 8y ago[deleted]
- taeric 8y agoThis is no longer there case, given deep learning, though. Right? Effectively, the training process can be seen as a giant matrix multiplication in one step.
- jules 8y agoFully connected layers are matrix-vector multiplication (which turns into matrix-matrix if you do an entire batch at once). Convolutional layers are lots of tiny dot products. You can rewrite that as matrix-matrix multiplication.
- foxes 8y agoWhat is the connection with the continued fraction?
- deleted 8y ago[deleted]
- deleted 8y ago[deleted]
- kibwen 8y agoThe OP's WordPress install appears to be infected with malicious adware; every time I load the site I get quickly redirected to a random one of a number of scummy pages which hijack the back button, have autoplaying sound, display false error messages, and attempt to ask for browser-level permissions.
- ronsor 8y agoIt's hosted on WordPress.com -- it isn't hacked, they just serve scummy hijacking ads on user's blogs
- fermienrico 8y agoWhy does the Ad industry suck so much? Put some nicely formatted text such as Google ad results and clearly mention it as an ad. WHY the fuck do ad companies have to do insanely annoying borderline unethical things? Why is this industry so rotten to the core?
- nabla9 8y agoBecause suckers who are not using not adblockers are the only market segment for these ads. In this time and age, every computer literate person install adblocking in every system or asks someone to help to do it and almost nevers sees these ads. What is left is people who are more likely to fall for scams.
- costrouc 8y agoI didn't see in the paper why these methods are not used in practice. There are parallel implementations of strassens algorithm out there (I have written one). Yes they are faster but they do not guarantee stability. Also they are significantly harder to parallelize than block cyclic MM.
- throwawaymath 8y ago> There are parallel implementations of strassens algorithm out there Do you have one off the top of your head you could link the code too? Doesn't have to be your implementation specifically. I just want to read the code for a parallel implementation.
- jhanschoo 8y agoParallel Strassens sounds like just a log2 n sequence of map-reduce jobs