# What sparse solver supports diagonal storage format

I'm writing finite-difference method program using C. The stiffness matrix is symmetrical and band. For its storage I'd like to use Sparse Diagonal Storage format.

Could someone tell please, what solvers can use diagonal storage format? Intel MKL's Paradiso uses only CRS-format, SparseLib doesn't have, Spooles seems also =(

Thank you.

• Hi DFooz, and welcome to Scicomp! Did you mean to say compressed diagonal storage format? – Paul Mar 20 '13 at 20:23
• DFooz, I'm curious why the use of diagonal storage is so important. You've listed some excellent software packages here, it seems a shame not to tailor your code to use them. – Michael Grant Mar 21 '13 at 1:18
• Actually I had a little trouble finding references on Sparse Diagonal Storage format. I ultimately did so, but also happened to find that you've asked this question on StackOverflow as well. Usually it is a good idea to note when you have posed the same question in multiple places. – Michael Grant Mar 21 '13 at 1:33
• Paul, heh=), how many diagonal formats... I meaned (center of the page) software.intel.com/sites/products/documentation/hpc/mkl/mklman/… @MichaelGrant, OK. =) – Ivan Kush Mar 21 '13 at 13:23
• Paul, yes, I meaned compressed diagonal storage. In intel MKL written without woord compressed – Ivan Kush Mar 21 '13 at 13:33

There are surprisingly few references to "Sparse Diagonal Storage" format on Google. Here is a PDF of some slides I found that provide a brief overview of Compressed Row, Jagged Diagonal, and Sparse Diagonal formats. Most of the other links are pointers to a single paper, Use of sparse diagonal storage in finite element analysis by K.K. Yalamanchili and S.C. Anand.

So this isn't good news, really: It suggests that Sparse Diagonal Storage has not been adopted very widely. I'm going to hazard a guess: the format is probably more useful for iterative methods than for direct (factorization) methods. Implementing sparse matrix-vector multiplication is relatively straightforward for any of these formats, so for iterative methods you have the freedom to store as you wish (at least until you need an incomplete factorization for a preconditioner!)

If your matrix has a relatively dense diagonal band, then you may want to consider one of LAPACK's banded solvers. These store the diagonals along the rows of a matrix with B rows, where B is the bandwidth of the matrix. (EDIT: or (B+1)/2 rows if the matrix is symmetric/Hermitian). But if you truly require a sparse direct solver, then it looks like you will either have to implement your own or convert to a more common storage format. (If you decide to implement your own, perhaps you will quickly learn why SDS is not suitable :P)

EDIT: The abstract for the Yalamanchili-Anand paper suggests that they are focused on vector-matrix multiplication; i.e., iterative methods.

• Thank you very much! I'm a newbie, your post is very helpful! I'll use band storage. – Ivan Kush Mar 21 '13 at 13:29

Found=), but haven't tried.

In Intel MKL Sparse BLAS Level 2 and Level 3 Routines.

mkl_?diatrsv Triangular solvers with simplified interface for a sparse matrix in the diagonal format with one-based indexing.

http://software.intel.com/sites/products/documentation/hpc/mkl/mklman/GUID-9FBF0F88-4731-45DA-BDE9-AF4D7A0A18A4.htm#GUID-9FBF0F88-4731-45DA-BDE9-AF4D7A0A18A4

Description of the used diagonal format is in the middle of the page http://software.intel.com/sites/products/documentation/hpc/mkl/mklman/GUID-9FCEB1C4-670D-4738-81D2-F378013412B0.htm