title: How can I efficiently initialize this sparse array in Mathematica?
body: <p>I'm trying to solve a rather large linear programming problem in Mathematica, but for some reason the bottleneck is setting up the array of linear constraints.</p>
  
  <p>My code for initializing the matrix looks like this:</p>
  
  <pre><code>AbsoluteTiming[S = SparseArray[{{i_, 1} -&gt; iaa[[i]],
      {i_, j_} /; Divisible[a[[j]], aa[[i]]] -&gt; 1.}, {2*n, n}]]
  </code></pre>
  
  <p>Here n is 4455, iaa is a list of reals, and a, aa are lists of integers. The output I get for this line is</p>
  
  <pre><code>{2652.014773,SparseArray[&lt;111742&gt;,{8910,4455}]}
  </code></pre>
  
  <p>In other words, it takes 45 minutes to initialize this matrix, even though it only has 111,742 nonzero entries. For comparison, actually solving the linear program only takes 17 seconds. What gives?</p>
  
  <p>Edit: Also, can anyone explain why this takes up so much memory as it is running? Because in user time, this calculation takes less than ten minutes... most of the computation time is spent paging through memory.</p>
  
  <p>Is Mathematica for some reason storing this matrix as a non-sparse matrix while it is building it? Because that would be really really dumb.</p>