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