search

rohitvarkey / GraphChallenge.jl

MIT License
2 stars 0 forks source link

Linear algebra information #17

Open jpfairbanks opened 6 years ago

jpfairbanks commented 6 years ago

Geoff had some good ideas about our method.

This is a big problem in Algebraic Multigrid if C is a matrix mapping vertices to communities. Then we need to update C but read from a matrix C'AC. So our write optimized DS is a vector for C. and our Read optimized DS is a CSC for C'AC, but we will calculate a sparse update to C'AC by using the formula:

(C+D)'A(C+D) = C'AC + D'AC + C'AD + D'AD where for undirected graphs we can exploit symmetry.

We can batch updates up to the point where Time to compute (C+D)'A(C+D) < Time to compute C'AC + D'AC + C'AD + D'AD

We should compare with the streaming of A' = A+D where (C+d)'(A+D)(C+d)

jpfairbanks commented 6 years ago

We should store C as a vector and D (the change in communities as a 3xn matrix of [vertexID from to] with a length field to enable memory reuse.

The look at computing rows and columns of C'AC + D'AC + C'AD + D'AD on demand. I think we will need to reaccumulate C'AC into a SparseMatrix after each update phase.