Many have been telling me for more than a decade that dense linear algebra is dead and that it is time to move on to more interesting subjects. I have concluded that despite our best efforts we have failed to beat this area to death. Rather, researchers in this area have painted themselves into a corner. The cause of this is very fundamental: the notation that we have been using to express algorithms. The fact that we have always expressed algorithms with intricate indices into the arrays that store matrices has always greatly complicated matters, restricting who can make progress in this area to the rare few who can keep track of all these indices. This, in my opinion, has also made it so that computational scientist view our products, libraries, as black boxes that few take the time to truly understand and appreciate for the mathematics and computer science advances that they also represent.

The solution is to carefully examine how one explains theory and algorithms in a classroom setting or during informal discussions at a whiteboard: we draw pictures to explain the algorithms. It is these pictures that should be captured in the notation that we use. An example of what an alternative notation could look like and its broad applicability is given in

Paolo Bientinesi and Robert van de Geijn. "Representing Dense Linear Algebra Algorithms: A Farewell to Indices." FLAME Working Note #17. The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-2006-10. http://www.cs.utexas.edu/~flame/web/publications.html

One question is how we arrived where we are in the first place. Personally, I believe the following events conspired over the past 40 years:

(1) The cost of typesetting mathematics. Mathematical papers are praised for the conciseness of the notation. I suspect that the cost of typesetting mathematical formulae in the early days was a major influence on this. Unfortunately, conciseness can also obscure.

I propose that a page should be viewed like a canvas now that printing is cheaper and electronic dissemination is widespread. Algorithms, formulae, and pictures should be placed on this canvas in a way that conveys information much like we would on a whiteboard.

(2) Early programming languages. Many libraries were originally developed in Fortran 77 (and Algol and Fortran 66 before this). Abstraction was not a key part of these early languages: loops with indexing into arrays was always the way to code. Since algorithms should be easy to translate to code, this same structure appears in the algorithms in texts.

I propose that modern programming practices embrace encapsulation and abstraction and that therefore algorithms as expressed in papers and texts should too.

(3) Optimizing compilers. Compilers were traditionally designed to optimize code as written by the target community. Thus, much research was pursued to optimize code with loops and intricate indices into arrays. In turn this meant that the community continued to write code with intricate indices, since that is what compilers could optimize. This has created a vicious cycle over the years. The introduction of the “BLAS” abstraction has only complicated matters, since interprocedural analysis makes it hard to optimize through the barrier that the interface represents.

I propose that if we all start coding at a high level of abstraction, where the abstraction matches the abstraction with which algorithms are naturally presented, then compiler research will focus on supporting such code. Since these abstractions present high level information to the compiler that dependence analysis otherwise needed to deduce from the loops, better optimizations should be possible.

My experience is that abandoning traditional notation for representing algorithms, either in a paper or in code, is what will get us out of our rut. It allows new algorithms for more complex operations to be easily identified and implemented. It also opens up a whole new research topic within this very old field: how to make the generation of algorithms from the mathematical specification of the operation mechanical, including implementation, optimization, and (cost and stability) analysis. And if this mechanical generation is successful, then the field of dense linear algebra library development will truly be solved, which is a much better place to be than being dead.

Robert van de Geijn
UT-Austin