CODEWITHSUNDEEP
performancealgorithmrefactoring
foobarfuzzbizz
foobarfuzzbizz

Reputation: 58725

Speed boost to adjacency matrix

I currently have an algorithm that operates on an adjacency matrix of size n by m. In my algorithm, I need to zero out entire rows or columns at a time. My implementation is currently O(m) or O(n) depending on if it's a column or row.

Is there any way to zero out a column or row in O(1) time?

Upvotes: 3

Views: 1095

Answers (3)

Pete Kirkham
Pete Kirkham

Reputation: 49331

It depends on how your matrices are implemented.

If you have a representation such as an array of arrays, you can point to a shared zeroed element array, as long as you check you don't subsequently write to it. Which means one out of a row or column can be zeroed in O(N), with a constant cost on all other write operations.

You also could have a couple of arrays - one for rows, one for columns - which scale the values in the matrix. Putting a zero in either would be a O(1) operation to mask out a row or column, at the cost of extra processing for every read; but it may be worth it as a way of temporarily removing a node from the graph if that's a common use case. It also leaves the original version of the matrix untouched, so you could parallelise your algorithm (assuming the only operation it requires is pruning all edges into or out of a node).

Upvotes: 0

nlucaroni
nlucaroni

Reputation: 47944

Is the distance metric and is the graph undirected? (in this case the matrix is symmetric). In that case you could just operate on lower or upper triangular matrices throughout the program. In this way you just have to 0 out one row (or column if you are dealing with upper triangular). and even then it wont be a whole row, on average half.

Upvotes: 0

Rob Lachlan
Rob Lachlan

Reputation: 14479

Essentially this depends on the Chip architecture that you're dealing with. For most CPUs, it isn't possible to zero out whole swathes of memory at go, and therefore each word will require a separate memory operation, no matter what facilities your programming language provides.

It helps tremendously if your memory is contiguous for memory access time, because memory adjacent to memory just accessed will be cached, and subsequent accesses will hit the cache, resulting in fast performance.

The result of this is that if your matrix is large, it may be faster to zero out a row at a time or a column at a time, rather than vice versa, depending on whether your data is written by column or by row.

EDIT: I have assumed that your matrices aren't sparse, or triangular, or otherwise special, since you talk about "zeroing out a whole row". If you know that your matrix is mostly empty or somehow otherwise fits a special pattern, you would be able to represent your matrix in a different way (not a simple nxm array) and the story would be different. But if you have an nxm matrix right now, then this is the case.

Upvotes: 4

Related Questions