column-major order, or a mix of both. In particular, in the idealized case of a fully associative cache consisting of bytes and bytes per cache line (i.e. cache lines), the above algorithm is sub-optimal for and stored in row-major order. When , every iteration of the inner loop (a simultaneous sweep through a row of and a column of ) incurs a cache miss when accessing an element of . This means that the algorithm incurs cache misses in the worst case. , the speed of memories compared to that of processors is such that the cache misses, rather than the actual calculations, dominate the running time for sizable matrices. The optimal variant of the iterative algorithm for and in row-major layout is a tiled version, where the matrix is implicitly divided into square tiles of size by : Input: matrices and Let be a new matrix of the appropriate size Pick a tile size For from 1 to in steps of : For from 1 to in steps of : For from 1 to in steps of : Multiply and into , that is: For from to : For from to : Let For from to : Set Set Return In the idealized cache model, this algorithm incurs only cache misses; the divisor amounts to several orders of magnitude on modern machines, so that the actual calculations dominate the running time, rather than the cache misses. Divide-and-conquer algorithm An alternative to the iterative algorithm is the divide-and-conquer algorithm for matrix multiplication. This relies on the block partitioning which works for all square matrices whose dimensions are powers of two, i.e., the shapes are for some . The matrix product is now which consists of eight multiplications of pairs of submatrices, followed by an addition step. The divide-and-conquer algorithm computes the smaller multiplications recursively, using the scalar multiplication as its base case. The complexity of this algorithm as a function of is given by the recurrence accounting for the eight recursive calls on matrices of size and to sum the four pairs of resulting matrices element-wise. Application of the master theorem for divide-and-conquer recurrences shows this recursion to have the solution , the same as the iterative algorithm. Non-square matrices A variant of this algorithm that works for matrices of arbitrary shapes and is faster in practice splits matrices in two instead of four submatrices, as follows. Splitting a matrix