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
225
stars
59
forks
source link
Performance improvements for coarsening/matching #227
Added push/pull optimization for one mxv, cutting down between 5-10% of the cost of one coarsening step. The major cost in this algorithm, according to the burble, is coming from the LAGraph_IncidenceMatrix function. The first GrB_Matrix_build call in this function takes about 17% of the runtime of one coarsening step. Other sources of significant cost include the mxms used to do $SAS^T$, as well as transposing $E$ into $E^T$
Changes to LAGraph_MaximalMatching:
Do not compute $E^T$ inside the algorithm, instead take it as input. Most of the times, if $E$ is computed then $E^T$ will also be needed/computed by the user, so we can avoid this relatively expensive computation here. This cuts down between 5-10% of the cost of a single coarsening step.
Other changes:
Updates to comments in custom CPP tests
Cleaned up OPTIMIZE_PUSH_PULL checking in maximal matching code
Updated calls to maximal matching to include $E^T$ on input
Changes to
LAGraph_Coarsen_Matching
:LAGraph_IncidenceMatrix
function. The firstGrB_Matrix_build
call in this function takes about 17% of the runtime of one coarsening step. Other sources of significant cost include the mxms used to do $SAS^T$, as well as transposing $E$ into $E^T$Changes to
LAGraph_MaximalMatching
:Other changes:
OPTIMIZE_PUSH_PULL
checking in maximal matching code