search

DrTimothyAldenDavis / GraphBLAS

SuiteSparse:GraphBLAS: graph algorithms in the language of linear algebra. For production: (default) STABLE branch. Code development: ask me for the right branch before submitting a PR. video intro: https://youtu.be/Tj5y6d7FegI .
http://faculty.cse.tamu.edu/davis/GraphBLAS.html
Other
364 stars 63 forks source link

Time Complexities of GrB_vxm and GrB_Matrix_extract #15

Closed victorstewart closed 4 years ago

victorstewart commented 4 years ago

What are the time complexities of GrB_vxm and GrB_Matrix_extract?

When conducting a BFS, I'm curious if it's faster to extract a submatrix and then LOR across the rows, than it is to multiply.

DrTimothyAldenDavis commented 4 years ago

Vxm is faster. It will be faster still once I release v4. See the draft LAGraph_bfs_parent. And the new bitmap data structure in the draft v4 of SuiteSparse:GraphBLAS. I’m seeing some great speedups as compared to v3.3.x.

The time complexity depends on the method and semiring. The ANY monoid is asymptotically faster than the others. A lot faster. With vxm and a dense matrix and dense vector the time is O(n) using the ANY monoid in the “pull” direction. It would be O(n^2) with any other monoid.

On Thu, Aug 6, 2020 at 2:48 PM Victor Stewart notifications@github.com wrote:

What are the time complexities of GrB_vxm and GrB_Matrix_extract?

When conducting a BFS, I'm curious if it's faster to extract a submatrix and then LOR across the rows, than it is to multiply.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/DrTimothyAldenDavis/GraphBLAS/issues/15, or unsubscribe https://github.com/notifications/unsubscribe-auth/AEYIIOOBVLZC5FUDZOEDJMTR7MCIDANCNFSM4PW5LVUQ .

-- Sent from Gmail Mobile

victorstewart commented 4 years ago

Wonderful. And I'll check out the v4 spec thanks.

And thanks for your always thorough responses. I really appreciate them. Without GraphBLAS I never would've been able to pull off the gymnastics I'm doing in the hottest realtime path of my application.