Classical C++ linear algebra libraries offer sparse matrix types where the sparseness is only known at run-time. At compile-time, some libraries also incorporate information about the matrix shape (upper/lower triangular, diagonal, symmetric) but not about sparsity.
However, due to run-time / SIMD considerations these sparse matrix shapes are stored as a dense matrix meaning that 50% or more of the entries are trivially 0. While being potentially beneficial for run-time, this also introduces a significant memory overhead.
In this talk, we will see how it is indeed possible to get a free lunch by combining memory efficiency with run-time efficiency.
We'll learn how sparseness information can be incorporated into a matrix class at compile time. This means that only the necessary (non-zero, non-one, non-symmetric) entries have to be stored making such matrices very memory efficient.
Furthermore, this enables compilers to automatically remove all unnecessary operations, yielding a performance on par with hand-written sparse-matrix code and in some cases even significantly faster.
Join me on this journey where we'll move from "No raw loops" to "No run-time loops" and learn how a type-safe library interface can enforce "If it compiles, it works!" as well as "If it compiles, it's efficient!".
View Slides
Daniel Withopf has been working on solving real-world problems with C++ in robotics and related fields for over 20 years. He currently is a Software Engineer at the German car supplier Bosch where he wrote and maintains an object tracking framework for self-driving car projects. While doing that he discovered novel ways how to leverage C++'s type system to create linear algebra and tracking code that is more expressive, easier to understand and less likely to contain errors.