Working on the projects, you must have had complained about the long running time of your Matlab code when you do a computation on huge matrices. Why do larger matrices take much longer running time? One of the obvious reasons is because there are more numbers to calculate with. If you are a very sensitive person, however, you must have felt that running time of a Matlab code is not always proportional to the number of calculations (multiplication, addition, etc.); when matrices get larger, running time increases much faster than the number of calculations. When a matrix gets 2 times larger and requires twice more computations to perform, running time would sometimes get even 3~4 times longer, which means running time per calculation gets longer!
Why would each calculation take a longer time, when matrices get larger? The main reason is because average memory access time (time required to access a memory location) increase as the matrices get larger. In computers, there are many levels of memory, each having different speed and size. While hard drives have huge storage space (40GB~500GB) but very slow access time (5~15ms) [1], L1 caches have very small storage (~32kB) with very fast access time (~1/4ns). While each level of memory would have different mechanism that determines its memory access time, the reason larger memory devices take longer access time is simple: it is harder to find something from a gigantic and more complex storage. Modern computers have multiple levels of memory with different sizes, because computer programs most of the times use small portion of the data, not everything stored in your computer; even now, I am not using any Matlab or other programs installed in my computer, but just have internet explorer and some other applications on my memory! By having smaller memories to store what is being used, we can avoid accessing large and slow memory but access small portion of data we need much faster by accessing the “cached” data from smaller memory. It would be same as having the books you read most frequently – possibly CS322 textbook - next to your desk and keeping your CS312 book back in your garage.
So, what happens when we get larger matrices to compute with is your matrix would not fit to a smaller memory and you have to use a larger but slower one, and your average memory access time would get larger! It would cause each simple computation to take much longer time and slow your program super-linearly, as you use slower memory. There have been interesting studies that relate each memory level’s sizes and applications. One of the examples is [2], in which their algorithm divides the problems into smaller ones so that the working set of the sub-problems would fit into a small and fast cache (memory). It would prevent the working-set (data) to be too large and thus let us have fast memory access all the time. One of the main problems to which this algorithm and be applied is matrix computation, such as multiplication and transpose. Understanding how the computer hardware work can definitely benefit scientific computing.

References:
[1] Wikipedia – Hard Disk Drive, http://en.wikipedia.org/wiki/Hard_drive
[2] Kamen Yotov et al., An experimental comparison of cache-oblivious and cache-conscious programs (2007)

- this is my second post of the semester - sorry for missing the deadline