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. Thusv 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 parameter g which evaluates the ratio of flops to memory references. Theoretical estimations show that q depends on data partitioning, being submatrix blocks the best choice.