标签: determinants

谁能告诉我哪个是找到大小矩阵的行列式值的最佳算法N x N？

我正在尝试用Java计算逆矩阵.

我正在遵循伴随方法(首先计算伴随矩阵,然后转置这个矩阵,最后,将它乘以行列式值的倒数).

它在矩阵不太大时起作用.我已经检查过,对于尺寸为12x12的矩阵,可以快速得到结果.但是,当矩阵大于12x12时,完成计算所需的时间呈指数增长.

我需要反转的矩阵是19x19,需要花费太多时间.更多时间消耗的方法是用于计算行列式的方法.

我正在使用的代码是:

public static double determinant(double[][] input) {
  int rows = nRows(input);        //number of rows in the matrix
  int columns = nColumns(input); //number of columns in the matrix
  double determinant = 0;

  if ((rows== 1) && (columns == 1)) return input[0][0];

  int sign = 1;     
  for (int column = 0; column < columns; column++) {
    double[][] submatrix = getSubmatrix(input, rows, columns,column);
    determinant = determinant + sign*input[0][column]*determinant(submatrix);
    sign*=-1;
  }
  return determinant;
}   

有人知道如何更有效地计算大矩阵的行列式吗？如果没有,有没有人知道如何使用其他算法计算大矩阵的逆？

谢谢

假设我们有一个方阵M，例如，

set.seed(1)
M <- matrix(rnorm(5*5), 5, 5)

> M
           [,1]       [,2]       [,3]        [,4]        [,5]
[1,] -0.6264538 -0.8204684  1.5117812 -0.04493361  0.91897737
[2,]  0.1836433  0.4874291  0.3898432 -0.01619026  0.78213630
[3,] -0.8356286  0.7383247 -0.6212406  0.94383621  0.07456498
[4,]  1.5952808  0.5757814 -2.2146999  0.82122120 -1.98935170
[5,]  0.3295078 -0.3053884  1.1249309  0.59390132  0.61982575

我想知道是否有一种有效的方法可以找到一个子矩阵，使其行列式是所有子矩阵中的最大值。矩阵的大小应大于1x1但小于或等于5x5。一些子矩阵示例如下

> M[c(1,5),c(2,3)]
           [,1]     [,2]
[1,] -0.8204684 1.511781
[2,] -0.3053884 1.124931

> M[c(1,2,4),c(1,4,5)]
           [,1]        [,2]       [,3]
[1,] -0.6264538 -0.04493361  0.9189774
[2,]  0.1836433 -0.01619026  0.7821363
[3,]  1.5952808  0.82122120 -1.9893517

> M[1:4,2:5] …

我正在尝试计算矩阵(任何大小)的行列式,用于自编码/面试练习.我的第一次尝试是使用递归,这导致我进行以下实现:

import java.util.Scanner.*;
public class Determinant {

    double A[][];
    double m[][];
    int N;
    int start;
    int last;

    public Determinant (double A[][], int N, int start, int last){
            this.A = A;
            this.N = N;
            this.start = start;
            this.last = last;
    }

