Does the performance of matrix multiplication depend on the storage of the array?

Two matrices can be stored in either row major or column major order in contiguous memory. Does the time complexity of computing their multiplication vary depending on the storage scheme? That is, I want to know whether it will work faster if stored in row major or column major order.

The asymptotic complexity will not change with relation to how the matrices are laid out in memory, but the actual running time of the matrix multiplication will be very dependent upon the memory layout. There are two papers that I know of that go into detail about this, one by McKellar in 1969 and another by Prokop in 1999. Prokop's paper defines the concept of cache complexity which is related to the number of cache misses the algorithm will incur.

The two papers can be found here:
http://supertech.csail.mit.edu/papers/Prokop99.pdf and here: http://dl.acm.org/citation.cfm?id=362879

The short version is, an $O(n^3)$ algorithm will still be an $O(n^3)$ algorithm (assuming you are using the straightforward matrix-multiply). However, by taking into account the memory hierarchy of the system, you can significantly speed up that $O(n^3)$ algorithm.

StackExchange Computer Science Q#17865, answer score: 6