Dnia 04-09-2010 o 08:03:12 John Demme <[email protected]> napisał(a):
As for the graphs, I essentially take two input graphs, represented in
adjacency matrix form (two 2-d matrices of size n^2 each, assuming equal
sized graphs). Then, I compute the Kronecker Tensor Graph Product[2],
which
creates a matrix of size n^4. Depending on how you think about it, this
matrix is a simple (although large) 2-D adjacency matrix of the product
graph, and it can be treated as such for many operations. It can also be
inspected in four dimensional space to examine the relationships between
possible node pairs, but I don't do this. Frankly, it hurts my brain a
little bit.
Can't you compute the Kronecker product lazily? E.g. a proxy object that
computes a value in an overloaded opIndex. Even if your algorithms inspect
(compute) the same value several times, you may still win -- the
bottleneck these days is memory access, not CPU cycles.
Fascinating stuff you're dealing with... Good luck.
Tomek
