[BUG] Incorrect behavior of sparse matrix-matrix multiplication

[kose-y]

This PyTorch bug was introduced by #4707.
Unlike claimed there, indices should not only be unique, but also be sorted in coalesced matrix for correct behavior of matrix multiplication. This raises a major issue when performing matrix multiplication with coalesced then transposed matrix.

The following is tested on 2e156f3, but any version after 5e72d7a will have the same behavior.

import torch
idx = torch.LongTensor([[0,1,2], [2,1,0]])
val = torch.ones(3)
D = torch.sparse.FloatTensor(idx,val,torch.Size([3,3]))
Dc = D.coalesce()
x = torch.ones((3,1))

torch.mm(D.t(), x)

 1
 1
 1
[torch.FloatTensor of size (3,1)]

torch.mm(Dc.t(), x)

 3
 0
 0
[torch.FloatTensor of size (3,1)]

I will create a pull request regarding this and #6171 later today.

[weiyangfb]

This issue is caused by the following:

• t() because it swaps the indices of a sparse tensor without setting coalesce=false
• calling coalesce() sets coalesce=true
• mm(Sparse, Dense) doesn't really sort the sparse tensor - the call to coalesce() doesn't do anything.

A simple fix will be to set coalesce=false at t()

This is related to the invariants of transpose(): #4707, maybe should change coalesce slight to get around it.

After chatted to @zou3519, we can define a sparse tensor with coalesced=true when:

1. its elements are unique and
2. the indices are in sorted order

And set coalesce=false whenever the conditions are not held, e.g. t(). This should solve the issue.