Hacker News Reader

They'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.

View on HN

That 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.

it 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)

Reply on news.ycombinator.com