search

GraphBLAS / LAGraph

This is a library plus a test harness for collecting algorithms that use the GraphBLAS. For test coverage reports, see https://graphblas.org/LAGraph/ . Documentation: https://lagraph.readthedocs.org
Other
228 stars 61 forks source link

CSR should be better than CSC; also dropped an unnecessary variable. #194

Closed pcostanza closed 1 year ago

pcostanza commented 1 year ago

The SuiteSparse:GraphBLAS manual states that CSR is the default format, so it should be better to unpack in CSR rather than CSC (and it doesn't matter which of the two to choose in this algorithm). Also, there was an unused variable declaration that is now removed.

pcostanza commented 1 year ago

I added another small improvement to this pull request: It's not necessary to have both the graph and the multigraph in the asymmetric case. This simplifies the code even further. It also seems to perform a little bit better.

szarnyasg commented 1 year ago

Looks good! I ran the LCC algorithm on the Graphalytics size "S" data set using this new algorithm and it passed validaiton for all of the graphs.

23:46 [INFO ] [BenchmarkRun [r650838, LCC[none], graph500-22, timeout=9000s]] => succeed, T_l=22.431s, T_m=116.480s, T_p=111.708s.
23:46 [INFO ] [BenchmarkRun [r668675, LCC[none], dota-league, timeout=9000s]] => succeed, T_l=15.610s, T_m=183.085s, T_p=182.794s.
23:46 [INFO ] [BenchmarkRun [r746433, LCC[none], datagen-7_9-fb, timeout=9000s]] => succeed, T_l=30.820s, T_m=29.025s, T_p=25.768s.
23:46 [INFO ] [BenchmarkRun [r900614, LCC[none], datagen-7_8-zf, timeout=9000s]] => succeed, T_l=18.181s, T_m=42.724s, T_p=2.548s.
23:46 [INFO ] [BenchmarkRun [r576847, LCC[none], datagen-7_7-zf, timeout=9000s]] => succeed, T_l=14.478s, T_m=32.747s, T_p=2.141s.
23:46 [INFO ] [BenchmarkRun [r474899, LCC[none], datagen-7_6-fb, timeout=9000s]] => succeed, T_l=17.398s, T_m=13.501s, T_p=11.613s.
23:46 [INFO ] [BenchmarkRun [r599632, LCC[none], datagen-7_5-fb, timeout=9000s]] => succeed, T_l=11.776s, T_m=10.566s, T_p=9.152s.

Using GxB_PLUS_SECOND_FP64 instead of GrB_PLUS_TIMES_SEMIRING_FP64 is likely giving the algorithm a noticeable performance boost.