11–20 of 53 posts
Which one of these algos does Intel/Nvidia/Google use in their AVX/Cuda/TPU implementations?
Simple block partitioning, usually 4x4, with the full ordinary algorithm per block. This is the most numerically-stable and parallel. https://developer.nvidia.com/blog/cutlass-linear-algebra-cud...
Here's the paper: https://arxiv.org/abs/math/0511460
Here's a set of lecture notes that are simpler to read and give an easy example of how group theoretic methods work: http://www.ccs.neu.edu/home/viola/classes/gems-08/lectures/l...
Earlier quoted context omitted.
What makes you say that? I've had good speedups with Strassen multiplication in variable precision (or with floating-point, in case you meant fixed-point arithmetic).
Speed is fine. The issue is numerical stability.
Earlier quoted context omitted.
What makes you say that? I've had good speedups with Strassen multiplication in variable precision (or with floating-point, in case you meant fixed-point arithmetic).
Strassen method is faster than native multiplication, but it is not stable: you will get much larger rounding errors when implementing it using floating point numbers, compared to native multipllication. And fine precision is required for a lot of algorithm implemented using matrix multiplication, such as matrix inversion or gradient descent, so this is often a problem.
...and in case anyone is wondering, no, this is still not a practical speedup. https://en.wikipedia.org/wiki/Galactic_algorithm#Matrix_mult...
MM (especially MM on large type numbers like e.g. hashing algorithms) are very reliant on the cache because you can’t always fit that big of a number into a register. Side note, I was reading some Abseil code last night that did some funky bit twiddling on ARM: https://github.com/abseil/abseil-cpp/blob/master/absl/hash/i...
Off the top of my head, isn’t it about 200ns [edit, not ms] to query, bus, and read something from memory? Just a thought, perhaps the cache and memory is where we should focus our efforts.
This thought has been churning around in my mind for some years now — we focus too much on processing speed and reductions in time complexity and not enough on increasing the size and efficiency of our cache and stack . MM (especially MM on large type numbers like e.g. hashing algorithms) are very reliant on the cache because you can’t always fit that big of a number into a register. Side note, I was reading some Abs…
This thought has been churning around in my mind for some years now — we focus too much on processing speed and reductions in time complexity and not enough on increasing the size and efficiency of our cache and stack . MM (especially MM on large type numbers like e.g. hashing algorithms) are very reliant on the cache because you can’t always fit that big of a number into a register. Side note, I was reading some Abs…
It's only for mathematical interest
This thought has been churning around in my mind for some years now — we focus too much on processing speed and reductions in time complexity and not enough on increasing the size and efficiency of our cache and stack . MM (especially MM on large type numbers like e.g. hashing algorithms) are very reliant on the cache because you can’t always fit that big of a number into a register. Side note, I was reading some Abs…