Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement shape::is_one_to_one and shape::is_subset_of #2

Open
dsharlet opened this issue Nov 10, 2019 · 1 comment
Open

Implement shape::is_one_to_one and shape::is_subset_of #2

dsharlet opened this issue Nov 10, 2019 · 1 comment

Comments

@dsharlet
Copy link
Owner

dsharlet commented Nov 10, 2019

In order to determine if a shape maps two different indices to the same flat indices (i.e. is_one_to_one is false), we need to solve:

x_0*S_0 + x_1*S_1 + x_2*S_2 + ... == y_0*S_0 + y_1*S_1 + y_2*S_2 + ...

where x_i, y_i are (different) indices, and S_i are the strides of this shape. This is equivalent to:

(x_0 - y_0)*S_0 + (x_1 - y_1)*S_1 + ... == 0

We don't actually care what x_i and y_i are, so this is equivalent to:

x_0*S_0 + x_1*S_1 + x_2*S_2 + ... == 0

where x_i != 0. This is a linear diophantine equation, and we already have one solution at x_i = 0, so we just need to find other solutions, and check that they are in range.

This is pretty hard. Wikipedia research so far suggests we need to rewrite the equation as a system of linear diophantine equations, and then use the "Hermite normal form" to get the unbounded solutions, and then do some combinatoric search for the in-bounds solutions. This is an NP-hard problem, but the size of the problems are small, and I don't think these functions need to be fast.

is_subset_of is possibly similar.

@dsharlet
Copy link
Owner Author

dsharlet commented Jul 3, 2020

is_subset_of needs to possibly handle even shapes of different rank, but it boils down to solving a problem of the same form.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant