title: Reducing time complexity of bilinear interpolation
body: <p>I use bilinear interpolation in my android application. It runs perfectly, but takes a lot of time to get the result. </p>
  
  <p>I test it when xi = 259,920, and yi also = 259,920. The time to response was: Galaxy Note 4 takes 3 sec, 
                            and HTC One M8 takes about 8 sec !. So what I can change or use to reduce the time?!</p>
  
  <p>The code I use for bilinear interpolation: </p>
  
  <pre><code>public static double[] BiInterp(Mat z, ArrayList &lt; Double &gt; xi, ArrayList &lt; Double &gt; yi) {
      // Declare matrix indeces
      int xi_i, yi_i;
      // Initialize output vector
      double zi[] = new double[xi.size()];
      double s00, s01, s10, s11;
      for (int i = 0; i &lt; xi.size(); i++) { // Note: xi.length = yi.length !
          xi_i = xi.get(i).intValue(); // X index without round
          yi_i = yi.get(i).intValue(); // Y index without round
          if (xi_i &lt; z.rows() - 1 &amp;&amp; yi_i &lt; z.cols() - 1 &amp;&amp; xi_i &gt;= 0 &amp;&amp; yi_i &gt;= 0) {
              // Four neighbors of sample pixel
                  s00 = z.get(xi_i,yi_i)[0]; s01 = z.get(xi_i,yi_i + 1)[0];
                  s10 = z.get(xi_i + 1,yi_i)[0];s11 = z.get(xi_i + 1,yi_i + 1)[0];
  
              int neighbor_no = 4; // As bilinear interpolation take 4 neighbors
              double A[][] = new double[neighbor_no][neighbor_no];
  
              A[0][0]=xi_i; A[0][1]=yi_i; A[0][2]=xi_i*yi_i; A[0][3]=1;
              A[1][0]=xi_i; A[1][1]=yi_i+1; A[1][2]=xi_i*(yi_i+1); A[1][3]=1;
              A[2][0]=xi_i+1; A[2][1]=yi_i; A[2][2]=(xi_i+1)*yi_i; A[2][3]=1;
              A[3][0]=xi_i+1; A[3][1]=yi_i+1; A[3][2]=(xi_i+1)*(yi_i+1); A[3][3]=1;
  
              GaussianElimination solveE = new GaussianElimination();
              double b[] = {s00,s01,s10,s11};
              double x[] = solveE.solve(A, b);
              zi[i] = xi.get(i)*x[0] + yi.get(i)*x[1] + xi.get(i)*yi.get(i)*x[2] + x[3];
          }
      }
      return zi;
  }
  </code></pre>
  
  <p>and I use Gaussian elimination to solve the equation of 4 unknown </p>
  
  <pre><code>private static final double EPSILON = 1e-10;
  
  // Gaussian elimination with partial pivoting
  public static double[] solve(double[][] A, double[] b) {
      int N = b.length;
  
      for (int p = 0; p &lt; N; p++) {
  
          // find pivot row and swap
          int max = p;
          for (int i = p + 1; i &lt; N; i++) {
              if (Math.abs(A[i][p]) &gt; Math.abs(A[max][p])) {
                  max = i;
              }
          }
          double[] temp = A[p];
          A[p] = A[max];
          A[max] = temp;
          double t = b[p];
          b[p] = b[max];
          b[max] = t;
  
          // singular or nearly singular
          if (Math.abs(A[p][p]) &lt;= EPSILON) {
              throw new RuntimeException("Matrix is singular or nearly singular");
          }
  
          // pivot within A and b
          for (int i = p + 1; i &lt; N; i++) {
              double alpha = A[i][p] / A[p][p];
              b[i] -= alpha * b[p];
              for (int j = p; j &lt; N; j++) {
                  A[i][j] -= alpha * A[p][j];
              }
          }
      }
  
      // back substitution
      double[] x = new double[N];
      for (int i = N - 1; i &gt;= 0; i--) {
          double sum = 0.0;
          for (int j = i + 1; j &lt; N; j++) {
              sum += A[i][j] * x[j];
          }
          x[i] = (b[i] - sum) / A[i][i];
      }
      return x;
  }
  </code></pre>
  
  <p>As you see in the bilinear code, I take the pixels intensities immediately from the Mat object. However, when I used matrix it takes much less time, such as with note 4 takes 1 sec. </p>
  
  <p>But to convert from Mat image to matrix takes 4 sec. So I preferred to use Mat. </p>