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
|
//------------------------------------------------------------------------------
// GB_reduce_to_vector: reduce a matrix to a vector using a monoid
//------------------------------------------------------------------------------
// SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2025, All Rights Reserved.
// SPDX-License-Identifier: Apache-2.0
//------------------------------------------------------------------------------
// C<M> = accum (C,reduce(A)) where C is n-by-1. Reduces a matrix A or A'
// to a vector.
#define GB_FREE_ALL \
{ \
GB_Matrix_free (&B) ; \
GrB_Semiring_free (&semiring) ; \
}
#include "reduce/GB_reduce.h"
#include "binaryop/GB_binop.h"
#include "mxm/GB_mxm.h"
#include "mask/GB_get_mask.h"
#include "semiring/GB_Semiring_new.h"
GrB_Info GB_reduce_to_vector // C<M> = accum (C,reduce(A))
(
GrB_Matrix C, // input/output for results, size n-by-1
const GrB_Matrix M_in, // optional M for C, unused if NULL
const GrB_BinaryOp accum, // optional accum for z=accum(C,T)
const GrB_Monoid monoid, // reduce monoid for T=reduce(A)
const GrB_Matrix A, // first input: matrix A
const GrB_Descriptor desc, // descriptor for C, M, and A
GB_Werk Werk
)
{
//--------------------------------------------------------------------------
// check inputs
//--------------------------------------------------------------------------
GB_RETURN_IF_FAULTY_OR_POSITIONAL (accum) ;
GB_RETURN_IF_FAULTY (desc) ;
struct GB_Matrix_opaque B_header ;
GrB_Matrix B = NULL ;
struct GB_Semiring_opaque semiring_header ;
GrB_Semiring semiring = NULL ;
ASSERT_MATRIX_OK (C, "C input for reduce-to-vector", GB0) ;
ASSERT_MATRIX_OK_OR_NULL (M_in, "M_in for reduce-to-vector", GB0) ;
ASSERT_BINARYOP_OK_OR_NULL (accum, "accum for reduce-to-vector", GB0) ;
ASSERT_MONOID_OK (monoid, "monoid for reduce-to-vector", GB0) ;
ASSERT_MATRIX_OK (A, "A input for reduce-to-vector", GB0) ;
ASSERT_DESCRIPTOR_OK_OR_NULL (desc, "desc for reduce-to-vector", GB0) ;
ASSERT (GB_VECTOR_OK (C)) ;
ASSERT (GB_IMPLIES (M_in != NULL, GB_VECTOR_OK (M_in))) ;
// get the descriptor
GrB_Info info ;
GB_GET_DESCRIPTOR (info, desc, C_replace, Mask_comp, Mask_struct,
A_transpose, xx1, xx2, do_sort) ;
// get the mask
GrB_Matrix M = GB_get_mask (M_in, &Mask_comp, &Mask_struct) ;
// check domains and dimensions for C<M> = accum (C,T)
GrB_Type ztype = monoid->op->ztype ;
GB_OK (GB_compatible (C->type, C, M, Mask_struct, accum, ztype, Werk)) ;
// T = reduce (T,A) must be compatible
if (!GB_Type_compatible (A->type, ztype))
{
GB_ERROR (GrB_DOMAIN_MISMATCH,
"Incompatible type for reduction monoid z=%s(x,y):\n"
"input matrix A of type [%s]\n"
"cannot be typecast to reduction monoid of type [%s]",
monoid->op->name, A->type->name, ztype->name) ;
}
// check the dimensions
int64_t n = GB_NROWS (C) ;
if (A_transpose)
{
if (n != GB_NCOLS (A))
{
GB_ERROR (GrB_DIMENSION_MISMATCH,
"w=reduce(A'): length of w is " GBd ";\n"
"it must match the number of columns of A, which is " GBd ".",
n, GB_NCOLS (A)) ;
}
}
else
{
if (n != GB_NROWS(A))
{
GB_ERROR (GrB_DIMENSION_MISMATCH,
"w=reduce(A): length of w is " GBd ";\n"
"it must match the number of rows of A, which is " GBd ".",
n, GB_NROWS (A)) ;
}
}
// quick return if an empty mask is complemented
GB_RETURN_IF_QUICK_MASK (C, C_replace, M, Mask_comp, Mask_struct) ;
//--------------------------------------------------------------------------
// create B as full iso vector
//--------------------------------------------------------------------------
// B is constructed with a static header in O(1) time and space, even
// though it is m-by-1. It contains no dynamically-allocated content and
// does not need to be freed.
int64_t m = A_transpose ? GB_NROWS (A) : GB_NCOLS (A) ;
GB_CLEAR_MATRIX_HEADER (B, &B_header) ;
info = GB_new (&B, // full, existing header
ztype, m, 1, GB_ph_null, true, GxB_FULL, GB_NEVER_HYPER, 1,
/* OK: */ false, false, false) ;
ASSERT (info == GrB_SUCCESS) ;
B->magic = GB_MAGIC ;
B->iso = true ;
size_t zsize = ztype->size ;
GB_void bscalar [GB_VLA(zsize)] ;
memset (bscalar, 0, zsize) ;
B->x = bscalar ;
B->x_shallow = true ;
B->x_size = zsize ;
ASSERT_MATRIX_OK (B, "B for reduce-to-vector", GB0) ;
//--------------------------------------------------------------------------
// create the FIRST_ZTYPE binary operator
//--------------------------------------------------------------------------
struct GB_BinaryOp_opaque op_header ;
GrB_BinaryOp op ;
switch (ztype->code)
{
case GB_BOOL_code : op = GrB_FIRST_BOOL ; break ;
case GB_INT8_code : op = GrB_FIRST_INT8 ; break ;
case GB_INT16_code : op = GrB_FIRST_INT16 ; break ;
case GB_INT32_code : op = GrB_FIRST_INT32 ; break ;
case GB_INT64_code : op = GrB_FIRST_INT64 ; break ;
case GB_UINT8_code : op = GrB_FIRST_UINT8 ; break ;
case GB_UINT16_code : op = GrB_FIRST_UINT16 ; break ;
case GB_UINT32_code : op = GrB_FIRST_UINT32 ; break ;
case GB_UINT64_code : op = GrB_FIRST_UINT64 ; break ;
case GB_FP32_code : op = GrB_FIRST_FP32 ; break ;
case GB_FP64_code : op = GrB_FIRST_FP64 ; break ;
case GB_FC32_code : op = GxB_FIRST_FC32 ; break ;
case GB_FC64_code : op = GxB_FIRST_FC64 ; break ;
default :
// Create a FIRST_UDT binary operator. The function pointer for
// the FIRST_UDT op is NULL; it is not needed by FIRST. The
// function defn is also NULL. In the JIT, the FIRST multiply
// operator is a simple assignment so there's no need for a
// function definition. This binary op will not be treated as a
// builtin operator, however, since its data type is not builtin.
// Its hash, op->hash, will be nonzero. The name of FIRST_UDT is
// just "1st", which is not itself unique, but it will only be used
// in combination with the monoid, which must be user-defined. No
// typecasting is allowed between user-defined types, so the
// user-defined monoid must be specific this particular
// user-defined type and this "reduce_1st" will be a unique name
// for the constructed semiring (if "reduce" is the name of the
// monoid). In addition, it is not possible for the user to create
// a jitifyable operator with the name "1st", because of the
// leading "1" character in its name. So "reduce_1st" must be
// unique.
op = &op_header ;
op->header_size = 0 ;
info = GB_binop_new (op, NULL, // op->binop_func. NULL for FIRST_UDT
ztype, ztype, ztype, // ztype is user-defined
"1st", // a simple name for FIRST_UDT
NULL, // no op->defn for the FIRST_UDT operator
GB_FIRST_binop_code) ; // using a built-in opcode
break ;
}
// GB_binop_new cannot fail since it doesn't allocate the function defn.
ASSERT (info == GrB_SUCCESS) ;
ASSERT_BINARYOP_OK (op, "op for reduce-to-vector", GB0) ;
//--------------------------------------------------------------------------
// create the REDUCE_FIRST_ZTYPE semiring
//--------------------------------------------------------------------------
semiring = &semiring_header ;
semiring->header_size = 0 ;
info = GB_Semiring_new (semiring, monoid, op) ;
if (info != GrB_SUCCESS)
{
// out of memory
// GB_Semiring_new allocates semiring->name if it uses the FIRST_UDT
// operator created above, so it can run out of memory in that case.
GB_FREE_ALL ;
return (info) ;
}
ASSERT_SEMIRING_OK (semiring, "semiring for reduce-to-vector", GB0) ;
if (GB_Global_burble_get ( ))
{
GB_Semiring_check (semiring, "semiring for reduce-to-vector", 3, NULL) ;
}
//--------------------------------------------------------------------------
// reduce the matrix to a vector via C<M> = accum (C, A*B)
//--------------------------------------------------------------------------
info = GB_mxm (C, C_replace, M, Mask_comp, Mask_struct, accum,
semiring, A, A_transpose, B, false, false, GxB_DEFAULT, do_sort, Werk) ;
GB_FREE_ALL ;
return (info) ;
}
|
