GxB for vector dot product?

[eriknw]

How much trouble would it be for you to finally add this? I would use it and love it.

To work around the lack of this functionality, I make a Matrix with one column or row, do mxv with a semiring and a length 1 vector for the output, then extract the first element from the vector. This is pretty annoying. It's come up a few times for me.

I don't have a preference for the name. vxv, dot, inner, or really anything would work for me. Output types of GxB_Scalar or C scalar would work for me; GxB_Scalar is preferred/expected, because it makes everything so much easier. Is there really any question about what the signature or behavior would be?

[DrTimothyAldenDavis]

An output of GxB_Scalar would make sense. It's not difficult to add, it just expands the GxB space of methods, and it could get unwieldy in the API if I start adding all the possible vector methods like this (GrB_kronecker for example, which has also been requested). I need to figure out the best API for this, as well as the outer product of 2 vectors, GrB_kronecker, and so on.

In the short term, it's valid (just not documented) to do GrB_mxm (C, ..., (GrB_Matrix) v, (GrB_Matrix) w, desc) with the descriptor transposing v, where C is a 1-by-1 matrix. Or if you like, let c be a GxB_Scalar and do GrB_mxm ((GrB_Matrix) c, ...). That is, you can typecast a GrB_Vector to GrB_Matrix, and it works just fine, and likewise a GxB_Scalar can be typecast to a GrB_Vector or a GrB_Matrix. I don't expect to change that in the future, but it's not a documented feature. It's not in the GraphBLAS C API either. Don't tell anyone I said this :-).

[eriknw]

Thanks. I guess I don't understand what's unwieldly about this other than the risk that some day you'll have both GxB and GrB versions.

Adding the inner product adds one function to your API. I would maybe call it GxB_vxv_inner, which allows for the possibility of GxB_vxv_outer_* and GxB_vxv generic function. Outer and kron are both more complicated, because they can have different versions that support binaryop, monoid, and semiring.

I think there's an argument to be made that inner product is simple, useful/common, and expected. The cost is cheap, and the value is high. Whether you feel compelled to add outer product or kron is up to you; I'm not asking for them. If you're worried that adding inner product will result in people asking for outer and kron, well, it sounds like people already are! ;)

I know I can add this to the Python API using the tricks you shared. I will then likely want to add this to LAGraph someday as I use it there. I think it's reasonable to push to have this added to the spec or, barring that, implementations. If you or the spec committee want to see use cases first, then it can begin from Python I suppose.

[eriknw]

But certainly take your time and do what you feel comfortable with. You provided workarounds, so this is a non-blocking issue.

Heh, I wrote this issue out of frustration at midnight. It was perhaps a little impulsive :). Nevertheless, I think it's a good discussion to have in the open.

[DrTimothyAldenDavis]

It's a good topic to keep alive ... I have it as one of my pending issues to grapple with.

[eriknw]

Great. Dot product really does come up pretty often for me.

I'm computing global clustering coefficient right now, and the denominator is naturally obtained from a dot product of vectors. These vectors come from reducing a Matrix to a Vector, so I can't easily change the algorithm to use matrices instead (unless I copy a Vector to a Matrix, or cast a Vector to a Matrix using your trick).

Perhaps the thinking for why dot product isn't necessary is that one should be able to perform a binary operation between Vectors, then perform a reduction with a Monoid, and hopefully having an extra intermediate Vector isn't too costly. I suppose this may be true. But, we have semirings that are incredibly powerful and convenient to use, so why not allow them to be used here?

[DrTimothyAldenDavis]

Yes, I definitely agree that dot products, and also outer products of 2 vectors, are missing in the GrB API. They really should be there.

On Fri, Jul 9, 2021 at 2:32 PM Erik Welch @.***> wrote:

Great. Dot product really does come up pretty often for me.

