views:

411

answers:

3

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?

+3  A: 

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.

Rob Lachlan
Well I was looking more from a algorithm point of view, rather than a hardware dependant one, so I guess this means no.
samoz
I see what you mean, but your algorithms run on hardware after all. To put it another way, if there are n things that you want to change, in an algorithmic sense, you can only do this if changing those n items is a unitary operation.
Rob Lachlan
Another example, from matrix multiplication: it can easily be shown that for nxn matrices, the cost of multiplying them is at least n squared. Why? Because you have to at least look at each element. (As it happens, the best matrix multiplication known takes more than n squared.)
Rob Lachlan
A: 

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.

nlucaroni
True, a good observation.
Rob Lachlan
It will most likely not be symmetric, since some nodes will only be connected to one other node, or something similar.
samoz
A: 

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).

Pete Kirkham