<div dir="ltr">I can see a couple opportunities for improvements in your algorithm.  Running your code on a single experiment, I get about 2.9 seconds to run. I get this down to about 1.0 seconds by (1) exploiting the symmetry of the M matrix and (2) avoiding the costly inner loop over k in favor of array operations:<div>
<br></div><div><div>def check_segments(j, others, data):</div><div>    x1, y1, x2, y2 = data</div><div>    </div><div>    x_A1B1 = x2[j]-x1[j]</div><div>    y_A1B1 = y2[j]-y1[j]</div><div>    </div><div>    x_A1A2 = x1[others]-x1[j]</div>
<div>    y_A1A2 = y1[others]-y1[j]      </div><div>    </div><div>    x_A2A1 = -1*x_A1A2</div><div>    y_A2A1 = -1*y_A1A2</div><div>    </div><div>    x_A2B2 = x2[others]-x1[others]</div><div>    y_A2B2 = y2[others]-y1[others]</div>
<div>    </div><div>    x_A1B2 = x2[others]-x1[j]</div><div>    y_A1B2 = y2[others]-y1[j]</div><div>    </div><div>    x_A2B1 = x2[j]-x1[others]</div><div>    y_A2B1 = y2[j]-y1[others]</div><div><br></div><div>    p1 = x_A1B1*y_A1A2 - y_A1B1*x_A1A2</div>
<div>    p2 = x_A1B1*y_A1B2 - y_A1B1*x_A1B2</div><div>    p3 = x_A2B2*y_A2B1 - y_A2B2*x_A2B1</div><div>    p4 = x_A2B2*y_A2A1 - y_A2B2*x_A2A1</div><div><br></div><div>    condition_1=p1*p2</div><div>    condition_2=p3*p4                         </div>
<div><br></div><div>    return (p1 * p2 <= 0) & (p3 * p4 <= 0)</div><div><br></div><div>for j in xrange(1, N):</div><div>    valid = check_segments(j, range(j), (x1, y1, x2, y2))</div><div>    M[j,0:j] = valid</div>
<div>    M[0:j,j] = valid</div><div class="gmail_extra"><br></div><div class="gmail_extra">I don't see any other particularly simple ways to improve this.  You could probably add an interval check to ensure that the x and y intervals for the segments of interest overlap before doing the full check, but how much that would help would depend on the implementations.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">~Brett<br><br><div class="gmail_quote">On Fri, Aug 23, 2013 at 5:09 PM, Josè Luis Mietta <span dir="ltr"><<a href="mailto:joseluismietta@yahoo.com.ar" target="_blank">joseluismietta@yahoo.com.ar</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div><div style="font-size:10pt;font-family:'times new roman','new york',times,serif">
<div style="margin-bottom:6px;padding:0px 0px 0px 5px;border:none;font-size:14px;line-height:19px;font-family:sans-serif">I wrote an algorithm for study stick percolation (i.e.: networks between line segments that intersect between them). In my algorithm N sticks (line segments) are created inside a rectangular box of sides 'b' and 'h' and then, one by one, the algorithm explores the intersection between all line segments. This is a Monte Carlo simulation, so the 'experiment' is executed many times (no less than 100 times). Written like that, very much RAM is consumed:  Here, the element Mij=1 if stick i intersects stick j and Mij=0 if not.<br>
</div><div style="margin-bottom:6px;padding:0px 0px 0px 5px;border:none;font-size:14px;line-height:19px;font-family:sans-serif">How can I optimize my algorithm? Graph theory is useful in this case?</div></div></div></blockquote>
</div><br></div></div></div>