Show HN: Did you know you can multiply matrices without multiplication?

6 points

3 years ago

TL;DR: This idea implemented in Python https://gist.github.com/danbst/fdf604ae279f9e01c8a28f1f84f9876e

Hello. Long time ago I have learned that

     log(xy) = log(x) + log(y)

and that this was used by Napier to multiply numbers. Also I knew that matrix multiplication time is dominated by inner dot products, which use addition and multiplication.

And it just stuck me today, that it is possible to multiply matrices in logarithmic space (that is, matrix values are logs of real values) without multiplication! By using same trick Napier did.

(There are restrictions, as negative values produce complex logarithms. So it has to be handled carefully)

3 comments