Добрый вечер!
Недавно я столкнулся со следующей проблемой: в процессе решения некой задачи мне понадобилось считать определитель достаточно специфичной матрицы:
1) Ее размер может быть до 600.
2) Все ее элементы — целые числа из множества { - 1, 0, 1}.
3) В любой ее строке и столбце не более 4 ненулевых элементов — то есть, она сильно разрежена (вообще говоря, это матрица смежности некого двудольного графа, но некоторые ребра взяты с минусом).
Притом определители надо подсчитать приблизительно у сотни таких матриц.
Я скопировал код с e-maxx.ru, и переписал все на Java, но сомневаюсь в эффективности полученного кода. Детерминант, очевидно, может быть очень большим, из-за чего приходится пользоваться BigDecimal и BigInteger с округлениями. По всем этим причинам код работает жутко медленно и нуждается в оптимизации.
public static BigInteger determinant(final int[][] matr) {
int accuracy = 20;
BigDecimal EPS = BigDecimal.valueOf(0.00000000001);
int n = matr.length;
BigDecimal[][] a = new BigDecimal[n][n];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
a[i][j] = new BigDecimal(matr[i][j]);
a[i][j].setScale(accuracy, BigDecimal.ROUND_HALF_UP);
}
BigDecimal det = new BigDecimal(1.0);
det.setScale(accuracy, BigDecimal.ROUND_HALF_UP);
for (int i = 0; i < n; ++i) {
int k = i;
for (int j = i + 1; j < n; ++j)
if (a[j][i].abs().compareTo(a[k][i].abs()) > 0)
k = j;
if (a[k][i].abs().compareTo(EPS) < 0) {
det = new BigDecimal(0.0);
det.setScale(accuracy, BigDecimal.ROUND_HALF_UP);
break;
}
BigDecimal[] tmp = a[i];
a[i] = a[k];
a[k] = tmp;
if (i != k)
det = det.divide(new BigDecimal(-1), accuracy, BigDecimal.ROUND_HALF_UP);
det = det.multiply(a[i][i]);
for (int j = i + 1; j < n; ++j)
a[i][j] = a[i][j].divide(a[i][i], accuracy, BigDecimal.ROUND_HALF_UP);
for (int j = 0; j < n; ++j)
if (j != i && a[j][i].abs().compareTo(EPS) > 0)
for (int kk = i + 1; kk < n; ++kk) {
BigDecimal aikji = new BigDecimal(1.0);
aikji.setScale(accuracy, BigDecimal.ROUND_HALF_UP);
aikji = aikji.multiply(a[i][kk]);
aikji = aikji.multiply(a[j][i]);
aikji = aikji.multiply(new BigDecimal(-1));
a[j][kk] = a[j][kk].add(aikji);
}
}
det = det.abs();
det = det.add(new BigDecimal(0.00001));
return det.abs().toBigInteger();
}
На Java я начал писать сравнительно недавно, и, возможно, упускаю какие-то моменты для оптимизации. Может ли кто-нибудь дать совет по коду, или привести ссылку на уже реализованный оптимизированный алгоритм?
