Velocity Reviews > Another optimization request :-)

# Another optimization request :-)

jeffg
Guest
Posts: n/a

 02-12-2009
If anyone wants to take this on... I would really really like to have
the spring_layout modified to support multi-threading if at all
possible.
My test data is 20,000, which makes this process 20,000 x 20,000 or
400,000,000 (400 million) calculations. This is taking somewhere
between 2-3 hours an iteration.
I plan to plot out over 1,000,000 data points or more, which would put
this at 1,000,000,000,000 (1 trillion) calculations. Any help in
making this more efficient would be much appreciated.

def spring_layout(G, iterations=50, dim=2, node_pos=None,
verbose=False):
"""Spring force model layout"""
if node_pos==None : # set the initial positions randomly in 1x1
box
vpos=random_layout(G, dim=dim)
else:
vpos=node_pos
if iterations==0:
return vpos
if G.order()==0:
k=1.0
else:
k=N.sqrt(1.0/G.order()) # optimal distance between nodes
disp={} # displacements

# initial "temperature" (about .1 of domain area)
# this is the largest step allowed in the dynamics
# linearly step down by dt on each iteration so
# on last iteration it is size dt.
t=0.1
dt=0.1/float(iterations+1)
for i in range(0,iterations):
for v in G:
if verbose==True:
print("Interation: " + str(i + 1) + ", Calculating: "
+ str(v.encode('iso-8859-15', "replace")))
disp[v]=N.zeros(dim)
for u in G:
delta=vpos[v]-vpos[u]
dn=max(sqrt(N.dot(delta,delta)),0.01)
# repulsive force between all
deltaf=delta*k**2/dn**2
disp[v]=disp[v]+deltaf
# attractive force between neighbors
if G.has_edge(v,u):
deltaf=-delta*dn**2/(k*dn)
disp[v]=disp[v]+deltaf

# update positions
for v in G:
l=max(sqrt(N.dot(disp[v],disp[v])),0.01)
vpos[v]=vpos[v]+ disp[v]*t/l
t-=dt
return vpos

jeffg
Guest
Posts: n/a

 02-12-2009
On Feb 11, 9:56*pm, "andrew cooke" <(E-Mail Removed)> wrote:
> sorry, that was stupid. *there is no inversion (apart from 1/m), just the
> integration.
>
> still, improving the integration would allow larger steps.
>
> andrew
>
> andrew cooke wrote:
>
> > why are you dong this point by point? *surely you can express the physics
> > as a set of equations and invert the matrix? *wouldn't that be a lot
> > faster? *you'd replace the iteration over all combinations of points with
> > a faster matrix inversion.

>
> > see for example
> >http://www.medwelljournals.com/fullt...24-338.pdfpage 331
> > onwards.

>
> > there's a very nice into to the verlet integration mentioned here -
> >http://teknikus.dk/tj/gdc2001.htm

>
> > andrew

>
> > jeffg wrote:
> >> If anyone wants to take this on... I would really really like to have
> >> the spring_layout modified to support multi-threading if at all
> >> possible.
> >> My test data is 20,000, which makes this process 20,000 x 20,000 or
> >> 400,000,000 (400 million) calculations. *This is taking somewhere
> >> between 2-3 hours an iteration.
> >> I plan to plot out over 1,000,000 data points or more, which would put
> >> this at 1,000,000,000,000 (1 trillion) calculations. *Any help in
> >> making this more efficient would be much appreciated.

>
> >> def spring_layout(G, iterations=50, dim=2, node_pos=None,
> >> verbose=False):
> >> * * """Spring force model layout"""
> >> * * if node_pos==None : *# set the initial positions randomly in 1x1
> >> box
> >> * * * * vpos=random_layout(G, dim=dim)
> >> * * else:
> >> * * * * vpos=node_pos
> >> * * if iterations==0:
> >> * * * * return vpos
> >> * * if G.order()==0:
> >> * * * * k=1.0
> >> * * else:
> >> * * * * k=N.sqrt(1.0/G.order()) # optimal distance between nodes
> >> * * disp={} * * * * # displacements

