1 //------------------------------------------------------------------------------
2 // GB_AxB_saxpy3_symbolic: symbolic analysis for GB_AxB_saxpy3
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 // Symbolic analysis for C=A*B, C<M>=A*B or C<!M>=A*B, via GB_AxB_saxpy3.
11 // Coarse tasks compute nnz (C (:,j)) for each of their vectors j. Fine tasks
12 // just scatter the mask M into the hash table. This phase does not depend on
13 // the semiring, nor does it depend on the type of C, A, or B. It does access
14 // the values of M, if the mask matrix M is present and not structural.
15
16 // If B is hypersparse, C must also be hypersparse.
17 // Otherwise, C must be sparse.
18
19 // If both A and B are bitmap/full for C=A*B or C<!M>=A*B, then saxpy3 is
20 // not used. C is selected as bitmap instead.
21
22 #include "GB_AxB_saxpy3.h"
23
GB_AxB_saxpy3_symbolic(GrB_Matrix C,const GrB_Matrix M,const bool Mask_comp,const bool Mask_struct,const bool M_packed_in_place,const GrB_Matrix A,const GrB_Matrix B,GB_saxpy3task_struct * SaxpyTasks,const int ntasks,const int nfine,const int nthreads)24 void GB_AxB_saxpy3_symbolic
25 (
26 GrB_Matrix C, // Cp is computed for coarse tasks
27 const GrB_Matrix M, // mask matrix M
28 const bool Mask_comp, // M complemented, or not
29 const bool Mask_struct, // M structural, or not
30 const bool M_packed_in_place,
31 const GrB_Matrix A, // A matrix; only the pattern is accessed
32 const GrB_Matrix B, // B matrix; only the pattern is accessed
33 GB_saxpy3task_struct *SaxpyTasks, // list of tasks, and workspace
34 const int ntasks, // total number of tasks
35 const int nfine, // number of fine tasks
36 const int nthreads // number of threads
37 )
38 {
39
40 //--------------------------------------------------------------------------
41 // check inputs
42 //--------------------------------------------------------------------------
43
44 ASSERT (!GB_ZOMBIES (M)) ;
45 ASSERT (GB_JUMBLED_OK (M)) ;
46 ASSERT (!GB_PENDING (M)) ;
47
48 ASSERT (!GB_ZOMBIES (A)) ;
49 ASSERT (GB_JUMBLED_OK (A)) ;
50 ASSERT (!GB_PENDING (A)) ;
51
52 ASSERT (!GB_ZOMBIES (B)) ;
53 ASSERT (GB_JUMBLED_OK (B)) ;
54 ASSERT (!GB_PENDING (B)) ;
55
56 const bool A_is_sparse = GB_IS_SPARSE (A) ;
57 const bool A_is_hyper = GB_IS_HYPERSPARSE (A) ;
58 const bool A_is_bitmap = GB_IS_BITMAP (A) ;
59
60 const bool B_is_sparse = GB_IS_SPARSE (B) ;
61 const bool B_is_hyper = GB_IS_HYPERSPARSE (B) ;
62 const bool B_is_bitmap = GB_IS_BITMAP (B) ;
63
64 //==========================================================================
65 // phase1: count nnz(C(:,j)) for coarse tasks, scatter M for fine tasks
66 //==========================================================================
67
68 if (M == NULL)
69 {
70
71 //----------------------------------------------------------------------
72 // C = A*B
73 //----------------------------------------------------------------------
74
75 if (A_is_sparse)
76 {
77 if (B_is_sparse)
78 {
79 // both A and B are sparse
80 GB_AxB_saxpy3_sym_ss (C,
81 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
82 }
83 else if (B_is_hyper)
84 {
85 // A is sparse and B is hyper
86 GB_AxB_saxpy3_sym_sh (C,
87 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
88 }
89 else if (B_is_bitmap)
90 {
91 // A is sparse and B is bitmap
92 GB_AxB_saxpy3_sym_sb (C,
93 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
94 }
95 else
96 {
97 // A is sparse and B is full
98 GB_AxB_saxpy3_sym_sf (C,
99 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
100 }
101 }
102 else if (A_is_hyper)
103 {
104 if (B_is_sparse)
105 {
106 // A is hyper and B is sparse
107 GB_AxB_saxpy3_sym_hs (C,
108 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
109 }
110 else if (B_is_hyper)
111 {
112 // both A and B are hyper
113 GB_AxB_saxpy3_sym_hh (C,
114 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
115 }
116 else if (B_is_bitmap)
117 {
118 // A is hyper and B is bitmap
119 GB_AxB_saxpy3_sym_hb (C,
120 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
121 }
122 else
123 {
124 // A is hyper and B is full
125 GB_AxB_saxpy3_sym_hf (C,
126 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
127 }
128 }
129 else if (A_is_bitmap)
130 {
131 // C=A*B where A is bitmap; B must be sparse/hyper
132 if (B_is_sparse)
133 {
134 // A is bitmap and B is sparse
135 GB_AxB_saxpy3_sym_bs (C,
136 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
137 }
138 else
139 {
140 // A is bitmap and B is hyper
141 ASSERT (B_is_hyper) ;
142 GB_AxB_saxpy3_sym_bh (C,
143 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
144 }
145 }
146 else
147 {
148 // C=A*B where A is full; B must be sparse/hyper
149 if (B_is_sparse)
150 {
151 // A is full and B is sparse
152 GB_AxB_saxpy3_sym_fs (C,
153 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
154 }
155 else
156 {
157 // A is full and B is hyper
158 ASSERT (B_is_hyper) ;
159 GB_AxB_saxpy3_sym_fh (C,
160 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
161 }
162 }
163
164 }
165 else if (!Mask_comp)
166 {
167
168 //----------------------------------------------------------------------
169 // C<M> = A*B
170 //----------------------------------------------------------------------
171
172 if (A_is_sparse)
173 {
174 if (B_is_sparse)
175 {
176 // both A and B are sparse
177 GB_AxB_saxpy3_sym_mss (C, M, Mask_struct, M_packed_in_place,
178 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
179 }
180 else if (B_is_hyper)
181 {
182 // A is sparse and B is hyper
183 GB_AxB_saxpy3_sym_msh (C, M, Mask_struct, M_packed_in_place,
184 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
185 }
186 else if (B_is_bitmap)
187 {
188 // A is sparse and B is bitmap
189 GB_AxB_saxpy3_sym_msb (C, M, Mask_struct, M_packed_in_place,
190 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
191 }
192 else
193 {
194 // A is sparse and B is full
195 GB_AxB_saxpy3_sym_msf (C, M, Mask_struct, M_packed_in_place,
196 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
197 }
198 }
199 else if (A_is_hyper)
200 {
201 if (B_is_sparse)
202 {
203 // A is hyper and B is sparse
204 GB_AxB_saxpy3_sym_mhs (C, M, Mask_struct, M_packed_in_place,
205 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
206 }
207 else if (B_is_hyper)
208 {
209 // both A and B are hyper
210 GB_AxB_saxpy3_sym_mhh (C, M, Mask_struct, M_packed_in_place,
211 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
212 }
213 else if (B_is_bitmap)
214 {
215 // A is hyper and B is bitmap
216 GB_AxB_saxpy3_sym_mhb (C, M, Mask_struct, M_packed_in_place,
217 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
218 }
219 else
220 {
221 // A is hyper and B is full
222 GB_AxB_saxpy3_sym_mhf (C, M, Mask_struct, M_packed_in_place,
223 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
224 }
225 }
226 else if (A_is_bitmap)
227 {
228 if (B_is_sparse)
229 {
230 // A is bitmap and B is sparse
231 GB_AxB_saxpy3_sym_mbs (C, M, Mask_struct, M_packed_in_place,
232 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
233 }
234 else if (B_is_hyper)
235 {
236 // A is bitmap and B is hyper
237 GB_AxB_saxpy3_sym_mbh (C, M, Mask_struct, M_packed_in_place,
238 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
239 }
240 else if (B_is_bitmap)
241 {
242 // both A and B are bitmap
243 GB_AxB_saxpy3_sym_mbb (C, M, Mask_struct, M_packed_in_place,
244 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
245 }
246 else
247 {
248 // A is bitmap and B is full
249 GB_AxB_saxpy3_sym_mbf (C, M, Mask_struct, M_packed_in_place,
250 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
251 }
252 }
253 else
254 {
255 if (B_is_sparse)
256 {
257 // A is full and B is sparse
258 GB_AxB_saxpy3_sym_mfs (C, M, Mask_struct, M_packed_in_place,
259 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
260 }
261 else if (B_is_hyper)
262 {
263 // A is full and B is hyper
264 GB_AxB_saxpy3_sym_mfh (C, M, Mask_struct, M_packed_in_place,
265 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
266 }
267 else if (B_is_bitmap)
268 {
269 // A is full and B is bitmap
270 GB_AxB_saxpy3_sym_mfb (C, M, Mask_struct, M_packed_in_place,
271 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
272 }
273 else
274 {
275 // both A and B are full
276 GB_AxB_saxpy3_sym_mff (C, M, Mask_struct, M_packed_in_place,
277 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
278 }
279 }
280
281 }
282 else
283 {
284
285 //----------------------------------------------------------------------
286 // C<!M> = A*B
287 //----------------------------------------------------------------------
288
289 if (A_is_sparse)
290 {
291 if (B_is_sparse)
292 {
293 // both A and B are sparse
294 GB_AxB_saxpy3_sym_nss (C, M, Mask_struct, M_packed_in_place,
295 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
296 }
297 else if (B_is_hyper)
298 {
299 // A is sparse and B is hyper
300 GB_AxB_saxpy3_sym_nsh (C, M, Mask_struct, M_packed_in_place,
301 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
302 }
303 else if (B_is_bitmap)
304 {
305 // A is sparse and B is bitmap
306 GB_AxB_saxpy3_sym_nsb (C, M, Mask_struct, M_packed_in_place,
307 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
308 }
309 else
310 {
311 // A is sparse and B is full
312 GB_AxB_saxpy3_sym_nsf (C, M, Mask_struct, M_packed_in_place,
313 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
314 }
315 }
316 else if (A_is_hyper)
317 {
318 if (B_is_sparse)
319 {
320 // A is hyper and B is sparse
321 GB_AxB_saxpy3_sym_nhs (C, M, Mask_struct, M_packed_in_place,
322 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
323 }
324 else if (B_is_hyper)
325 {
326 // both A and B are hyper
327 GB_AxB_saxpy3_sym_nhh (C, M, Mask_struct, M_packed_in_place,
328 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
329 }
330 else if (B_is_bitmap)
331 {
332 // A is hyper and B is bitmap
333 GB_AxB_saxpy3_sym_nhb (C, M, Mask_struct, M_packed_in_place,
334 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
335 }
336 else
337 {
338 // A is hyper and B is full
339 GB_AxB_saxpy3_sym_nhf (C, M, Mask_struct, M_packed_in_place,
340 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
341 }
342 }
343 else if (A_is_bitmap)
344 {
345 // C<!M>=A*B where A is bitmap; B must be sparse/hyper
346 if (B_is_sparse)
347 {
348 // A is bitmap and B is sparse
349 GB_AxB_saxpy3_sym_nbs (C, M, Mask_struct, M_packed_in_place,
350 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
351 }
352 else
353 {
354 // A is bitmap and B is hyper
355 ASSERT (B_is_hyper) ;
356 GB_AxB_saxpy3_sym_nbh (C, M, Mask_struct, M_packed_in_place,
357 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
358 }
359 }
360 else
361 {
362 // C<!M>=A*B where A is full; B must be sparse/hyper
363 if (B_is_sparse)
364 {
365 // A is full and B is sparse
366 GB_AxB_saxpy3_sym_nfs (C, M, Mask_struct, M_packed_in_place,
367 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
368 }
369 else
370 {
371 // A is full and B is hyper
372 ASSERT (B_is_hyper) ;
373 GB_AxB_saxpy3_sym_nfh (C, M, Mask_struct, M_packed_in_place,
374 A, B, SaxpyTasks, ntasks, nfine, nthreads) ;
375 }
376 }
377 }
378 }
379
380