2019/11/21 by Christos Psarras, Henrik Barthels, Paolo Bientinesi · 1 voice · 15 citations
Computer Science · Mathematics · #Algebra over a field #Benchmark (surveying) #Compiler #Computer science #Linear algebra #Linear system #Mathematics #Matrix Theory and Algorithms #Numerical Methods and Algorithms #Numerical linear algebra #Parallel Computing and Optimization Techniques #Programming language #Pure mathematics #Python (programming language) #Set (abstract data type) #Theoretical computer science #cs.MS #cs.PL
paper · pdf · doi:10.1145/3549935
published in ACM Transactions on Mathematical Software 48(3), 1-30 (Association for Computing Machinery)
arxiv created 2021/09/05 · openalex publication_date 2022/07/20 · arxiv updated 2022/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We observe a disconnect between the developers and the end users of linear algebra libraries. On the one hand, the numerical linear algebra and the high-performance communities invest significant effort in the development and optimization of highly sophisticated numerical kernels and libraries, aiming at the maximum exploitation of both the properties of the input matrices, and the architectural features of the target computing platform. On the other hand, end users are progressively less likely to go through the error-prone and time consuming process of directly using said libraries by writing their code in C or Fortran; instead, languages and libraries such as Matlab, Julia, Eigen and Armadillo, which offer a higher level of abstraction, are becoming more and more popular. Users are given the opportunity to code matrix computations with a syntax that closely resembles the mathematical description; it is then a compiler or an interpreter that internally maps the input program to lower level kernels, as provided by libraries such as BLAS and LAPACK. Unfortunately, our experience suggests that in terms of performance, this translation is typically vastly suboptimal. In this paper, we first introduce the Linear Algebra Mapping Problem, and then investigate how effectively a benchmark of test problems is solved by popular high-level programming languages. Specifically, we consider Matlab, Octave, Julia, R, Armadillo (C++), Eigen (C++), and NumPy (Python); the benchmark is meant to test both standard compiler optimizations such as common subexpression elimination and loop-invariant code motion, as well as linear algebra specific optimizations such as optimal parenthesization of a matrix product and kernel selection for matrices with properties. The aim of this study is to give concrete guidelines for the development of languages and libraries that support linear algebra computations.