Tomek Sowiński wrote: > Dnia 04-09-2010 o 08:03:12 John Demme <j...@cs.columbia.edu> 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.
That's an interesting thought. It'd be a bit trickier than that since I'm doing some post-processing on the product, but not enough to make this impossible. I'll probably give this a shot if I really need to scale up -- it'd be difficult to fight n^4 space with more RAM... though I'd sure like to give it a shot :) > > Fascinating stuff you're dealing with... Good luck. Thanks ~John