巨大矩阵Java的行列式

Question

我正在用Java做一个项目，我必须使用BigInteger类来实现加密方法。

我有平方矩阵nxn，其中n可以是200，我需要计算行列式。我用子矩阵的行列式做了这个方法，但计算起来花了很长时间。

public BigInteger determinant(Matrix matrix){
    if (matrix.getColumns()!=matrix.getRows()){
        System.out.println("The matrix is not square");
        return BigInteger.valueOf(-1);
    }
    if (matrix.getColumns() == 1) {
    return matrix.getMatrix()[0][0];
    }
    if (matrix.getRows()==2) {
        return ((matrix.getValueAt(0, 0).multiply(matrix.getValueAt(1, 1)))).subtract(( matrix.getValueAt(0, 1).multiply(matrix.getValueAt(1, 0))));
    }
    BigInteger sum = BigInteger.valueOf(0);
    for (int i=0; i<matrix.getColumns(); i++) {
        sum = sum.add(this.changeSign(BigInteger.valueOf(i)).multiply(matrix.getValueAt(0, i)).multiply(determinant(createSubMatrix(matrix, 0, i))));// * determinant(createSubMatrix(matrix, 0, i));
    }
    return sum;
    } 

有没有一种非递归的方法来计算行列式？

提前谢谢。

Answer 1

我已经把它作为评论发布了，但我认为这实际上可以解决你的问题，所以我也把它作为答案发布。您可以使用此软件包：http://math.nist.gov/javanumerics/jama/

Answer 2

计算大型矩阵的行列式的一种常见做法是使用LUP分解。在这种情况下，可以使用以下思想来计算死者：

{L, U, P} = LUP(A)
sign = -1 ^ 'number of permutations in P'
det(A) = diagonalProduct(U) * sign

这就是大型数学包的作用。您可能应该自己实现LU。

Answer 3

我相信这正是您所需要的。使用此类，您可以计算任何维度的矩阵的行列式

这个类使用许多不同的方法来使矩阵成为三角形，然后计算它的行列式。它可以用于500 x 500甚至更高维的矩阵。这个类的好处是，您可以在BigDecimal中得到结果，所以不存在无穷大，您将始终得到准确的答案。顺便说一句，使用许多不同的方法并避免递归会带来更快的方法和更高的性能。希望这会有所帮助。

import java.math.BigDecimal;

public class DeterminantCalc {
private double[][] matrix;
private int sign = 1;

DeterminantCalc(double[][] matrix) {
    this.matrix = matrix;
}
public int getSign() {
    return sign;
}
public BigDecimal determinant() {
    BigDecimal deter;
    if (isUpperTriangular() || isLowerTriangular())
        deter = multiplyDiameter().multiply(BigDecimal.valueOf(sign));
    else {
        makeTriangular();
        deter = multiplyDiameter().multiply(BigDecimal.valueOf(sign));
    }
    return deter;
}

/*  receives a matrix and makes it triangular using allowed operations
    on columns and rows
*/
public void makeTriangular() {
    for (int j = 0; j < matrix.length; j++) {
        sortCol(j);
        for (int i = matrix.length - 1; i > j; i--) {
            if (matrix[i][j] == 0)
                continue;
            double x = matrix[i][j];
            double y = matrix[i - 1][j];
            multiplyRow(i, (-y / x));
            addRow(i, i - 1);
            multiplyRow(i, (-x / y));
        }
    }
}

public boolean isUpperTriangular() {
    if (matrix.length < 2)
        return false;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < i; j++) {
            if (matrix[i][j] != 0)
                return false;
        }
    }
    return true;
}

public boolean isLowerTriangular() {
    if (matrix.length < 2)
        return false;
    for (int j = 0; j < matrix.length; j++) {
        for (int i = 0; j > i; i++) {
            if (matrix[i][j] != 0)
                return false;
        }
    }
    return true;
}

public BigDecimal multiplyDiameter() {
    BigDecimal result = BigDecimal.ONE;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix.length; j++) {
            if (i == j)
                result = result.multiply(BigDecimal.valueOf(matrix[i][j]));
        }
    }
    return result;
}

// when matrix[i][j] = 0 it makes it's value non-zero
public void makeNonZero(int rowPos, int colPos) {
    int len = matrix.length;
    outer:
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            if (matrix[i][j] != 0) {
                if (i == rowPos) { // found "!= 0" in it's own row, so cols must be added
                    addCol(colPos, j);
                    break outer;
                }
                if (j == colPos) { // found "!= 0" in it's own col, so rows must be added
                    addRow(rowPos, i);
                    break outer;
                }
            }
        }
    }
}

//add row1 to row2 and store in row1
public void addRow(int row1, int row2) {
    for (int j = 0; j < matrix.length; j++)
        matrix[row1][j] += matrix[row2][j];
}

//add col1 to col2 and store in col1
public void addCol(int col1, int col2) {
    for (int i = 0; i < matrix.length; i++)
        matrix[i][col1] += matrix[i][col2];
}

