Viewing a single comment thread. View all comments

mcilrain t1_isbru8i wrote

Maybe I don't understand matrix multiplication but isn't that just iterating over two arrays of numbers and multiplying each pair together?

I don't understand how that could be optimized, it shouldn't be possible to make it simpler than LOAD -> MULTIPLY -> STORE, right?

2

Nostr0m t1_isbt2ks wrote

You can save multiplication operations by clever additions and subtractions. See Strassen's algorithm for an example.

8

mcilrain t1_isbtvx2 wrote

That wouldn't work in all cases though, right? Wouldn't the logic needed to determine when it's safe make it slow? Or are errors worth the increased performance?

1

Nostr0m t1_iscv4x4 wrote

No, these are deterministic algorithms guaranteed to produce the right answer, so there are no errors involved. If you would like to learn more look into an intro to algorithms course, pretty interesting stuff

5

mcilrain t1_iscw9kh wrote

Floating point number calculations are always slightly inaccurate to a certain degree as a performance trade-off, increasing the inaccuracy in the result in exchange for even greater efficiency is plausible.

I'd expect an algorithms course to go right over my head, I'm good with logic but terrible with numbers.

3

Chop1n t1_isdcwxh wrote

Don't tell me: your name is a portmanteau of Nick Bostrom.

1

Nostr0m t1_isggbvd wrote

Haha not intentionally, but that's interesting now you mentioned it.

3

pie3636 t1_iscem6o wrote

> isn't that just iterating over two arrays of numbers and multiplying each pair together?

It isn't. That would be elementwise multiplication, which is sometimes used but not nearly as useful/ubiquitous.

2

PolymorphismPrince t1_ismf6h6 wrote

Matrix multiplication is taking the dot product of every row with every column.

1

mcilrain t1_ismffnr wrote

I don't know what a dot product is, I tried googling it and it spat greek at me.

1

PolymorphismPrince t1_ismncj6 wrote

For example, to find the entry in row 4 and column 3 of the matrix you get out of the product, you take all the entries in the fourth row of the first matrix, all the entries in the 3rd column of the second matrix, multiply those lists together in the way you were talking about in your comment, and then add up all those multiplications.

1