  Expressions that involve matrices and vectors, known as linear algebra
expressions, are commonly evaluated through a sequence of invocations to highly
optimised kernels provided in libraries such as BLAS and LAPACK. A sequence of
kernels represents an algorithm, and in general, because of associativity,
algebraic identities, and multiple kernels, one expression can be evaluated via
many different algorithms. These algorithms are all mathematically equivalent
(i.e., in exact arithmetic, they all compute the same result), but often differ
noticeably in terms of execution time. When faced with a decision, high-level
languages, libraries, and tools such as Julia, Armadillo, and Linnea choose by
selecting the algorithm that minimises the FLOP count. In this paper, we test
the validity of the FLOP count as a discriminant for dense linear algebra
algorithms, analysing "anomalies": problem instances for which the fastest
algorithm does not perform the least number of FLOPs.
  To do so, we focused on relatively simple expressions and analysed when and
why anomalies occurred. We found that anomalies exist and tend to cluster into
large contiguous regions. For one expression anomalies were rare, whereas for
the other they were abundant. We conclude that FLOPs is not a sufficiently
dependable discriminant even when building algorithms with highly optimised
kernels. Plus, most of the anomalies remained as such even after filtering out
the inter-kernel cache effects. We conjecture that combining FLOP counts with
kernel performance models will significantly improve our ability to choose
optimal algorithms.
