Robust Ranking of Linear Algebra Algorithms via Relative Performance

For a given linear algebra problem, we consider those solution algorithms that are mathematically equivalent to one another, and that mostly consist of a sequence of calls to kernels from optimized libraries such as BLAS and LAPACK. Although equivalent (at least in exact precision), those algorithms typically exhibit significant differences in terms of performance, and naturally, we are interested in finding the fastest one(s). In practice, we often observe that multiple algorithms yield comparable performance characteristics. Therefore, we aim to identify the subset of algorithms that are reliably faster than the rest. To this end, instead of quantifying the performance of an algorithm in absolute terms, we present a measurement-based approach that assigns a relative score to the algorithms in comparison to one another. The relative performance is encoded by sorting the algorithms based on pair-wise comparisons and ranking them into equivalence classes, where more than one algorithm can obtain the same rank. We show that the relative performance leads to robust identification of the fastest algorithms, that is, reliable identifications even with noisy system conditions