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所以这不是不可能的。