Matrix Computing太慢

Question

我正在開發名爲Lights Out的遊戲。所以爲了解決這個問題，我必須在模塊2中計算出AX = B的答案。所以，由於這個原因我選擇了jscience庫。在這個遊戲中，A的大小是25x25矩陣，X和B都是25x1矩陣。我寫的代碼，如下：

AllLightOut.java類：

public class AllLightOut { 
    public static final int SIZE = 5; 

    public static double[] Action(int i, int j) { 
     double[] change = new double[SIZE * SIZE]; 
     int count = 0; 

     for (double[] d : Switch(new double[SIZE][SIZE], i, j)) 
      for (double e : d) 
       change[count++] = e; 

     return change; 
    } 

    public static double[][] MatrixA() { 
     double[][] mat = new double[SIZE * SIZE][SIZE * SIZE]; 

     for (int i = 0; i < SIZE; i++) 
      for (int j = 0; j < SIZE; j++) 
       mat[i * SIZE + j] = Action(i, j); 

     return mat; 
    } 

    public static SparseVector<ModuloInteger> ArrayToDenseVectorModule2(
      double[] array) { 
     List<ModuloInteger> list = new ArrayList<ModuloInteger>(); 

     for (int i = 0; i < array.length; i++) { 
      if (array[i] == 0) 
       list.add(ModuloInteger.ZERO); 
      else 
       list.add(ModuloInteger.ONE); 
     } 

     return SparseVector.valueOf(DenseVector.valueOf(list), 
       ModuloInteger.ZERO); 
    } 

    public static SparseMatrix<ModuloInteger> MatrixAModule2() { 
     double[][] mat = MatrixA(); 
     List<DenseVector<ModuloInteger>> list = new ArrayList<DenseVector<ModuloInteger>>(); 

     for (int i = 0; i < mat.length; i++) { 
      List<ModuloInteger> l = new ArrayList<ModuloInteger>(); 
      for (int j = 0; j < mat[i].length; j++) { 
       if (mat[i][j] == 0) 
        l.add(ModuloInteger.ZERO); 
       else 
        l.add(ModuloInteger.ONE); 
      } 

      list.add(DenseVector.valueOf(l)); 
     } 

     return SparseMatrix.valueOf(DenseMatrix.valueOf(list), 
       ModuloInteger.ZERO); 
    } 

    public static double[][] Switch(double[][] action, int i, int j) { 
     action[i][j] = action[i][j] == 1 ? 0 : 1; 

     if (i > 0) 
      action[i - 1][j] = action[i - 1][j] == 1 ? 0 : 1; 

     if (i < action.length - 1) 
      action[i + 1][j] = action[i + 1][j] == 1 ? 0 : 1; 

     if (j > 0) 
      action[i][j - 1] = action[i][j - 1] == 1 ? 0 : 1; 

     if (j < action.length - 1) 
      action[i][j + 1] = action[i][j + 1] == 1 ? 0 : 1; 

     return action; 
    } 
} 

和主類是如下：

public class Main { 
    public static void main(String[] args) { 
     double[] bVec = new double[] { 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 
       1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0 }; 

     SparseMatrix<ModuloInteger> matA = AllLightOut.MatrixAModule2(); 
     SparseVector<ModuloInteger> matB = AllLightOut 
       .ArrayToDenseVectorModule2(bVec); 

     ModuloInteger.setModulus(LargeInteger.valueOf(2)); 
    Vector<ModuloInteger> matX = matA.solve(matB); 

     System.out.println(matX); 
    } 
} 

我跑這個節目約30分鐘，但它不會導致。我的代碼是否包含致命錯誤或錯誤？爲什麼需要太長時間？

感謝您的關注:)

編輯 放緩在這條線Matrix<ModuloInteger> matX = matA.inverse();發生。請注意，這個庫的速度非常高，但我不知道爲什麼我的程序運行速度太慢！

EDIT2 請注意，當我嘗試SIZE = 3，我真的得到答案。例如： MATA：

{{1, 1, 0, 1, 0, 0, 0, 0, 0}, 
{1, 1, 1, 0, 1, 0, 0, 0, 0}, 
{0, 1, 1, 0, 0, 1, 0, 0, 0}, 
{1, 0, 0, 1, 1, 0, 1, 0, 0}, 
{0, 1, 0, 1, 1, 1, 0, 1, 0}, 
{0, 0, 1, 0, 1, 1, 0, 0, 1}, 
{0, 0, 0, 1, 0, 0, 1, 1, 0}, 
{0, 0, 0, 0, 1, 0, 1, 1, 1}, 
{0, 0, 0, 0, 0, 1, 0, 1, 1}} 

MATB：

{1，1，1，1，1，1，1，0，0}

MatC：

{0,0,1,1,0,0,0,0,0}

但是，當我嘗試SIZE = 5，發生放緩。

Answer 1

放緩在此行Matrix<ModuloInteger> matX = matA.inverse();

這將是因爲係數矩陣matA不可逆爲SIZE == 5（或4，9，11，14，16，...？）的發生。

我有點驚訝庫沒有檢測出，並拋出一個異常。如果庫嘗試反轉矩陣solve()，這將導致同樣的後果。

對於某些尺寸的係數矩陣的奇異性的一個後果是並不是所有這些尺寸的謎題都是可解的，而其他的則有多個解。由於我們正在計算模2，所以我們可以使用位或boolean s來建模我們的狀態/切換，使用XOR進行加法，&進行乘法運算。我已經熟了用高斯消元法簡單的求解，也許它可以幫助你（我沒有花太多時間思考設計，所以它不是漂亮）：

public class Lights{ 
    private static final int SIZE = 5; 

    private static boolean[] toggle(int i, int j) { 
     boolean[] action = new boolean[SIZE*SIZE]; 
     int idx = i*SIZE+j; 
     action[idx] = true; 
     if (j > 0)  action[idx-1] = true; 
     if (j < SIZE-1) action[idx+1] = true; 
     if (i > 0)  action[idx-SIZE] = true; 
     if (i < SIZE-1) action[idx+SIZE] = true; 
     return action; 
    } 
    private static boolean[][] matrixA() { 
     boolean[][] mat = new boolean[SIZE*SIZE][]; 
     for(int i = 0; i < SIZE; ++i) { 
      for(int j = 0; j < SIZE; ++j) { 
       mat[i*SIZE+j] = toggle(i,j); 
      } 
     } 
     return mat; 
    } 
    private static void rotateR(boolean[] a, int r) { 
     r %= a.length; 
     if (r < 0) r += a.length; 
     if (r == 0) return; 
     boolean[] tmp = new boolean[r]; 
     for(int i = 0; i < r; ++i) { 
      tmp[i] = a[i]; 
     } 
     for(int i = 0; i < a.length - r; ++i) { 
      a[i] = a[i+r]; 
     } 
     for(int i = 0; i < r; ++i) { 
      a[i + a.length - r] = tmp[i]; 
     } 
    } 
    private static void rotateR(boolean[][] a, int r) { 
     r %= a.length; 
     if (r < 0) r += a.length; 
     if (r == 0) return; 
     boolean[][] tmp = new boolean[r][]; 
     for(int i = 0; i < r; ++i) { 
      tmp[i] = a[i]; 
     } 
     for(int i = 0; i < a.length - r; ++i) { 
      a[i] = a[i+r]; 
     } 
     for(int i = 0; i < r; ++i) { 
      a[i + a.length - r] = tmp[i]; 
     } 
    } 
    private static int count(boolean[] a) { 
     int c = 0; 
     for(int i = 0; i < a.length; ++i) { 
      if (a[i]) ++c; 
     } 
     return c; 
    } 
    private static void swapBits(boolean[] a, int i, int j) { 
     boolean tmp = a[i]; 
     a[i] = a[j]; 
     a[j] = tmp; 
    } 
    private static void addBit(boolean[] a, int i, int j) { 
     a[j] ^= a[i]; 
    } 
    private static void swapRows(boolean[][] a, int i, int j) { 
     boolean[] tmp = a[i]; 
     a[i] = a[j]; 
     a[j] = tmp; 
    } 
    private static void xorb(boolean[] a, boolean[] b) { 
     for(int i = 0; i < a.length; ++i) { 
      a[i] ^= b[i]; 
     } 
    } 
    private static boolean[] boolBits(int bits, long param) { 
     boolean[] bitArr = new boolean[bits]; 
     for(int i = 0; i < bits; ++i) { 
      if (((param >> i) & 1L) != 0) { 
       bitArr[i] = true; 
      } 
     } 
     return bitArr; 
    } 
    private static boolean[] solve(boolean[][] m, boolean[] b) { 
     // Move first SIZE rows to bottom, so that on the diagonal 
     // above the lowest SIZE rows, there are unit matrices 
     rotateR(m, SIZE); 
     // modify right hand side accordingly 
     rotateR(b,SIZE); 
     // clean first SIZE*(SIZE-1) columns 
     for(int i = 0; i < SIZE*(SIZE-1); ++i) { 
      for(int k = 0; k < SIZE*SIZE; ++k) { 
       if (k == i) continue; 
       if (m[k][i]) { 
        xorb(m[k], m[i]); 
        b[k] ^= b[i]; 
       } 
      } 
     } 
     // Now we have a block matrix 
     /* 
     * E 0 0 ... 0 X 
     * 0 E 0 ... 0 X 
     * 0 0 E ... 0 X 
     * ... 
     * 0 0 ... E 0 X 
     * 0 0 ... 0 E X 
     * 0 0 ... 0 0 Y 
     * 
     */ 
     // Bring Y to row-echelon form 
     int i = SIZE*(SIZE-1), j, k, mi = i; 
     while(mi < SIZE*SIZE){ 
      // Try to find a row with mi-th bit set 
      for(j = i; j < SIZE*SIZE; ++j) { 
       if (m[j][mi]) break; 
      } 
      if (j < SIZE*SIZE) { 
       // Found one 
       if (j > i) { 
        swapRows(m,i,j); 
        swapBits(b,i,j); 
       } 
       for(k = 0; k < SIZE*SIZE; ++k) { 
        if (k == i) continue; 
        if (m[k][mi]) { 
         xorb(m[k], m[i]); 
         b[k] ^= b[i]; 
        } 
       } 
       // cleaned up column, good row, next 
       ++i; 
      } 
      // Look at next column 
      ++mi; 
     } 
     printMat(m,b); 
     boolean[] best = b; 
     if (i < SIZE*SIZE) { 
      // We have zero-rows in the matrix, 
      // check whether the puzzle is solvable at all, 
      // i.e. all corresponding bits in the rhs are 0 
      for(j = i; j < SIZE*SIZE; ++j) { 
       if (b[j]) { 
        System.out.println("Puzzle not solvable, some lights must remain lit."); 
        break; 
//      throw new IllegalArgumentException("Puzzle is not solvable!"); 
       } 
      } 
      // Pretending it were solvable if not 
      if (j < SIZE*SIZE) { 
       System.out.println("Pretending the puzzle were solvable..."); 
       for(; j < SIZE*SIZE; ++j) { 
        b[j] = false; 
       } 
      } 
      // Okay, puzzle is solvable, but there are several solutions 
      // Let's try to find the one with the least toggles. 

      // We have the canonical solution with last bits all zero 
      int toggles = count(b); 
      System.out.println(toggles + " toggles in canonical solution"); 
      int freeBits = SIZE*SIZE - i; 
      long max = 1L << freeBits; 
      System.out.println(freeBits + " free bits"); 
      // Check all combinations of free bits whether they produce 
      // something better 
      for(long param = 1; param < max; ++param) { 
       boolean[] base = boolBits(freeBits,param); 
       boolean[] c = new boolean[SIZE*SIZE]; 
       for(k = 0; k < freeBits; ++k) { 
        c[i+k] = base[k]; 
       } 
       for(k = 0; k < i; ++k) { 
        for(j = 0; j < freeBits; ++j) { 
         c[k] ^= base[j] && m[k][j+i]; 
        } 
       } 
       xorb(c,b); 
       int t = count(c); 
       if (t < toggles) { 
        System.out.printf("Found new best for param %x, %d toggles\n",param,t); 
        printMat(m,c,b); 
        toggles = t; 
        best = c; 
       } else { 
        System.out.printf("%d toggles for parameter %x\n", t, param); 
       } 
      } 
     } 
     return best; 
    } 
    private static boolean[] parseLights(int[] lights) { 
     int lim = lights.length; 
     if (SIZE*SIZE < lim) lim = SIZE*SIZE; 
     boolean[] b = new boolean[SIZE*SIZE]; 
     for(int i = 0; i < lim; ++i) { 
      b[i] = (lights[i] != 0); 
     } 
     return b; 
    } 
    private static void printToggles(boolean[] s) { 
     for(int i = 0; i < s.length; ++i) { 
      if (s[i]) { 
       System.out.print("(" + (i/SIZE + 1) + ", " + (i%SIZE + 1) + "); "); 
      } 
     } 
     System.out.println(); 
    } 
    private static void printMat(boolean[][] a, boolean[] rhs) { 
     for(int i = 0; i < SIZE*SIZE; ++i) { 
      for(int j = 0; j < SIZE*SIZE; ++j) { 
       System.out.print((a[i][j] ? "1 " : "0 ")); 
      } 
      System.out.println("| " + (rhs[i] ? "1" : "0")); 
     } 
    } 
    private static void printMat(boolean[][] a, boolean[] sol, boolean[] rhs) { 
     for(int i = 0; i < SIZE*SIZE; ++i) { 
      for(int j = 0; j < SIZE*SIZE; ++j) { 
       System.out.print((a[i][j] ? "1 " : "0 ")); 
      } 
      System.out.println("| " + (sol[i] ? "1" : "0") + " | " + (rhs[i] ? "1" : "0")); 
     } 
    } 
    private static void printGrid(boolean[] g) { 
     for(int i = 0; i < SIZE; ++i) { 
      for(int j = 0; j < SIZE; ++j) { 
       System.out.print(g[i*SIZE+j] ? "1" : "0"); 
      } 
      System.out.println(); 
     } 
    } 
    public static void main(String[] args) { 
     int[] initialLights = new int[] { 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 
       1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0 }; 
     boolean[] b = parseLights(initialLights); 
     boolean[] b2 = b.clone(); 
     boolean[][] coefficients = matrixA(); 
     boolean[] toggles = solve(coefficients, b); 
     printGrid(b2); 
     System.out.println("--------"); 
     boolean[][] check = matrixA(); 
     boolean[] verify = new boolean[SIZE*SIZE]; 
     for(int i = 0; i < SIZE*SIZE; ++i) { 
      if (toggles[i]) { 
       xorb(verify, check[i]); 
      } 
     } 
     printGrid(verify); 
     xorb(b2,verify); 
     if (count(b2) > 0) { 
      System.out.println("Aww, shuck, screwed up!"); 
      printGrid(b2); 
     } 
     printToggles(toggles); 
    } 
} 

Answer 2

如果可以避免的話，您幾乎從不想計算矩陣的實際逆矩陣。這樣的操作是有問題的並且非常耗時。查看JScience的文檔是否考慮使用解決方法？沿着MATX = matA.solve（MATB）線的東西應該給你你在找什麼，我懷疑他們正在使用逆來計算，雖然我沒有挖那麼遠到JScience所以這不是不可能的。