//multiply the whole row by num
public void multiplyRow(int row, double num) {
    if (num < 0)
        sign *= -1;

    for (int j = 0; j < matrix.length; j++) {
        matrix[row][j] *= num;
    }
}

//multiply the whole column by num
public void multiplyCol(int col, double num) {
    if (num < 0)
        sign *= -1;
    for (int i = 0; i < matrix.length; i++)
        matrix[i][col] *= num;
}

// sort the cols from the biggest to the lowest value
public void sortCol(int col) {
    for (int i = matrix.length - 1; i >= col; i--) {
        for (int k = matrix.length - 1; k >= col; k--) {
            double tmp1 = matrix[i][col];
            double tmp2 = matrix[k][col];
            if (Math.abs(tmp1) < Math.abs(tmp2))
                replaceRow(i, k);
        }
    }
}

//replace row1 with row2
public void replaceRow(int row1, int row2) {
    if (row1 != row2)
        sign *= -1;
    double[] tempRow = new double[matrix.length];
    for (int j = 0; j < matrix.length; j++) {
        tempRow[j] = matrix[row1][j];
        matrix[row1][j] = matrix[row2][j];
        matrix[row2][j] = tempRow[j];
    }
}

//replace col1 with col2
public void replaceCol(int col1, int col2) {
    if (col1 != col2)
        sign *= -1;
    System.out.printf("replace col%d with col%d, sign = %d%n", col1, col2, sign);
    double[][] tempCol = new double[matrix.length][1];
    for (int i = 0; i < matrix.length; i++) {
        tempCol[i][0] = matrix[i][col1];
        matrix[i][col1] = matrix[i][col2];
        matrix[i][col2] = tempCol[i][0];
    }
}

}

然后这个类从用户那里接收一个n x n的矩阵，或者可以生成一个nxn的随机矩阵，然后计算它的行列式。它还展示了解和最终的三角矩阵。

import java.math.BigDecimal;
import java.security.SecureRandom;
import java.text.NumberFormat;
import java.util.Scanner;

public class DeterminantTest {
public static void main(String[] args) {
    String determinant;
    //generating random numbers
int len = 500;
SecureRandom random = new SecureRandom();
double[][] matrix = new double[len][len];
for (int i = 0; i < len; i++) {
    for (int j = 0; j < len; j++) {
        matrix[i][j] = random.nextInt(500);
        System.out.printf("%15.2f", matrix[i][j]);
    }
}
System.out.println();
/*double[][] matrix = {
    {1, 5, 2, -2, 3, 2, 5, 1, 0, 5},
    {4, 6, 0, -2, -2, 0, 1, 1, -2, 1},
    {0, 5, 1, 0, 1, -5, -9, 0, 4, 1},
    {2, 3, 5, -1, 2, 2, 0, 4, 5, -1},
    {1, 0, 3, -1, 5, 1, 0, 2, 0, 2},
    {1, 1, 0, -2, 5, 1, 2, 1, 1, 6},
    {1, 0, 1, -1, 1, 1, 0, 1, 1, 1},
    {1, 5, 5, 0, 3, 5, 5, 0, 0, 6},
    {1, -5, 2, -2, 3, 2, 5, 1, 1, 5},
    {1, 5, -2, -2, 3, 1, 5, 0, 0, 1}
};
    double[][] matrix = menu();*/
    DeterminantCalc deter = new DeterminantCalc(matrix);
    BigDecimal det = deter.determinant();
    determinant = NumberFormat.getInstance().format(det);
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix.length; j++) {
            System.out.printf("%15.2f", matrix[i][j]);
        }
        System.out.println();
    }
    System.out.println();
    System.out.printf("%s%s%n", "Determinant: ", determinant);
    System.out.printf("%s%d", "sign: ", deter.getSign());
}

public static double[][] menu() {
    Scanner scanner = new Scanner(System.in);
    System.out.print("Matrix Dimension: ");
    int dim = scanner.nextInt();
    double[][] inputMatrix = new double[dim][dim];
    System.out.println("Set the Matrix: ");
    for (int i = 0; i < dim; i++) {
        System.out.printf("%5s%d%n", "row", i + 1);
        for (int j = 0; j < dim; j++) {
            System.out.printf("M[%d][%d] = ", i + 1, j + 1);
            inputMatrix[i][j] = scanner.nextDouble();
        }
        System.out.println();
    }
    scanner.close();
    return inputMatrix;
}

}

Answer 4

递归方法需要很长时间才能找到维度大于10x10的矩阵的行列式。您需要进行LU分解和高斯归约。我用它找到了1000x1000矩阵的行列式，它在一秒内得到了正确的结果。你可以在数字食谱书（只使用第三版）中得到这个代码：第52行。它是用C++编写的，但你可以很容易地用Java 进行转换

否则，请在此中检查ludcmp（）https://www.cc.gatech.edu/gvu/people/Phd/warren/matrix.c