>
> >> * * # initial "temperature" (about .1 of domain area)
> >> * * # this is the largest step allowed in the dynamics
> >> * * # linearly step down by dt on each iteration so
> >> * * # on last iteration it is size dt.
> >> * * t=0.1
> >> * * dt=0.1/float(iterations+1)
> >> * * for i in range(0,iterations):
> >> * * * * for v in G:
> >> * * * * * * if verbose==True:
> >> * * * * * * * * print("Interation: " + str(i + 1) + ", Calculating: "
> >> + str(v.encode('iso-8859-15', "replace")))
> >> * * * * * * disp[v]=N.zeros(dim)
> >> * * * * * * for u in G:
> >> * * * * * * * * delta=vpos[v]-vpos[u]
> >> * * * * * * * * dn=max(sqrt(N.dot(delta,delta)),0.01)
> >> * * * * * * * * # repulsive force between all
> >> * * * * * * * * deltaf=delta*k**2/dn**2
> >> * * * * * * * * disp[v]=disp[v]+deltaf
> >> * * * * * * * * # attractive force between neighbors
> >> * * * * * * * * if G.has_edge(v,u):
> >> * * * * * * * * * * deltaf=-delta*dn**2/(k*dn)
> >> * * * * * * * * * * disp[v]=disp[v]+deltaf

>
> >> * * * * # update positions
> >> * * * * for v in G:
> >> * * * * * * l=max(sqrt(N.dot(disp[v],disp[v])),0.01)
> >> * * * * * * vpos[v]=vpos[v]+ disp[v]*t/l
> >> * * * * t-=dt
> >> * * return vpos
> >> --
> >>http://mail.python.org/mailman/listinfo/python-list

>
> > --
> >http://mail.python.org/mailman/listinfo/python-list

>
>

To be honest, this is not my code and I'm new to python. It's part of
the open source project NetworkX, but I'm using this one call
extensively. I'm also not that familiar with the math behind the
physics. I'll read the documents and see if I can figure it
out. Thank you for the links and suggestions. I really need to
get this code performing at peak levels.

Terry Reedy
Guest
Posts: n/a

 02-12-2009
jeffg wrote:
> If anyone wants to take this on... I would really really like to have
> the spring_layout modified to support multi-threading if at all
> possible.
> My test data is 20,000, which makes this process 20,000 x 20,000 or
> 400,000,000 (400 million) calculations. This is taking somewhere
> between 2-3 hours an iteration.
> I plan to plot out over 1,000,000 data points or more, which would put
> this at 1,000,000,000,000 (1 trillion) calculations. Any help in
> making this more efficient would be much appreciated.
>
> def spring_layout(G, iterations=50, dim=2, node_pos=None,
> verbose=False):
> """Spring force model layout"""
> if node_pos==None : # set the initial positions randomly in 1x1
> box
> vpos=random_layout(G, dim=dim)
> else:
> vpos=node_pos
> if iterations==0:
> return vpos
> if G.order()==0:
> k=1.0
> else:
> k=N.sqrt(1.0/G.order()) # optimal distance between nodes
> disp={} # displacements
>
> # initial "temperature" (about .1 of domain area)
> # this is the largest step allowed in the dynamics
> # linearly step down by dt on each iteration so
> # on last iteration it is size dt.
> t=0.1
> dt=0.1/float(iterations+1)
> for i in range(0,iterations):
> for v in G:
> if verbose==True:
> print("Interation: " + str(i + 1) + ", Calculating: "
> + str(v.encode('iso-8859-15', "replace")))
> disp[v]=N.zeros(dim)
> for u in G:
> delta=vpos[v]-vpos[u]

Let n = len(vpos). I believe there are only n-1 different deltas, dns,
and deltafs, where as n**2 calculations are made.

> dn=max(sqrt(N.dot(delta,delta)),0.01)
> # repulsive force between all
> deltaf=delta*k**2/dn**2
> disp[v]=disp[v]+deltaf
> # attractive force between neighbors
> if G.has_edge(v,u):
> deltaf=-delta*dn**2/(k*dn)
> disp[v]=disp[v]+deltaf
>
> # update positions
> for v in G:
> l=max(sqrt(N.dot(disp[v],disp[v])),0.01)
> vpos[v]=vpos[v]+ disp[v]*t/l
> t-=dt
> return vpos

That aside, array calculations like this should be *much* faster with
numpy. Or try compiling (with weave or Cython, for instance).

bearophileHUGS@lycos.com
Guest
Posts: n/a

 02-12-2009
On Feb 12, 2:48*am, jeffg <(E-Mail Removed)> wrote:
> If anyone wants to take this on... I would really really like to have
> the spring_layout modified to support multi-threading if at all
> possible.

You can start creating a compiled Python extension using ShedSkin, it
may be enough.

Bye,
bearophile

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Ravikiran C Programming 22 11-24-2008 03:19 AM belfast-biker Microsoft Certification 0 01-14-2006 12:49 PM Guru03 Perl Misc 12 02-14-2004 01:21 AM Brian Birtle ASP .Net 2 10-16-2003 02:11 PM Steve ASP .Net 0 07-01-2003 12:11 AM