3 ms·
However, the number of additions required to add those sets of matrices is much closer together. Generally, the number of additions is equal to the number of en
by balefrost 6y ago
However, the number of additions required to add those sets of matrices is much closer together. Generally, the number of additions is equal to the number of entries in the matrix, so four for the two-by-two matrices and 16 for the four-by-four matrices.
Maybe my linear algebra is REALLY rusty, but I that doesn't seem right to me.
For two 4x4 matrices, each element in the output matrix will be the sum of four products. So each of the 16 output elements will require 3 additions, and you'll need a total of 48 additions.
I'm not sure where they're getting "16 additions" from.
To multiply two nxn matrices according to the textbook method, I think you'll need n^3 multiplications and n^3-n^2 additions.
I don't doubt that the multiplication time dominates the algorithm. Maybe this is just a nitpick.
- soVeryTired 6y agoThey're counting the additions needed to add the matricies, not to multiply them. The point being that matrix addition is order n^2 so even if you need to do a large number of matrix additions in some intermediate calculation, they don't hurt you as n gets large if you're trying to speed up matrix multiplication.
- balefrost 6y agoThat doesn't seem to be what they are saying. Here's the first sentence of the paragraph that I had originally quoted: As matrices grow larger, the number of multiplications needed to find their product increases much faster than the number of additions. The whole paragraph is talking about the multiplications and additions needed to find the product of two matrices.
- afiori 6y agoit could refer to matrix multiplication and matrix addition of smaller matrices during the algorithm (iirc most fast multiplication algorithms start by splitting the matrix in pieces)