# Sparse Linear Algebra vs Dense Linear Algebra

I am interested in a reference in the literature that discusses the performance of Dense Linear Algebra (blas routines) and dense linear algebra (sparse blas routines).

I am interested in knowing for what combinations of size and density sparse routines outperform dense routines. I am mainly interested in a shared memory computer. Does anyone know of a reference?

Thanks,

• Which operations, and what is your definition of performance? E.g., FLOPS may be misleading when comparing a dense DGEMV vs. a sparse MatVec when time to complete the operation is all you really care about. Jun 30, 2015 at 1:26
• Also, how do you want to amortize the cost of setting up your sparse data structures? Are you going to setup a sparse matrix once and then do millions of sparse matrix-vector multiplications? Even after you've specified the benchmark tasks, you'll still find that the results depend a lot on the particular computer that you use (e.g. number of processor cores and memory bandwidth) and on the particular implementations of the sparse blas and blas library routines that you use. Jun 30, 2015 at 2:11
• I would start with Demmel's book. Also, I think you have written "dense" twice by accident. Jun 30, 2015 at 5:02
• I am the original poster. I have been using sparse matrix routines extensively for finite elements but have never done any benchmarking. I recently watched a talk by Bjarne Soustroup where he compared the performance of arrays and linked lists in tasks where I would guess a linked list would vastly outperform vectors. This made me question my assumption that sparse linear algebra routines outperform dense ones. Does anyone have any thoughts on this?
– fred
Jul 1, 2015 at 1:30
• To answer Bill Barth's question, my idea of performance in this case is time to completion. The point that Soustroup made in his talk is that plain old vectors are contiguous in memory and have a lot of advantages on a modern processor with a sophisticated cache hierarchy.
– fred
Jul 1, 2015 at 1:38