Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Intel Community
- Software
- Software Development SDKs and Libraries
- Intel® oneAPI Math Kernel Library
- The right matrix for the adjacency matrix of a power-law graph

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

zhengda1936

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-09-2015
11:54 AM

49 Views

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

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-multipl..., 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

Link Copied

4 Replies

Maxim_P_Intel

Employee

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-12-2015
05:31 AM

49 Views

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

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-12-2015
06:03 AM

49 Views

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

Employee

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-17-2015
07:43 AM

49 Views

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

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-17-2015
07:06 PM

49 Views

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

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

For more complete information about compiler optimizations, see our Optimization Notice.