    public double[][] generateSubArray (double A[][], int N, int j1){
            m = new double[N-1][];
            for (int k=0; k<(N-1); k++)
                    m[k] = new double[N-1];

            for (int i=1; i<N; i++){
                  int j2=0;
                  for (int j=0; j<N; j++){
                      if(j == j1)
                            continue;
                      m[i-1][j2] = …

对于一篇研究论文,我被指派研究用于计算矩阵行列式的最快算法.

我已经知道LU分解和Bareiss算法都在O(n ^ 3)中运行,但在做了一些挖掘之后,似乎有一些算法运行在n ^ 2和n ^ 3之间.

此源(参见第113-114页)和此源(参见第198页)表示存在一个在O(n ^ 2.376)中运行的算法,因为它基于Coppersmith-Winograd的乘法矩阵算法.但是,我还没有找到关于这种算法的任何细节.

我的问题是:

1. 用于计算矩阵行列式的最快创建(非理论)算法是什么？
2. 我在哪里可以找到有关这种最快算法的信息？

非常感谢.

我有以下程序

format compact; format short g; clear; clc;  
L = 140; J = 77; Jm = 10540; G = 0.8*10^8; d = L/3;  
for i=1:500000  
omegan=1.+0.0001*i;

a(1,1) = ((omegan^2)*(Jm/(G*J))*d^2)-2; a(1,2) = 2; a(1,3) = 0; a(1,4) = 0;
a(2,1) = 1; a(2,2) = ((omegan^2)*(Jm/(G*J))*d^2)-2; a(2,3) = 1; a(2,4) = 0;
a(3,1) = 0; a(3,2) = 1; a(3,3) = ((omegan^2)*(Jm/(G*J))*d^2)-2; a(3,4) = 1;
a(4,1) = 0; a(4,2) = 0; a(4,3) = 2; a(4,4) = ((omegan^2)*(Jm/(G*J))*d^2)-2;

if(abs(det(a))<1E-10) sprintf('omegan= %8.3f det= %8.3f',omegan,det(a))
end …

我有一个大矩阵,n!xn !,我需要采取决定因素.对于n的每个排列,我都联想到了

• 一个长度为2n的向量(这很容易计算)
• 2n个变量的多项式(在n上递归计算的线性因子的乘积)

矩阵是向量处的多项式的评估矩阵(被认为是点).因此,矩阵的sigma,tau入口(由置换索引)是在tau的向量处评估的sigma的多项式.

示例:对于n=3,如果第ith个多项式是(x1 - 4)(x3 - 5)(x4 - 4)(x6 - 1)并且第jth个是(2,2,1,3,5,2),那么(i,j)矩阵的第th个条目将是(2 - 4)(1 - 5)(3 - 4)(2 - 1) = -8.这里n=3,所以点在R^(3!) = R^6,多项式有3!=6变量.

我的目标是确定矩阵是否是非奇异的.

我现在的方法是:

• 该函数point采用置换并输出向量
• 该函数poly采用置换并输出多项式
• 该函数nextPerm以字典顺序给出下一个排列

我的代码的删节伪代码版本是这样的:

B := [];
P := [];
w := [1,2,...,n];
while w <> NULL do
  B := B append poly(w);
  P := …

我有兴趣使用TensorFlow计算矩阵行列式的导数.我可以从实验中看出,TensorFlow尚未实现通过行列式区分的方法:

LookupError: No gradient defined for operation 'MatrixDeterminant' 
(op type: MatrixDeterminant)

进一步的调查显示,实际上可以计算导数; 例如,参见Jacobi的公式.我确定为了实现这种通过决定因素来区分我需要使用函数装饰器的方法,

@tf.RegisterGradient("MatrixDeterminant")
def _sub_grad(op, grad):
    ...

但是,我对张量流不熟悉,无法理解如何实现这一目标.有没有人对此事有任何见解？

这是我遇到这个问题的一个例子:

x = tf.Variable(tf.ones(shape=[1]))
y = tf.Variable(tf.ones(shape=[1]))

A = tf.reshape(
    tf.pack([tf.sin(x), tf.zeros([1, ]), tf.zeros([1, ]), tf.cos(y)]), (2,2)
)
loss = tf.square(tf.matrix_determinant(A))


optimizer = tf.train.GradientDescentOptimizer(0.001)
train = optimizer.minimize(loss)

init = tf.initialize_all_variables()
sess = tf.Session()
sess.run(init)


for step in xrange(100):
    sess.run(train)
    print sess.run(x)

numpy.linalg.det正在发出一些我不明白的警告。这并不是每次都会发生，但它是通过下面的示例代码引发的。

警告：“运行时警告：det r = _umath_linalg.det（a，signature=signature）中遇到无效值

matrix = np.array([[1, 1, 1], [3, 3, 3], [4, 4, 4]])
    a = np.linalg.det(matrix)
    print(a)

我四处寻找，但没有找到很多。这篇文章讨论了大型矩阵的溢出问题，但我怀疑这就是这里的问题。

的文档numpy.linalg.det指出

行列式是使用LAPACK例程 z/ dgetrf通过 LU 分解计算的。

我运行了以下运行时测试并拟合了 2、3 和 4 次多项式，因为这涵盖了该表中最不差的选项。该表还提到 LU 分解方法需要 $O(n^3)$ 时间，但此处给出的 LU 分解的理论复杂度为$O(n^{2.376})$。当然，算法的选择很重要，但我不确定我应该期望什么可用的时间复杂度numpy.linalg.det。

from timeit import timeit

import matplotlib.pyplot as plt
import numpy as np
from sklearn.linear_model import LinearRegression
from sklearn.preprocessing import PolynomialFeatures


sizes = np.arange(1,10001, 100)
times = []

for size in sizes:
    A = np.ones((size, size))
    time = timeit('np.linalg.det(A)', globals={'np':np, 'A':A}, number=1)
    times.append(time)
    print(size, time)

sizes = sizes.reshape(-1,1)
times = np.array(times).reshape(-1,1)

quad_sizes = …