Cache-independent algorithms

The memory in modern computer systems has a highly complex hierarchy. The farther the memory from the processor, the larger it is, but also the slower. Each computer has its own architecture and its own cache memory, and it is not easy to write an algorithm that will run with equal efficiency on all computers. In this article we consider the simplest model of a two-level memory for which two cacheindependent algorithms are proposed: multiplication of full matrices and multiplication of a sparse matrix by a block vector.