I'm computing global clustering coefficient right now, and the denominator is naturally obtained from a dot product of vectors. These vectors come from reducing a Matrix to a Vector, so I can't easily change the algorithm to use matrices instead (unless I copy a Vector to a Matrix, or cast a Vector to a Matrix using your trick).

Perhaps the thinking for why dot product isn't necessary is that one should be able to perform a binary operation between Vectors, then perform a reduction with a Monoid, and hopefully having an extra intermediate Vector isn't too costly. I suppose this may be true. But, we have semirings that are incredibly powerful and convenient to use, so why not allow them to be used here?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/DrTimothyAldenDavis/GraphBLAS/issues/57#issuecomment-877411512, or unsubscribe https://github.com/notifications/unsubscribe-auth/AEYIIONV7NBDZRYM52ZJM3LTW5FGBANCNFSM5ACAAQPA .

[eriknw]

For GxB, I think it would be sufficient of you only added outer product and kron for BinaryOp just like how you only had GxB_kron for matrices with BinaryOp. Hence, this would add up to three new GxB functions, which I think is reasonable given the value of the functions.

[DrTimothyAldenDavis]

kron is a kind of odd one, since you could imagine a kron (vector, matrix) and kron(matrix,vector), kron(vector,vector), etc. which gets a little verbose. So I might leave kron alone for now.

On Fri, Jul 9, 2021 at 5:18 PM Erik Welch @.***> wrote:

For GxB, I think it would be sufficient of you only added outer product and kron for BinaryOp just like how you only had GxB_kron for matrices with BinaryOp. Hence, this would add up to three new GxB functions, which I think is reasonable given the value of the functions.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/DrTimothyAldenDavis/GraphBLAS/issues/57#issuecomment-877485353, or unsubscribe https://github.com/notifications/unsubscribe-auth/AEYIIONLRR53T5QHKQPN7U3TW5YR7ANCNFSM5ACAAQPA .

[eriknw]

I decided I like the names inner and outer, which is what I'm adding to grblas using your casting trick (works great!).

[michelp]

While I like adding inner as a GxB method, it seems like now that we have GxB_Matrix/Vector_diag, inner can be done with (Matrix.from_diag(a) @ Matrix.from_diag(b)).vector_diag() (in pygraphblas syntax). I still think it would be nice to have inner as a shorthand.

As for outer, @DrTimothyAldenDavis what do you think of this: we have iso scalar matrices, why not iso column or row vector? It seems just like iso scalars that you could detect this at assignment time and store only one vector. Then outer becomes B[:,] = b; Matrix.from_diag(a) @ B.

[DrTimothyAldenDavis]

By "iso column" do you mean a matrix where every column is the same? That would be far too hard to do. A single vector is much more complex than a single scalar. The scalar iso property does not affect the way I store the pattern at all, just the A->x array which becomes size 1. An iso column or iso row breaks that.

[DrTimothyAldenDavis]

This isn't hard to add, at least for a simple implementation using my existing matrix-multiply kernels. GxB_vxv_inner and GxB_vxv_outer would be simple wrappers around calls to my existing GB_mxm.c kernel (see for example how GrB_mxv and GrB_vxm are implemented). I would simply hide the typecast from GrB_Vector to my internal GrB_Matrix variable, and call GB_mxm.c. That would work but they could be done faster if I wrote specialized kernels for both of these.

In particular, the inner product would be single threaded right now. I do not yet exploit multiple threads when computing a single dot product.

The outer product has a very specialized (and simple!) nonzero pattern, being a Cartesian product (a dense clique in a graph or a dense submatrix). Also, the outer product doesn't make use of the monoid at all. My existing matrix-matrix multiply methods would work just fine, but they don't exploit these special cases to get better performance. In particular, exploiting the mask while computing matrix-times-matrix is sometimes hard to do, depending on the specific cases. But exploiting the mask for the vector outer product would be a lot easier.

The outer product would be parallel, at least.

But I could easily add these wrappers now, and then work on the performance later.