Neville elimination: a study of the efficiency using checkerboard partitioning Original Research Article

It is well known that checkerboard partitioning can exploit more concurrency than striped partitioning because the matrix computation can be divided among more processors than in the case of striping. In this work we analyze the performance of Neville method when a checkerboard partitioning is used, focusing on the special case of block–cyclic-checkerboard partitioning. This method is an alternative to Gaussian elimination and it has been proved to be very useful for some classes of matrices, such as totally positive matrices. The performance of this parallel system is measured in terms of the efficiency (the fraction of time for which a processor is usefully employed) which in our model is close to one, when the optimum block size is used. Also, we have executed our algorithms on a Parallel PC cluster, observing that both efficiencies (theoretical and empirical) are quite similar.