1 //------------------------------------------------------------------------------
2 // GB_add_sparsity: determine the sparsity structure for C<M or !M>=A+B
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 // Determines the sparsity structure for C, for computing C=A+B, C<M>=A+B,
11 // or C<!M>=A+B, based on the sparsity structures of M, A, and B, and whether
12 // or not M is complemented. It also decides if the mask M should be applied
13 // by GB_add, or if C=A+B should be computed without the mask, and the mask
14 // applied later.
15
16 // If C should be hypersparse or sparse, on output, this function simply
17 // returns GxB_SPARSE. The final determination is made by GB_add_phase0.
18
19 #include "GB_add.h"
20
GB_add_sparsity(bool * apply_mask,const GrB_Matrix M,const bool Mask_comp,const GrB_Matrix A,const GrB_Matrix B)21 int GB_add_sparsity // return the sparsity structure for C
22 (
23 // output:
24 bool *apply_mask, // if true then mask will be applied by GB_add
25 // input:
26 const GrB_Matrix M, // optional mask for C, unused if NULL
27 const bool Mask_comp, // if true, use !M
28 const GrB_Matrix A, // input A matrix
29 const GrB_Matrix B // input B matrix
30 )
31 {
32
33 //--------------------------------------------------------------------------
34 // determine the sparsity of C
35 //--------------------------------------------------------------------------
36
37 // Unless deciding otherwise, use the mask if it appears
38 (*apply_mask) = (M != NULL) ;
39
40 int C_sparsity ;
41
42 // In the table below, sparse/hypersparse are listed as "sparse". If C is
43 // listed as sparse: it is hypersparse if M is hypersparse (and not
44 // complemented), or if both A and B are hypersparse, and sparse otherwise.
45 // This is determined by GB_add_phase0. If M is complemented and all 4
46 // matrices are sparse, then C=A+B is always computed. So C is hypersparse
47 // if both A and B are hypersparse, in this case.
48
49 bool M_is_sparse_or_hyper = GB_IS_SPARSE (M) || GB_IS_HYPERSPARSE (M) ;
50 bool A_is_sparse_or_hyper = GB_IS_SPARSE (A) || GB_IS_HYPERSPARSE (A) ;
51 bool B_is_sparse_or_hyper = GB_IS_SPARSE (B) || GB_IS_HYPERSPARSE (B) ;
52 bool A_is_full = GB_as_if_full (A) ;
53 bool B_is_full = GB_as_if_full (B) ;
54
55 if (M == NULL)
56 {
57
58 // ------------------------------------------
59 // C = A + B
60 // ------------------------------------------
61 // sparse . sparse sparse
62 // bitmap . sparse bitmap
63 // full . sparse full
64 // bitmap . bitmap sparse
65 // bitmap . bitmap bitmap
66 // full . bitmap full
67 // full . full sparse
68 // full . full bitmap
69 // full . full full
70
71 if (A_is_sparse_or_hyper && B_is_sparse_or_hyper)
72 {
73 C_sparsity = GxB_SPARSE ;
74 }
75 else if (A_is_full || B_is_full)
76 {
77 C_sparsity = GxB_FULL ;
78 }
79 else
80 {
81 C_sparsity = GxB_BITMAP ;
82 }
83
84 }
85 else if (!Mask_comp)
86 {
87
88 if (M_is_sparse_or_hyper)
89 {
90
91 // ------------------------------------------
92 // C <M> = A + B
93 // ------------------------------------------
94 // sparse sparse sparse sparse
95 // sparse sparse sparse bitmap
96 // sparse sparse sparse full
97 // sparse sparse bitmap sparse
98 // sparse sparse bitmap bitmap
99 // sparse sparse bitmap full
100 // sparse sparse full sparse
101 // sparse sparse full bitmap
102 // sparse sparse full full
103
104 // TODO: if M and A and/or B are all sparse, use the mask only if:
105 // 8*nnz(M) <= ( (A sparse or hyper) ? nnz(A) : 0 ) +
106 // ( (B sparse or hyper) ? nnz(B) : 0 )
107 // if A and B are both bitmap or full, then always use the mask.
108 // GB_sparse_add_template handles this case, but exploiting the
109 // mask can be asympotically slow, when C and M are sparse, and A
110 // and/or B are sparse.
111
112 // TODO: check the sparse_mask_is_easy condition: use M
113 // if Mask_struct is true, A is not bitmap, B is not bitmap,
114 // and one of the 3 conditions holds. In this case, ignore the
115 // 8*nnz(M) <= (...) test, and always use the mask.
116
117 // TODO: See the GB_MASK_VERY_SPARSE (M, A, B) macro for this test.
118
119 C_sparsity = GxB_SPARSE ;
120
121 }
122 else
123 {
124
125 // ------------------------------------------
126 // C <M> = A + B
127 // ------------------------------------------
128 // sparse bitmap sparse sparse
129 // bitmap bitmap sparse bitmap
130 // bitmap bitmap sparse full
131 // bitmap bitmap bitmap sparse
132 // bitmap bitmap bitmap bitmap
133 // bitmap bitmap bitmap full
134 // bitmap bitmap full sparse
135 // bitmap bitmap full bitmap
136 // bitmap bitmap full full
137
138 // ------------------------------------------
139 // C <M> = A + B
140 // ------------------------------------------
141 // sparse full sparse sparse
142 // bitmap full sparse bitmap
143 // bitmap full sparse full
144 // bitmap full bitmap sparse
145 // bitmap full bitmap bitmap
146 // bitmap full bitmap full
147 // bitmap full full sparse
148 // bitmap full full bitmap
149 // bitmap full full full
150
151 // The mask is very efficient to use in the case, when C is sparse.
152
153 if (A_is_sparse_or_hyper && B_is_sparse_or_hyper)
154 {
155 C_sparsity = GxB_SPARSE ;
156 }
157 else
158 {
159 C_sparsity = GxB_BITMAP ;
160 }
161 }
162
163 }
164 else // Mask_comp
165 {
166
167 // ------------------------------------------
168 // C <!M> = A + B
169 // ------------------------------------------
170 // sparse sparse sparse sparse (mask later)
171 // bitmap sparse sparse bitmap
172 // bitmap sparse sparse full
173 // bitmap sparse bitmap sparse
174 // bitmap sparse bitmap bitmap
175 // bitmap sparse bitmap full
176 // bitmap sparse full sparse
177 // bitmap sparse full bitmap
178 // bitmap sparse full full
179
180 // ------------------------------------------
181 // C <!M> = A + B
182 // ------------------------------------------
183 // sparse bitmap sparse sparse
184 // bitmap bitmap sparse bitmap
185 // bitmap bitmap sparse full
186 // bitmap bitmap bitmap sparse
187 // bitmap bitmap bitmap bitmap
188 // bitmap bitmap bitmap full
189 // bitmap bitmap full sparse
190 // bitmap bitmap full bitmap
191 // bitmap bitmap full full
192
193 // ------------------------------------------
194 // C <!M> = A + B
195 // ------------------------------------------
196 // sparse full sparse sparse
197 // bitmap full sparse bitmap
198 // bitmap full sparse full
199 // bitmap full bitmap sparse
200 // bitmap full bitmap bitmap
201 // bitmap full bitmap full
202 // bitmap full full sparse
203 // bitmap full full bitmap
204 // bitmap full full full
205
206 if (A_is_sparse_or_hyper && B_is_sparse_or_hyper)
207 {
208 // !M must be applied later if all 4 matrices are sparse or
209 // hypersparse, since the GB_sparse_add_template method does not
210 // handle this case. See the "(mask later)" above. The method can
211 // construct a sparse/hyper C with !M as bitmap or full.
212 C_sparsity = GxB_SPARSE ;
213 (*apply_mask) = !M_is_sparse_or_hyper ;
214 }
215 else
216 {
217 // !M can be applied now, or later. TODO: If M is sparse and
218 // either A or B are sparse/hyper, then there might be cases where
219 // !M should be applied later, for better performance.
220 C_sparsity = GxB_BITMAP ;
221 }
222 }
223
224 return (C_sparsity) ;
225 }
226
227