Paper Info
Title
The Linear Algebra Mapping Problem. Current State of Linear Algebra Languages and Libraries
Abstract
We observe a disconnect between developers and end-users of linear algebra libraries. On the one hand, developers invest significant effort in creating sophisticated numerical kernels. On the other hand, end-users are progressively less likely to go through the time consuming process of directly using said kernels; instead, languages and libraries, which offer a higher level of abstraction, are becoming increasingly popular. These languages offer mechanisms that internally map the input program to lower level kernels. Unfortunately, our experience suggests that, in terms of performance, this translation is typically suboptimal.In this paper, we define the problem of mapping a linear algebra expression to a set of available building blocks as the “Linear Algebra Mapping Problem” (LAMP); we discuss its NP-complete nature, and investigate how effectively a benchmark of test problems is solved by popular high-level programming languages and libraries. Specifically, we consider Matlab, Octave, Julia, R, Armadillo (C++), Eigen (C++), and NumPy (Python); the benchmark is meant to test both compiler optimizations, as well as linear algebra specific optimizations, such as the optimal parenthesization of matrix products. The aim of this study is to facilitate the development of languages and libraries that support linear algebra computations.
Year
DOI
Venue
2022
10.1145/3549935
ACM Transactions on Mathematical Software
Keywords
DocType
Volume
LAMP, linear algebra mapping problem, linear algebra, domain specific languages, compilers
Journal
48
Issue
ISSN
Citations 
3
0098-3500
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Christos Psarras100.34
Henrik Barthels200.34
Paolo Bientinesi344853.91