Multiplying Matrices Without Multiplying

Re:Multiplying Matrices Without Multiplying by infogulch on Tuesday August 31, 2021 @11:30PM (#28376177)

I wonder how much alternative number representations have been studied for use in matrices. Like, storing the log of values instead so that multiplication can be done by just adding. Or something like Zech's logarithm. Or even, take the log of whole matrices (which is a thing apparently [0]), then adding them to compute their multiplication. I wonder if the logarithm of a matrix can be computed using ML.

[0]: https://en.wikipedia.org/wiki/Logarithm_of_a_matrix

[ Parent | on HN ]

Re:Multiplying Matrices Without Multiplying by ffast-math on Wednesday September 01, 2021 @12:50AM (#28376541)

There's been some work on doing adds instead of multiplies (e.g., https://arxiv.org/abs/2012.03458). And I think float8 will roughly be doing this under the hood.

Personally, I'm not sure whether this is the path to go down or not. Doing everything in log space could help from a hardware perspective, since multiply-adds are much more complex than adds. But it 1) doesn't reduce the number of operations being performed, 2) might increase the necessary bit width for a given level of fidelity (depending on your input distribution and other factors), and 3) might make accumulate operations expensive, since these aren't cleanly expressed in the log domain.

[ Parent | on HN ]

Re:Multiplying Matrices Without Multiplying by michelpp on Wednesday September 01, 2021 @09:07AM (#28379345)

There is a logarithmic semiring:

https://en.wikipedia.org/wiki/Log_semiring

which can be used to multiply two sparse matrices with the GraphBLAS. here is an example in Python:

https://github.com/Graphegon/pygraphblas/blob/main/demo/Log-...

[ Parent | on HN ]

Re:Multiplying Matrices Without Multiplying by rocqua on Wednesday September 01, 2021 @05:47AM (#28377951)

storing log values helps with the multiply part of multiply and add.

But it seems like it would make the add part of multiply and add quite a bit more difficult.

[ Parent | on HN ]

Re:Multiplying Matrices Without Multiplying by thwoeri2324 on Wednesday September 01, 2021 @12:34AM (#28376467)

Quick note: the exp does not work the way it does with scalars.

https://en.wikipedia.org/wiki/Matrix_exponential#Elementary_...

[ Parent | on HN ]