BB-53: Pattern-only matrices and vectors

[mcmillan03]

The addition of the pattern-only matrix type needs a lot of careful thought, in terms of the impact it will have throughout the spec. It's a pervasive change that will impact every GraphBLAS function. I think it has a clean definition but we would need to go through each part of the spec carefully to make sure everything makes sense.

For example, is this a new built-in matrix type, say GxB_STRUCTURE or GxB_PATTERN, to go along with GrB_BOOL, GrB_INT8, GrB_FP32, etc? Probably. What happens with typecasting? I would suppose that it should typecast to/from the other built-in types, and any time the "value" of a GxB_PATTERN matrix is accessed it would be seen as "1", in any type. What happens to GrB_Matrix_extractTuples, to the "values" array? Is it ignored? Filled with 1's? All of the built-in operators have 11 type-specific versions, like GrB_PLUS_BOOL, GrB_PLUS_INT8, etc. Is there a GrB_PLUS_PATTERN? That seems redundant since all built-in binary operators T = op(T,T) where T = GrB_PATTERN would be identical to one another. So are pattern-only operators not needed at all since all operators act the same on a GrB_PATTERN matrix? That is, if "f" is a binary operator applied to two entries of a GrB_PATTERN matrix, then z=f(x,y) ignores the value of z, and the result is just an entry in the pattern. So do we need any operators at all? Or perhaps GrB_LOR is the "native" binary operator for a GxB_PATTERN matrix (one that effectively does no typecasting)? Or can the 'op' input to, say, GrB_eWiseMult be NULL, to denote the fact that the binary operator isn't actually used, and the output C is just the pattern-only matrix of the set intersection of A and B? Likewise, for GrB_mxm, is the semiring input a NULL pointer, to denote the fact that no semiring is actually needed?

What happens if the user creates a new binary operator with the following?

GrB_BinaryOp_new (&op, f, GrB_FP32, GxB_PATTERN, GrB_FP32) ;

where f (void z, const void x, const void y) is the user function. So the parameter x has type "GxB_PATTERN" ... what does that mean? I'm not sure what that means to the C-callable function itself. Is x passed to the user function as a NULL pointer, since there are no values expected? Is it a pointer to "1"? If so, is it a pointer to a boolean 1 (of one byte)?

[DrTimothyAldenDavis]

I don't think this is necessary, and it would create lots of difficulties. I'm already able to exploit this with the idea of "iso-valued" matrices. This "iso" feature requires nothing at all to be added to the spec (except perhaps a change to GrB_Matrix_import/export, and GrB_Matrix/Vector_build).

If a mask is iso-valued and that value is nonzero, then internally I turn on the "structure" flag, as if the user asked for a structural mask. This gives the same result and makes the kernels faster since structural masks are faster than valued masks.

Trying to describe a matrix of type GrB_PATTERN is awkward. What is the type and value of A(i,j)? This breaks far too many things in GraphBLAS. Instead, just keep the GrB_Matrix as it is, and let the type be whatever it wants to be (GrB_BOOL, GrB_FP32, etc). Then let A(i,j) have a value, say 3.14159. Then if all the entries in the matrix have this same value, I can easily detect this and exploit it, and just store the value 3.14159 once. Computing a resulting matrix C with, say C = A+B is well defined, and if both A and B are iso-valued then so is C, and computing its new value takes O(1) time.

All of this can be done in the current v1.3 spec, although I do add an option to my GxB_import/export to tell the user "there is only one value for all entries". I also add a GxB_Matrix_build_Scalar, which always builds an iso-valued matrix, whose iso value is given by a single GrB_Scalar. These changes are very very minor additions to the spec.

By contrast, adding a GrB_PATTERN is very disruptive to the spec. I can get all the benefit of a GrB_PATTERN style of matrix with the current spec as it is, and all matrices (even user-defined types) can exploit this iso property.

So there is no need to add GrB_PATTERN. Please do not add it to the spec.

[DrTimothyAldenDavis]

I suggest that this issue be closed.