The right matrix for the adjacency matrix of a power-law graph

[zhengda1936]

Hello,

What is the best matrix format for the adjacency matrix of a power-law graph when we perform sparse matrix vector multiplication? I would like to use a format that has both memory efficiency and performance efficiency. CSR and CSC are both memory efficient, but these formats will cause many CPU cache misses in multiplication when the matrix is very large. BSR doesn't seem very memory efficient for the adjacency matrix of a power-law graph. Ellpack sparse block (ESB) seems a much better format (https://software.intel.com/en-us/articles/the-intel-math-kernel-library-sparse-matrix-vector-multiply-format-prototype-package), but I can't find it in the document (https://software.intel.com/sites/products/documentation/doclib/iss/2013/mkl/mklman/index.htm). Is CSR or CSC the only best option for an adjacency matrix?

Thanks,

Da

[Maxim_P_Intel]

Hi Da,

You can read about ESB format in the original article - http://dl.acm.org/citation.cfm?id=2465013, just click on PDF document link.

The article also contains performance comparison with CSR format on a number of test matrices.

[zhengda1936]

Hello Maxim,

I have read the paper. I'm just curious whether their ESB format and their sparse matrix vector multiplication are or will be released in MKL.

Thanks,

Da

[Maxim_P_Intel]

Hello Da,

Currently there is no ESB format support in MKL.

However it is be possible that ESB format and ESB optimized operations appear in MKL if there will be enough customer’s request for it.

So may I ask you a couple of questions?

    Did you try to use ESB from SpMV package? If yes, with what results?

    What kind of problems do you simulate?

    Is it important for you to have ESB format support in MKL and why?

[zhengda1936]

Hello Maxim,

I don't have an ESB implementation, so I don't know its performance. I guess it'll perform better than CSR. I'm also eager to know how well it can perform on CPUs.

I'm looking for a very fast SpMV implementation optimized for adjacency matrices of power-law graphs. It seems MKL isn't optimized for this kind of sparse matrix. I don't particularly care about ESB format. Currently I'm interesting in computing the eigenvalues/vectors of the adjacency matrices.

Thanks,

Da