MJ Rutter's Linpack Page: Counting Operations

The original algorithm for the Linpack benchmark used two-thirds N3 plus twice N2 floating-point operations. When discussing timings, it is assumed that any implementation of LU factorisation with partial pivoting followed by back substitution takes this number of operations, and from a time in seconds and this assumption one can calculate a number of GFLOPS.

In order to have a result accepted by the Top500 benchmarking site, the operation count must be two-thirds N3 plus order N2 floating-point operations. There are known methods for reducing the count below order N3 based on matrix-matrix multiplication methods which are better than order N3, such as Strassen's algorithm, for which the power of N in the order is not three but log27, approximately 2.81.

Methods which reduce the operation count may also reduce the accuracy. They also tend to move away from an equal number of additions and multiplications, whereas modern processors tend to perform optimally only when multiplications and additions can be paired.

Back to Linpack page.