Blocking Neville elimination algorithm for exploiting cache memories

摘要

Neville elimination is a method for solving a linear system of equations that introduces zeros in a matrix column by adding to each row an adequate multiple of the previous one. In this paper, we explore block algorithms for Neville elimination which take into account the memory hierarchies of a computer. These algorithms try to manage the memory movements to optimize them. Thus, the matrix of the system is divided following three different strategies, blocking by rows, columns or submatrices. In each case, we study the performance of the algorithm according to the ratio of floating point operations to memory references (q). Theoretical estimations show that q depends on data partitioning, being submatrix blocks the best choice.