search

gonum / matrix

Matrix packages for the Go language [DEPRECATED]
446 stars 53 forks source link

mat64: consider making symmetric and triangular overlap detection more precise #357

Closed kortschak closed 8 years ago

kortschak commented 8 years ago

There is a couple of TODOs in shadow.go that suggest this. We need to understand whether it is worth doing. The intention of the TODO for each case is to only flag an overlap if the actual triangles in use overlap; this is consistent with the wording of the documentation (which would otherwise be changed), but is more work and more complicated code than appears in rectanglesOverlap (a brief survey suggests 6 cases instead of the current 2 - and I'm still not entirely sure of the best approach).

Is the cost of implementing this worth the effort?

btracey commented 8 years ago

It is definitely tricky. In lapack, generally two triangles occupy the same rectangular area, but one assumes a diagonal of 1s and so doesn't actually need storage on the diagonal. It's pretty tricky in mat64 to actually construct triangles whose slices overlap but whose data does not. It at least requires two calls to NewDense and one call to ViewTri (which doesn't exist, but could). Assuming we disallow any overlap, what do we prevent? Is it more than just a factor of two in storage?

kortschak commented 8 years ago

I have a sketch of a reasonable algorithm, but yes, at the moment, I don't think you can create an overlap that is a rectangle overlap and not a triangle overlap - at least not without recourse to a Raw method (which do have said that we consider).

The storage factor is < 2x since we don't allow unit matrices in mat64.