6

私は大きな行列nを持っています！xn !、行列式を取る必要があります。nの順列ごとに、関連付けます

  • 長さ2nのベクトル（これは計算上簡単です）
  • in 2n変数の多項式（nで再帰的に計算された線形因子の積）

行列は、ベクトルでの多項式の評価行列です（点として考えられます）。したがって、行列のsigma、tauエントリ（順列によってインデックス付けされます）は、tauのベクトルで評価されたシグマの多項式です。

例：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 := P append point(w);
  w := nextPerm(w);
od;

// BUILD A MATRIX IN MAPLE
M := Matrix(n!, (i,j) -> eval(B[i],P[j]));

// COMPUTE DETERMINANT IN MAPLE
det := LinearAlgebra[Determinant]( M );

// TELL ME IF IT'S NONSINGULAR
if det = 0 then return false;
else return true; fi;

組み込み関数を使用してMapleで作業していLinearAlgebra[Determinant]ますが、それ以外はすべて、低レベルのMaple関数（、、など）を使用するカスタムビルドseq関数convertですcat。

私の問題は、これには時間がかかりすぎることです。つまりn=7、辛抱強く立ち上がることができますが、取得にn=8は数日かかります。理想的には、に到達できるようにしたいと思いますn=10。

誰かが私が時間を改善する方法についてのアイデアを持っていますか？私はMatlabやCなどの別の言語で作業することを受け入れていますが、Maple内でこれを高速化する方法を見つけたいと考えています。

これはすべての厄介な詳細なしでは答えるのが難しいかもしれませんが、各関数のコード、たとえば、、pointはpolyすでに最適化されているので、ここでの本当の問題は、行列式を構築することによって行列式を取得するより速い方法があるかどうかです。飛ぶ、またはそのようなもの。

更新：これは私がいじった2つのアイデアが機能しないものです：

  1. 多項式を長さのベクトルに格納し（計算に時間がかかるため、やり直したくない）、n!その場で点を計算し、これらの値を順列式に代入することができます。行列式の場合：

    順列行列式

    ここでの問題は、これがO(N!)行列のサイズにあることです。したがって、私の場合、これはになりますO((n!)!)。いつn=10、(n!)! = 3,628,800!それはやることを検討するのにさえ大きな方法です。

  2. LU分解を使用して行列式を計算します。幸い、私の行列の主対角線はゼロ以外なので、これは実行可能です。これはO(N^3)マトリックスのサイズであるため、O((n!)^3)実行可能にはるかに近いものになります。ただし、問題は、マトリックス全体を保存する必要があることです。これにより、メモリに深刻な負担がかかり、実行時間を気にする必要がありません。したがって、これも機能しません。少なくとももう少し賢くなければ機能しません。何か案は？

4

2 に答える 2

2

あなたの問題が空間なのか時間なのかは私にはわかりません。明らかに、2つの取引は行ったり来たりします。行列式が正であるかどうかだけを知りたい場合は、間違いなくLU分解を使用する必要があります。その理由は、A = LU下L三角とU上三角がある場合、

det(A) = det(L) det(U) = l_11 * ... * l_nn * u_11 * ... * u_nn

Lしたがって、またはの主な対角要素のいずれかUがであるかどうかを判断するだけで済みます0。

さらに単純化するには、Doolittle のアルゴリズムを使用しl_ii = 1ます。いずれかの時点でアルゴリズムが故障した場合、行列は特異であるため停止できます。要点は次のとおりです。

for k := 1, 2, ..., n do {
  for j := k, k+1, ..., n do {
    u_kj := a_kj - sum_{s=1...k-1} l_ks u_sj;
  }
  for i = k+1, k+2, ..., n do {
    l_ik := (a_ik - sum_{s=1...k-1} l_is u_sk)/u_kk;
  }
}

i重要なのは、 の番目の行Uと のi番目の列を同時に計算できL、前の行/列を知るだけで前に進むことができるということです。このようにして、できる限り多くの処理を並列処理し、必要なだけ保存します。a_ij必要に応じてエントリを計算できるため、長さの 2 つのベクトルを格納するn一方で、さらに 2 つの長さのベクトルn( の行U、 の列L) を生成する必要があります。アルゴリズムにはn^2時間がかかります。さらにいくつかのトリックを見つけることができるかもしれませんが、それはスペースと時間のトレードオフに依存します。

于 2013-03-05T04:27:40.090 に答える
-1

あなたの問題をフォローしたかどうかはわかりません。それは次のとおりですか（または削減されますか）？

n 個の数値の 2 つのベクトルがあり、それらを および と呼ぶxとc、行列要素は の積でkあり(x_k+c_k)、各行/列は および の異なる順序に対応しxますc。

もしそうなら、行列は行/列が繰り返されるため、xまたはに繰り返し値があるときはいつでも行列は特異になると思います。の個別の値を持つcより小さなもので一連のモンテカルロを試してみて、そのケースが一般的に特異でないかどうかを確認してください。 nxc

ブルートフォースに関する限り、あなたの方法は次のとおりです。

  1. 非初心者です
  2. n=7LU の代わりに SVD を試してみるのもよいかもしれません。
于 2013-02-24T09:27:32.497 に答える