Matrix Multiplication Inches Closer To Mythic Goal

Post by [deleted] » Sat, Dec 18, 2021, 2:38 PM UTC

nynx wrote: post #20

e-dant wrote: post #17

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…

200ns, not 200ms

Post by hamilyon2 » Sat, Dec 18, 2021, 4:03 PM UTC

dnautics wrote: post #15

SuchAnonMuchWow wrote: post #9

Earlier quoted context omitted.

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.

do we know if the rounding errors are a big deal for numerical methods that can tolerate inaccuracy (like gradient descent for machine learning)?

Post by nestorD » Sat, Dec 18, 2021, 4:31 PM UTC

dnautics wrote: post #15

SuchAnonMuchWow wrote: post #9

Earlier quoted context omitted.

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.

do we know if the rounding errors are a big deal for numerical methods that can tolerate inaccuracy (like gradient descent for machine learning)?

Post by davidgrenier » Sat, Dec 18, 2021, 4:54 PM UTC

MrYellowP wrote: post #27

I want to learn everything about this, so I can help solving it. Where do I start?

Post by saeta » Sat, Dec 18, 2021, 5:05 PM UTC

salamanderman wrote: post #29

The part I don't follow is that I thought multiplication used the same number of CPU cycles as addition, so I didn't get the the part where one multiplication replaced with many additions was obviously better. Could someone explain that part? I feel I must be fundamentally misunderstanding something.