7 ms·

It 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

It 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 ago
Well 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 ago
  Extremely 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 ago
    It’s about O(n^2.37). The entire article is about this number.
  - deleted 8y ago
    [deleted]
- taeric 8y ago
  This 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 ago
    Fully 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.
    - taeric 8y ago
      This was my thought. Am I correct in saying the batch size influences the size of the matrix? Or is there a more natural limiting factor?
      - jules 8y ago
        That's right. For a fully connected layer the matrix is of dimension (batch size) x (number of neurons in layer k) which gets multiplied by a matrix of dimension (number of neurons in layer k) x (number of neurons in layer k+1). People do this because going through the network with a batch is more efficient than going through the network separately for each element in the batch, mainly because multiplying two matrices is more efficient than doing n matrix-vector products. The batch size is limited because you get diminishing speedup out of increasing your batch size. Stochastic gradient descent also gets less improvement out of each data point per pass through the data set as you increase the batch size, so you need more passes. If you take the whole data set to be your batch size then you get ordinary gradient descent, which needs a lot more passes through the data set than stochastic gradient descent.
  - dan-robertson 8y ago
    If deep learning we’re just a big matrix multiplication then it would not be deep, it would be linear. The (eg sigmoid) functions mixed between the layers make it deep. I’m not really sure what it is about the training that you think is just a matrix multiplication. It’s also worth noting that eg a convolution can be written with matrix multiplication (or rather some tensor products and contraction but there would be much redundancy from the fact that distant points cannot influence each other and the same thing is done to each point in the convolution. This is much less general than matrix multiplication
jules 8y ago
The algorithms with the best asymptotic complexity aren't used in practice because they are slow for the n we care about. In practice optimising matrix multiplication comes down to making efficient use of SIMD, multiple cores and caches.
stochastic_monk 8y ago
There has been an enormous amount of effort placed into optimizing matrix multiplication. The key here is that the methods have impracticably huge constant factors, such that for anything beyond Strassen would necessitate matrices larger than we could conceivably use to be more effective. This comment also seems to suggest that legions of scientists and engineers aren't trying to optimize matrix multiplication. They are. Here are a few directions to pay attention to: 1. Specialized matrix multiplications for specific sizes and with reduced precision. For example, Intel's libxsmm, methods for multiplying with reduced precision on [CGT]PU. 2. Structured matrix multiplication Circulant and FFT-like matrices can be multiplied in linearithmic time. If you can set your problem up to use these instead (see Choromanski's Orthogonal Random Features [2016] or Smola's Deep-Fried Convnets [2015]/Fastfood [2014]), you can dramatically improve the speed and memory efficiency of your application. 3. Hardware-specific optimizations. Optimizing algorithms by cache efficiency, using FMA (fused multiply-addition) and SIMD instructions, and prefetching all play a big part in improving these multiplications. I'm commenting specifically on CPUs, but similar issues and methods exist on all hardware backends. In summary, many people are working very hard on improving matrix multiplication. Lower asymptotic complexity algorithms are not the answer for this due to the absurd constant factors they require.
- wbhart 8y ago
  Is it yet known what the optimal sequence is for 3x3 matrix multiplication (for noncommuting entries, of course)?
  - wLMeOv2qjsFOjZG 8y ago
    No!
    - stochastic_monk 8y ago
      Wouldn’t this be easy to explore exhaustively? 27! is ~1e26, but most of these orderings are obviously terrible ideas.
davidmr 8y ago
At least in my limited experience, matrix multiplication optimization is some combination of a) so specific to the specific matrices being used that the optimization amounts to finding "tricks" to reduce the problem (dgemm to sgemm or sgemm to syrk, etc.) and thus is not generally useful or b) so highly tied to IP that general optimizations (be they mathematical or advances in GPU or CPU low-level code) are kept secret.
kkylin 8y ago
In addition to all the other reasons given (large constant, etc.), these faster algorithms are also often less stable numerically, as another poster alluded to above. See, e.g., https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm .

