equality of matrices of m * n

Question

What is the most efficient way for checking for equality of two m * n matrices and more importantly the [i][j] index (or indices) which caused the two matrices to be unequal.

In my case, 'm' is relatively small (<=4) and n is relatively large (<=512).

Context of the problem : I have an Active Standby setup for my application. Whenever an event happens which causes a state change, the active sends an update to the standby. However, we have observed sometimes standby is out-of-sync with the active even though the active has send all updates. We are planning therefore to run an audit on the data structure synced. The audit will calculate a checksum on active and send them to the slave. The slave will do the same and will return a NAk if they do not match. The active will then sync the slave again. My problem is I want the slave to return the [i][j] position which caused the checksum to not match.

Edit: Language C

Answer 1

Since you have no idea where the matrices mismatch you'll have to compare them element-by-element. Just iterate the matrices and compare.

You have to take care of possible cache misses penalties - you need to scan matrices in such order that you don't cause unnecessary cach line reloads. This is language dependent. For C, for example, you need to have the outer loop iterating the first index and the inner loop iterating the second index.

Answer 2

As sharptooth stated, checksums mostly cannot be reversed. If you can hash only parts for the matrix you can a sort of binary search, where you eliminate half of remaining range at every iteration. This can work even when there's more than one mismatched element: you have to check both halves.
Also, your matrix has about 2000 cells, is in fact very small. Comparing them should therefore be quick. If every object contains a lot of data you can hash every object (so you have 2000 hashes, which should be much smaller than your objects), and compare the matrices of hashes - then you'll know for sure where the problem is.
Again, keep in mind that calculating a checksum means going over the whole matrix, so the best wat to compare them is probably one-by-one, as suggested.

Answer 3

While it's not much use for the case where m >> n, if m ~ n you can checksum all rows and columns individually, giving you a total of m + n checksums to transmit. By doing this, you know that when the ith row checksum and jth column checksum do not match, there's a problem with entry A_ij of the matrix. But there could be other problems, depending on how robust your checksums are and how often they allow false negatives.

For your case, sending 516 separate checksums is not a significant win over sending the whole matrix of 2048 entries, and so implementing this is probably just wasting your time with premature optimization. But for a 512×512 matrix, sending 1024 checksums is much nicer than sending 262,144 entries.

Answer 4

Information Theory tells us that you can't get something for nothing here. If there are m * n cells and each of them contains k bits of information (e.g. 16 bit integers), then the possibility space of your matrix occupies m * n * k bits.

If you want to be able to send one single "message" and handle every case from "they are in sync" to "every cell is different in a unique and strange way" then the laws of nature require you to make this message m * n * k bits long. If you use m * n * b - 1 bits, I will be able to construct two situations that you cannot distinguish. In fact, half of your state space will become indistinguishable.

Now, if you describe your requirements further, we can cut some possibility space. What you can get on the cheap, for example, is the ability to recognize 1 cell out of sync, as has been described by others. Keep in mind that the algorithm designed to locate 1 diff will completely fail if there are 2 diffs. e.g. it will tell you that cell A is out of sync when it's really cells B and C.