Hello Tomek,
Dnia 04-09-2010 o 08:03:12 John Demme <j...@cs.columbia.edu>
napisal(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.
If enough elements from the 4d matrix are accessed, in the wrong order, then
the cache effects of doing it lazily might kill it. I'd guess that highly
optimized code for doing the pre-compute version exists already.
Fascinating stuff you're dealing with... Good luck.
Tomek
--
... <IXOYE><
