LAGraphStruct.tex

\section{LAGraph Repository}
\label{sec:repo}

The hypothesis underlying the GraphBLAS is that algorithm designers can focus on expressing their algorithms
in terms of the high level linear algebra operations defined in the GraphBLAS while leaving low level
optimizations to any particular hardware platform to the implementation of the GraphBLAS.  Ultimately, 
we want hardware vendors to be responsible for creating highly tuned versions of the GraphBLAS
specialized to the features of their systems.
Kumar et al.~\cite{KuHPEC2016} show that mitigating the adverse impact of memory
latency on performance of algorithms for large graph can lead to significant improvements.
Such optimizations require detailed knowledge of the underlying system, and hence the 
low-level optimizations are best left to hardware vendors.
Furthermore, a tuned linear algebra library delivers
better performance than straight-forward textbook implementation on many basic graph algorithms~\cite{KuJour}.

Algorithm designers will naturally wonder how much performance is lost due to the use of a high 
level API such as the GraphBLAS.  As shown in~\cite{KuJour}, a linear algebra 
implementation brings inherent efficiency advantages to 
graph algorithms due to the more structured access to data afforded by the linear algebra 
formulation~\cite{KuJour}.
The GraphBLAS API is more general, but we expect its implementations to retain or improve upon
the efficiency advantages.
This is an untested hypothesis, since until now, we have not had multiple 
implementations of the GraphBLAS API tuned to the features of a range of platforms.

Testing this hypothesis of the performance potential afforded by the GraphBLAS is a major outcome
we anticipate from the LAGraph project.  By collecting high level graph algorithms and validating them
across an engaged community, we will produce the library of algorithms needed to evaluate the 
effectiveness of the GraphBLAS approach.

Before we can conduct such experiments, however, we need to collect graph algorithms implemented on 
top of the GraphBLAS. We have created a GitHub repository at
\url{https://github.com/GraphBLAS/LAGraph} for members of the LAGraph community to 
use to contribute GraphBLAS algorithms. The basic elements of the repository include:
%% DONE: this is complete:
\begin{itemize}
\item A Build System for creating the LAGraph library and the test routines.
\item A library of utilities including loading matrices from disk in Matrix Market format~\cite{MM},
    evaluating results, and creating random test matrices.
\item A directory of graph algorithms.
\item A directory holding a test harness for each algorithm.
\end{itemize}

We will write documentation, a programmer's reference guide and define procedures for how people
can add new algorithms.