1 //------------------------------------------------------------------------------
2 // GB_emult_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_emult, or if C=A.*B should be computed without the mask, and the mask
14 // applied later.
15
16 // If C should be constructed as hypersparse or sparse, this function simply
17 // returns GxB_SPARSE. The final determination is made later.
18
19 // If both A and B are full, then GB_ewise can call GB_add instead of GB_emult.
20 // This is the only case where the eWise multiply can produce a full C matrix,
21 // and as a result, there is no need for a GB_emult to handle the case when
22 // C is full.
23
24 #include "GB_emult.h"
25
GB_emult_sparsity(bool * apply_mask,int * ewise_method,const GrB_Matrix M,const bool Mask_comp,const GrB_Matrix A,const GrB_Matrix B)26 int GB_emult_sparsity // return the sparsity structure for C
27 (
28 // output:
29 bool *apply_mask, // if true then mask will be applied by GB_emult
30 int *ewise_method, // method to use
31 // input:
32 const GrB_Matrix M, // optional mask for C, unused if NULL
33 const bool Mask_comp, // if true, use !M
34 const GrB_Matrix A, // input A matrix
35 const GrB_Matrix B // input B matrix
36 )
37 {
38
39 //--------------------------------------------------------------------------
40 // determine the sparsity of C
41 //--------------------------------------------------------------------------
42
43 // Unless deciding otherwise, use the mask if it appears
44 (*apply_mask) = (M != NULL) ;
45 int C_sparsity ;
46
47 // In the table below, sparse/hypersparse are listed as "sparse". If C is
48 // listed as sparse, it will become sparse or hypersparse, depending on the
49 // method.
50
51 bool M_is_sparse_or_hyper = GB_IS_SPARSE (M) || GB_IS_HYPERSPARSE (M) ;
52 bool A_is_sparse_or_hyper = GB_IS_SPARSE (A) || GB_IS_HYPERSPARSE (A) ;
53 bool B_is_sparse_or_hyper = GB_IS_SPARSE (B) || GB_IS_HYPERSPARSE (B) ;
54
55 bool A_is_full = GB_as_if_full (A) ;
56 bool B_is_full = GB_as_if_full (B) ;
57
58 if (M == NULL)
59 {
60
61 // ------------------------------------------
62 // C = A .* B
63 // ------------------------------------------
64 // sparse . sparse sparse (method: 01)
65 // sparse . sparse bitmap (method: 02a)
66 // sparse . sparse full (method: 02a)
67 // sparse . bitmap sparse (method: 02b)
68 // bitmap . bitmap bitmap (method: 05)
69 // bitmap . bitmap full (method: 05)
70 // sparse . full sparse (method: 02b)
71 // bitmap . full bitmap (method: 05)
72 // full . full full (must use GB_add)
73
74 if (A_is_sparse_or_hyper && B_is_sparse_or_hyper)
75 {
76 // C=A.*B with A and B both sparse/hyper, C sparse
77 C_sparsity = GxB_SPARSE ;
78 (*ewise_method) = GB_EMULT_METHOD_01 ;
79 }
80 else if (A_is_sparse_or_hyper)
81 {
82 // C=A.*B with A sparse/hyper, B bitmap/full
83 C_sparsity = GxB_SPARSE ;
84 (*ewise_method) = GB_EMULT_METHOD_02A ;
85 }
86 else if (B_is_sparse_or_hyper)
87 {
88 // C=A.*B with B sparse/hyper, A bitmap/full
89 C_sparsity = GxB_SPARSE ;
90 (*ewise_method) = GB_EMULT_METHOD_02B ;
91 }
92 else if (A_is_full && B_is_full)
93 {
94 // C=A.*B with A and B full, must use GB_add since GB_emult does
95 // not handle the case when C is full.
96 C_sparsity = GxB_FULL ;
97 (*ewise_method) = GB_EMULT_METHOD_ADD ;
98 }
99 else
100 {
101 // C=A.*B, otherwise, C bitmap
102 C_sparsity = GxB_BITMAP ;
103 (*ewise_method) = GB_EMULT_METHOD_05 ;
104 }
105
106 }
107 else if (!Mask_comp)
108 {
109
110 if (M_is_sparse_or_hyper)
111 {
112
113 // ------------------------------------------
114 // C <M>= A .* B
115 // ------------------------------------------
116 // sparse sparse sparse sparse (method: 01)
117 // sparse sparse sparse bitmap (04a or 02a)
118 // sparse sparse sparse full (04a or 02a)
119 // sparse sparse bitmap sparse (04b or 02b)
120 // sparse sparse bitmap bitmap (method: 03)
121 // sparse sparse bitmap full (method: 03)
122 // sparse sparse full sparse (04b or 02b)
123 // sparse sparse full bitmap (method: 03)
124 // sparse sparse full full (GB_add or 03)
125
126 // C<M>=A.*B with M sparse/hyper, C sparse
127 C_sparsity = GxB_SPARSE ;
128
129 if (A_is_sparse_or_hyper && B_is_sparse_or_hyper)
130 {
131 // C<M>=A.*B with A and B both sparse/hyper, C sparse
132 // apply the mask only if it is extremely sparse
133 (*apply_mask) = GB_MASK_VERY_SPARSE (8, M, A, B) ;
134 (*ewise_method) = GB_EMULT_METHOD_01 ;
135 }
136 else if (A_is_sparse_or_hyper)
137 {
138 // C<M>=A.*B with A sparse/hyper, B bitmap/full
139 // apply the mask only if it is very sparse
140 if (GB_MASK_VERY_SPARSE (2, M, A, B))
141 {
142 // C<M>=A.*B with A sparse/hyper, B bitmap/full
143 (*apply_mask) = true ;
144 (*ewise_method) = GB_EMULT_METHOD_04A ;
145 }
146 else
147 {
148 // C<M>=A.*B with A sparse/hyper, B bitmap/full, mask later
149 (*apply_mask) = false ;
150 (*ewise_method) = GB_EMULT_METHOD_02A ;
151 }
152 }
153 else if (B_is_sparse_or_hyper)
154 {
155 // C<M>=A.*B with B sparse/hyper, A bitmap/full
156 // apply the mask only if it is very sparse
157 if (GB_MASK_VERY_SPARSE (2, M, A, B))
158 {
159 // C<M>=A.*B with A bitmap/full, B sparse/hyper
160 (*apply_mask) = true ;
161 (*ewise_method) = GB_EMULT_METHOD_04B ;
162 }
163 else
164 {
165 // C<M>=A.*B with A bitmap/full, B sparse/hyper, mask later
166 (*apply_mask) = false ;
167 (*ewise_method) = GB_EMULT_METHOD_02B ;
168 }
169 }
170 else if (A_is_full && B_is_full)
171 {
172 // C=A.*B with A and B full
173 // (*ewise_method) = GB_EMULT_METHOD_ADD ; this is possible
174 (*ewise_method) = GB_EMULT_METHOD_03 ;
175 }
176 else
177 {
178 // C=A.*B, otherwise
179 (*ewise_method) = GB_EMULT_METHOD_03 ;
180 }
181
182 }
183 else
184 {
185
186 // ------------------------------------------
187 // C <M> = A .* B
188 // ------------------------------------------
189 // sparse bitmap sparse sparse (method: 01)
190 // sparse bitmap sparse bitmap (method: 02a)
191
192 // sparse bitmap sparse full (method: 02a)
193 // sparse bitmap bitmap sparse (method: 02b)
194 // bitmap bitmap bitmap bitmap (method: 07)
195 // bitmap bitmap bitmap full (method: 07)
196 // sparse bitmap full sparse (method: 02b)
197 // bitmap bitmap full bitmap (method: 07)
198 // bitmap bitmap full full (GB_add or 07)
199
200 // ------------------------------------------
201 // C <M> = A .* B
202 // ------------------------------------------
203 // sparse full sparse sparse (method: 01)
204 // sparse full sparse bitmap (method: 02a)
205 // sparse full sparse full (method: 02a)
206 // sparse full bitmap sparse (method: 02b)
207 // bitmap full bitmap bitmap (method: 07)
208 // bitmap full bitmap full (method: 07)
209 // sparse full full sparse (method: 02b)
210 // bitmap full full bitmap (method: 07)
211 // bitmap full full full (GB_add or 07)
212
213 if (A_is_sparse_or_hyper && B_is_sparse_or_hyper)
214 {
215 // C<M>=A.*B with A and B both sparse/hyper, C sparse
216 C_sparsity = GxB_SPARSE ;
217 (*ewise_method) = GB_EMULT_METHOD_01 ;
218 }
219 else if (A_is_sparse_or_hyper)
220 {
221 // C<M>=A.*B with A sparse/hyper, B bitmap/full
222 C_sparsity = GxB_SPARSE ;
223 (*ewise_method) = GB_EMULT_METHOD_02A ;
224 }
225 else if (B_is_sparse_or_hyper)
226 {
227 // C<M>=A.*B with B sparse/hyper, A bitmap/full
228 C_sparsity = GxB_SPARSE ;
229 (*ewise_method) = GB_EMULT_METHOD_02B ;
230 }
231 else if (A_is_full && B_is_full)
232 {
233 // C<M>=A.*B with A and B full
234 C_sparsity = GxB_BITMAP ;
235 // (*ewise_method) = GB_EMULT_METHOD_ADD ; this is possible
236 (*ewise_method) = GB_EMULT_METHOD_07 ;
237 }
238 else
239 {
240 // C=A.*B, otherwise, C bitmap
241 C_sparsity = GxB_BITMAP ;
242 (*ewise_method) = GB_EMULT_METHOD_07 ;
243 }
244 }
245
246 }
247 else // Mask_comp
248 {
249
250 if (M_is_sparse_or_hyper)
251 {
252
253 // ------------------------------------------
254 // C <!M>= A .* B
255 // ------------------------------------------
256 // sparse sparse sparse sparse (01: M later)
257 // sparse sparse sparse bitmap (02a: M later)
258 // sparse sparse sparse full (02a: M later)
259 // sparse sparse bitmap sparse (02b: M later)
260 // bitmap sparse bitmap bitmap (method: 06)
261 // bitmap sparse bitmap full (method: 06)
262 // sparse sparse full sparse (02b: M later)
263 // bitmap sparse full bitmap (method: 06)
264 // bitmap sparse full full (GB_add or 06)
265
266 if (A_is_sparse_or_hyper && B_is_sparse_or_hyper)
267 {
268 // C<!M>=A.*B with A and B sparse/hyper, C sparse, M later
269 (*apply_mask) = false ;
270 C_sparsity = GxB_SPARSE ;
271 (*ewise_method) = GB_EMULT_METHOD_01 ;
272 }
273 else if (A_is_sparse_or_hyper)
274 {
275 // C<!M>=A.*B with A sparse/hyper, B bitmap/full, M later
276 (*apply_mask) = false ;
277 C_sparsity = GxB_SPARSE ;
278 (*ewise_method) = GB_EMULT_METHOD_02A ;
279 }
280 else if (B_is_sparse_or_hyper)
281 {
282 // C<!M>=A.*B with B sparse/hyper, A bitmap/full, M later
283 (*apply_mask) = false ;
284 C_sparsity = GxB_SPARSE ;
285 (*ewise_method) = GB_EMULT_METHOD_02B ;
286 }
287 else if (A_is_full && B_is_full)
288 {
289 // C<!M>=A.*B with A and B full
290 C_sparsity = GxB_BITMAP ;
291 // (*ewise_method) = GB_EMULT_METHOD_ADD ; this is possible
292 (*ewise_method) = GB_EMULT_METHOD_06 ;
293 }
294 else
295 {
296 // C<!M>=A.*B, otherwise, C bitmap
297 C_sparsity = GxB_BITMAP ;
298 (*ewise_method) = GB_EMULT_METHOD_06 ;
299 }
300
301 }
302 else
303 {
304
305 // ------------------------------------------
306 // C <!M> = A .* B
307 // ------------------------------------------
308 // sparse bitmap sparse sparse (method: 01)
309 // sparse bitmap sparse bitmap (method: 02a)
310 // sparse bitmap sparse full (method: 02a)
311 // sparse bitmap bitmap sparse (method: 02b)
312 // bitmap bitmap bitmap bitmap (method: 07)
313 // bitmap bitmap bitmap full (method: 07)
314 // sparse bitmap full sparse (method: 02b)
315 // bitmap bitmap full bitmap (method: 07)
316 // bitmap bitmap full full (GB_add or 07)
317
318 // ------------------------------------------
319 // C <!M> = A .* B
320 // ------------------------------------------
321 // sparse full sparse sparse (method: 01)
322 // sparse full sparse bitmap (method: 02a)
323 // sparse full sparse full (method: 02a)
324 // sparse full bitmap sparse (method: 02b)
325 // bitmap full bitmap bitmap (method: 07)
326 // bitmap full bitmap full (method: 07)
327 // sparse full full sparse (method: 02b)
328 // bitmap full full bitmap (method: 07)
329 // bitmap full full full (GB_add or 07)
330
331 if (A_is_sparse_or_hyper && B_is_sparse_or_hyper)
332 {
333 // C<!M>=A.*B with A and B both sparse/hyper, C sparse
334 C_sparsity = GxB_SPARSE ;
335 (*ewise_method) = GB_EMULT_METHOD_01 ;
336 }
337 else if (A_is_sparse_or_hyper)
338 {
339 // C<!M>=A.*B with A sparse/hyper, B bitmap/full
340 C_sparsity = GxB_SPARSE ;
341 (*ewise_method) = GB_EMULT_METHOD_02A ;
342 }
343 else if (B_is_sparse_or_hyper)
344 {
345 // C<!M>=A.*B with B sparse/hyper, A bitmap/full
346 C_sparsity = GxB_SPARSE ;
347 (*ewise_method) = GB_EMULT_METHOD_02B ;
348 }
349 else if (A_is_full && B_is_full)
350 {
351 // C<!M>=A.*B with A and B full
352 C_sparsity = GxB_BITMAP ;
353 // (*ewise_method) = GB_EMULT_METHOD_ADD ; this is possible
354 (*ewise_method) = GB_EMULT_METHOD_07 ;
355 }
356 else
357 {
358 // C<!M>=A.*B, otherwise, C bitmap
359 C_sparsity = GxB_BITMAP ;
360 (*ewise_method) = GB_EMULT_METHOD_07 ;
361 }
362 }
363 }
364
365 //--------------------------------------------------------------------------
366 // return result
367 //--------------------------------------------------------------------------
368
369 return (C_sparsity) ;
370 }
371
372