dan-robertson 8y ago

Well 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 ago
Extremely 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 ago
  It’s about O(n^2.37). The entire article is about this number.
- deleted 8y ago
  [deleted]
taeric 8y ago
This 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 ago
  Fully 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.
  - taeric 8y ago
    This was my thought. Am I correct in saying the batch size influences the size of the matrix? Or is there a more natural limiting factor?
    - jules 8y ago
      That's right. For a fully connected layer the matrix is of dimension (batch size) x (number of neurons in layer k) which gets multiplied by a matrix of dimension (number of neurons in layer k) x (number of neurons in layer k+1). People do this because going through the network with a batch is more efficient than going through the network separately for each element in the batch, mainly because multiplying two matrices is more efficient than doing n matrix-vector products. The batch size is limited because you get diminishing speedup out of increasing your batch size. Stochastic gradient descent also gets less improvement out of each data point per pass through the data set as you increase the batch size, so you need more passes. If you take the whole data set to be your batch size then you get ordinary gradient descent, which needs a lot more passes through the data set than stochastic gradient descent.
- dan-robertson 8y ago
  If deep learning we’re just a big matrix multiplication then it would not be deep, it would be linear. The (eg sigmoid) functions mixed between the layers make it deep. I’m not really sure what it is about the training that you think is just a matrix multiplication. It’s also worth noting that eg a convolution can be written with matrix multiplication (or rather some tensor products and contraction but there would be much redundancy from the fact that distant points cannot influence each other and the same thing is done to each point in the convolution. This is much less general than matrix multiplication

jules 8y ago

The algorithms with the best asymptotic complexity aren't used in practice because they are slow for the n we care about. In practice optimising matrix multiplication comes down to making efficient use of SIMD, multiple cores and caches.

stochastic_monk 8y ago

There has been an enormous amount of effort placed into optimizing matrix multiplication. The key here is that the methods have impracticably huge constant factors, such that for anything beyond Strassen would necessitate matrices larger than we could conceivably use to be more effective. This comment also seems to suggest that legions of scientists and engineers aren't trying to optimize matrix multiplication. They are. Here are a few directions to pay attention to: 1. Specialized matrix multiplications for specific sizes and with reduced precision. For example, Intel's libxsmm, methods for multiplying with reduced precision on [CGT]PU. 2. Structured matrix multiplication Circulant and FFT-like matrices can be multiplied in linearithmic time. If you can set your problem up to use these instead (see Choromanski's Orthogonal Random Features [2016] or Smola's Deep-Fried Convnets [2015]/Fastfood [2014]), you can dramatically improve the speed and memory efficiency of your application. 3. Hardware-specific optimizations. Optimizing algorithms by cache efficiency, using FMA (fused multiply-addition) and SIMD instructions, and prefetching all play a big part in improving these multiplications. I'm commenting specifically on CPUs, but similar issues and methods exist on all hardware backends. In summary, many people are working very hard on improving matrix multiplication. Lower asymptotic complexity algorithms are not the answer for this due to the absurd constant factors they require.

wbhart 8y ago
Is it yet known what the optimal sequence is for 3x3 matrix multiplication (for noncommuting entries, of course)?
- wLMeOv2qjsFOjZG 8y ago
  No!
  - stochastic_monk 8y ago
    Wouldn’t this be easy to explore exhaustively? 27! is ~1e26, but most of these orderings are obviously terrible ideas.

davidmr 8y ago

At least in my limited experience, matrix multiplication optimization is some combination of a) so specific to the specific matrices being used that the optimization amounts to finding "tricks" to reduce the problem (dgemm to sgemm or sgemm to syrk, etc.) and thus is not generally useful or b) so highly tied to IP that general optimizations (be they mathematical or advances in GPU or CPU low-level code) are kept secret.

kkylin 8y ago

In addition to all the other reasons given (large constant, etc.), these faster algorithms are also often less stable numerically, as another poster alluded to above. See, e.g., https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm .