Building up matrix incrementally

[simpletonDL]

Hello! I've run into problem. I want to build up matrix incrementally.

Suppose initially we have A matrix, and at each step we add some another matrix to the original, so we compute A = A + B_i-1. But I don't want a new matrix to be created after each addition operation, because in this case running time of addition A and B will be at least the number of implicit elements. And if matrix A becomes dense, and matrices B_i contain only a small number of explicit values (let it be O(1)), the running time of addition will O(|A|) ~ O(n^2). It is not cool) But if I could build up the matrix incrementally, then the time for each operation would be O(B_i) ~ O(1).

I know, that CSR format doesn't provide matrix expansion and creating a new matrix after each operation is necessary, bu sometimes it degrades performance. So the question is whether GraphBlas supports other formats suitable for incremental computing (for example DOK - dict of values, of something else).

Thank you for your attention)

[szarnyasg]

Hi @simpletonDL,

So the question is whether GraphBlas supports other formats suitable for incremental computing (for example DOK - dict of values, of something else).

In theory, GraphBLAS allows using of such formats, in fact, any representation can be used because objects are treated as opaque. However, incrementally updatable matrix formats are currently not implemented in SuiteSparse:GraphBLAS. There are some interesting works on the topic, e.g. faimGraph, Hornet, and Stinger but none of these made it into GraphBLAS implementations yet.

[DrTimothyAldenDavis]

In the current implementation of SuiteSparse:GraphBLAS, the answer depends on what you are doing with the matrix A, and how its pattern changes.

If you don't need to do anything with A except update it, then GrB_assign or GxB_subassign will be very efficient, even if the pattern changes. If the pattern does not change, then no updates will be left pending, and you can operate on A with any other GraphBLAS operation without the need for me to finish any work.

With GrB_assign and GxB_subassign, as a result, if A is dense then A += B_i will not take O(n^2) time at any point, either during the update or when A is used.

If, on the other hand, the pattern of A changes after each update, and you want to use A in some other GrB* function (other than GrB_assign or GrB_subassign), then it will be slow, because I don't have an incrementally updatable format (except in a limited sense, with pending upates and zombies). All of A and B_i will have to be traversed.

With GrB_eWiseAdd, A = A + B_i (using inputs A and B_i, and no accum operator), all of A and B_i will be accessed. So if B_i is very sparse compared with A, then GrB_assign or GxB_subassign will be faster.

On Sat, Dec 7, 2019 at 10:33 AM Gabor Szarnyas notifications@github.com wrote:

Hi @simpletonDL https://github.com/simpletonDL,

So the question is whether GraphBlas supports other formats suitable for incremental computing (for example DOK - dict of values, of something else).

In theory, GraphBLAS allows using of such formats, in fact, any representation can be used because objects are treated as opaque. However, incrementally updatable matrix formats are currently not implemented in SuiteSparse:GraphBLAS. There are some interesting works on the topic, e.g. faimGraph https://dl.acm.org/citation.cfm?id=3291736, Hornet https://www.researchgate.net/publication/327569751_Hornet_An_Efficient_Data_Structure_for_Dynamic_Sparse_Graphs_and_Matrices_on_GPUs, and Stinger http://www.stingergraph.com/ but none of these made it into GraphBLAS implementations yet.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/GraphBLAS/LAGraph/issues/46?email_source=notifications&email_token=AEYIIOMBL2EO5B3XEAHKCBLQXPF6NA5CNFSM4JXO7DA2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEGGKO5I#issuecomment-562866037, or unsubscribe https://github.com/notifications/unsubscribe-auth/AEYIIOPX56DMNKQU6AOSRCDQXPF6NANCNFSM4JXO7DAQ .

[simpletonDL]

Thank you for your answers!) It’s very interesting to learn how GraphBlas backend works. I really need to apply some other operations after assigning a value to the matrix, so pending updates will not help me. I can store matrix A as a sum of B_i and perform operation on (B_1 + ... + B_n) on my own.

[tgmattso]

In the GraphBLAS 1.3 specification we’ve added a new method

 GrB_Matrix_setElement()

It was designed for exactly the problem you’ve mentioned.

Of course, we can put whatever we want in the specification. It’s up to others to implement the functionality and I’m hoping over time we get the right backend data structures so the implementations are really fast. Tim Davis is pretty clever so maybe we’ll see a really fast implementation of GrB_Matrix_setElement() someday, but it may require new data structures such as the ones used in Stinger.

--The other Tim

From: simpletonDL notifications@github.com Reply-To: GraphBLAS/LAGraph reply@reply.github.com Date: Saturday, December 7, 2019 at 10:22 AM To: GraphBLAS/LAGraph LAGraph@noreply.github.com Cc: Subscribed subscribed@noreply.github.com Subject: Re: [GraphBLAS/LAGraph] Building up matrix incrementally (#46)

Thank you for your answers!) It’s very interesting to learn how GraphBlas backend works. I really need to apply some other operations after assigning a value to the matrix, so pending updates will not help me. I can store matrix A as a sum of B_i and perform operation on (B_1 + ... + B_n) on my own.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://github.com/GraphBLAS/LAGraph/issues/46?email_source=notifications&email_token=AATVME25RMRTDGRWZO7BK3TQXPSW5A5CNFSM4JXO7DA2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEGGMQRQ#issuecomment-562874438, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AATVME3MCVJQTFPJ4NMJR3LQXPSW5ANCNFSM4JXO7DAQ.