1 //------------------------------------------------------------------------------
2 // GB_AxB_dot2_control.c: determine when to use GB_AxB_dot2
3 //------------------------------------------------------------------------------
4
5 // SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved.
6 // SPDX-License-Identifier: Apache-2.0
7
8 //------------------------------------------------------------------------------
9
10 // C=A'*B, C<M>=A'*B, or C<!M>=A'*B where C is constructed in bitmap format.
11 // C must be small and likely very dense.
12
13 #include "GB_mxm.h"
14
GB_AxB_dot2_control(const GrB_Matrix A,const GrB_Matrix B,GB_Context Context)15 bool GB_AxB_dot2_control // true: use dot2, false: use saxpy
16 (
17 const GrB_Matrix A,
18 const GrB_Matrix B,
19 GB_Context Context
20 )
21 {
22
23 //--------------------------------------------------------------------------
24 // C = A'*B is very efficient if A and/or B are full or bitmap
25 //--------------------------------------------------------------------------
26
27 if (GB_IS_FULL (A) || GB_IS_BITMAP (A) ||
28 GB_IS_FULL (B) || GB_IS_BITMAP (B))
29 {
30 return (true) ;
31 }
32
33 //--------------------------------------------------------------------------
34 // both A and B are sparse or hyper
35 //--------------------------------------------------------------------------
36
37 // Notation: C=A'*B where all 3 matrices are CSC. This might be C=A*B'
38 // where all 3 matrices are CSR, equivalently. The comments here assume
39 // CSC, but this method is CSC/CSR agnostic.
40
41 double anz = GB_NNZ (A) ; // # of entries in A
42 double bnz = GB_NNZ (B) ; // # of entries in B
43 if (A->nvec_nonempty < 0) A->nvec_nonempty = GB_nvec_nonempty (A, Context) ;
44 if (B->nvec_nonempty < 0) B->nvec_nonempty = GB_nvec_nonempty (B, Context) ;
45 double anvec = A->nvec_nonempty ;
46 double bnvec = B->nvec_nonempty ;
47 double avlen = A->vlen ;
48 ASSERT (avlen == B->vlen) ;
49 double cnz = (anvec * bnvec) ; // size of the C bitmap
50 double row_degree = anz / GB_IMAX (avlen, 1) ;
51 double col_degree = anz / GB_IMAX (anvec, 1) ;
52
53 if (cnz > anz + bnz)
54 {
55 // The C bitmap is too big, use saxpy and construct C as sparse
56 GBURBLE ("(C large: use saxpy C=(A')*B) ") ;
57 return (false) ;
58 }
59
60 if ((anz + bnz > 10000 * cnz) || (cnz <= 100))
61 {
62 // The C bitmap is very small compared with A and B, so use dot2
63 // and construct C as bitmap
64 GBURBLE ("(C tiny: dot) ") ;
65 return (true) ;
66 }
67
68 // average # of entries in each row and column of A (assuming A is CSC)
69 if (row_degree < 0.125 && col_degree > 1200)
70 {
71 // If AT=A' is computed, it will have mostly empty vectors (the
72 // row_degree of A), so do not transpose it. If the fraction of
73 // populated vectors in AT is very low (< 0.0625 by default), then AT
74 // will become hypersparse, and this slows down the saxpy method. If
75 // the vectors (col_degree) have lots of entries, then dot2 is
76 // efficient in this case. If both conditions hold, use dot2 and
77 // compute C as bitmap.
78 GBURBLE ("(A' implicit: dot) ") ;
79 return (true) ;
80 }
81
82 // if none of the above rules trigger, use saxpy
83 GBURBLE ("(saxpy C=(A')*B) ") ;
84 return (false) ;
85 }
86
87