title: Increase speed of finding minimum element in a 2-D numpy array which has many entries set to np.inf
body: <p>I have a 16000*16000 matrix and want to find the minimum entry. This matrix is a distance matrix, so it is symmetric about diagonal. In order to get exactly one minimum at each time, I set the lower triangle and the diagonal to <code>np.inf</code>. Below is an 5*5 matrix example:</p>
  <pre><code>inf a0  a1  a2  a3
  inf inf a4  a5  a6
  inf inf inf a7  a8
  inf inf inf inf a9
  inf inf inf inf inf
  </code></pre>
  <p>I want to find the index of the minimum entry only in the upper triangle. However, when I use <code>np.argmin()</code>, it will still go through the whole matrix. Is there any way to &quot;ignore&quot; the lower triangle and increase speed?</p>
  <p>I have tried many methods, such as:</p>
  <ol>
  <li>Use masked array</li>
  <li>Use <code>triu_indices()</code> to extract the upper triangle and then find the minimum</li>
  <li>Set the entries in the lower triangle and diagonal to <code>None</code> instead of <code>np.inf</code>, then use <code>np.nanargmin()</code> to find the minimum</li>
  </ol>
  <p>However, all of the methods I tried are slower the using <code>np.argmin()</code> directly.</p>
  <p>Thank you for your time, I would appreciate it if you can help me.</p>
  <p><em><strong>UPDATE 1: Some background of my problem</strong></em></p>
  <p>In fact, I am implementing a modified version of agglomerative clustering from scratch. The original dataset is 16000*64 (I have 16000 points, each is 64-dimensional). At first, I build 16000 clusters and each contains exactly one point. In each iteration, I find the nearest 2 clusters and merge them, until meet the terminate condition.</p>
  <p>To avoid repeated calculation of distances, I store the distances in a 16000*16000 distance matrix. I set the diagonal and lower triangle to <code>np.inf</code>. In each iteration, I will find the smallest entry in the distance matrix, and the index of this entry corresponds to the 2 nearest clusters, say <code>c_i</code> and <code>c_j</code>. Afterwards, in the distance matrix, I fill the 2 rows and 2 columns corresponding to <code>c_i</code> and <code>c_j</code> to np.inf, which means that these 2 clusters are merged and do not exist anymore. Then I will calculate an array of the distances between the new cluster and all other clusters, then put the array in the 1 row and 1 column corresponding to <code>c_i</code>.</p>
  <p>Let me make it clear: in the whole process, the size of the distance matrix never change. In each iteration, for the 2 rows and 2 columns correspond to the 2 nearest clusters I found, I fill 1 row and 1 column with <code>np.inf</code> and put the distance array of the new cluster in the other 1 row and 1 column.</p>
  <p>Now the bottleneck of the performance is finding the smallest entry in the distance matrix, which takes 0.008s. The run time of the whole algorithm is about 40 minutes.</p>
  <p><em><strong>UPDATE 2: How I compute distance matrix</strong></em></p>
  <p>Below is the code I used to generate distance matrix:</p>
  <pre><code>from sklearn.metrics import pairwise_distances
  
  dis_matrix = pairwise_distances(dataset)
  
  for i in range(num_dim):
      for j in range(num_dim):
          if i &gt;= j or (cluster_list[i].contain_reference_point and cluster_list[j].contain_reference_point):
              dis_matrix[i][j] = np.inf
  </code></pre>
  <p>Nevertheless, I need to say that generating the distance matrix is not the bottleneck in the algorithm now, because I generate it only once, and then I just update the distance matrix (as mentioned above).</p>