ウィキペディアでLLLアルゴリズムを実装しているが、深刻な問題になっている

Question

私の問題がプログラミングやLLLアルゴリズムの概念に関連しているか、Wikipediaで何が言及されているかわかりません。

私はLLLアルゴリズムを実装することを決めました。実際にアルゴリズムを学び、それが本当に機能していることを確認するためには、Wikipedia (step-by-step/line-by-line)に書かれています。

私はそれを実装するためにJavaScript（プログラミング言語）とnode.js（JavaScriptエンジン）を使用し、完全なコードを取得するにはthis is the git repositoryを使用しました。

ストーリーが短いと、例えば3つのベクトル（配列の大きさが3なのでインデックスの最大値は2）があるときなど、Kの値は範囲外になりますが、kは3になりナンセンスになります。

私のコードは、Wikipediaに記載されているアルゴリズムを段階的に（行単位で）実装しています。だから私は問題ではない。ここで

// ** important 
// {b} set of vectors are denoted by this.matrix_before 
// {b*} set of vectors are denoted by this.matrix_after 
calculate_LLL() { 
    this.matrix_after = new gs(this.matrix_before, false).matrix; // initialize after vectors: perform Gram-Schmidt, but do not normalize 
    var flag = false; // invariant 
    var k = 1; 

    while (k <= this.dimensions && !flag) { 
     for (var j = k - 1; j >= 0; j--) { 
      if (Math.abs(this.mu(k, j)) > 0.5) { 
       var to_subtract = tools.multiply(Math.round(this.mu(k, j)), this.matrix_before[j], this.dimensions); 
       this.matrix_before[k] = tools.subtract(this.matrix_before[k], to_subtract, this.dimensions); 

       this.matrix_after = new gs(this.matrix_before, false).matrix; // update after vectors: perform Gram-Schmidt, but do not normalize 
      } 
     } 

     if (tools.dot_product(this.matrix_after[k], this.matrix_after[k], this.dimensions) >= (this.delta - Math.pow(this.mu(k, k - 1), 2)) * tools.dot_product(this.matrix_after[k - 1], this.matrix_after[k - 1], this.dimensions)) { 
      if (k + 1 >= this.dimensions) { // invariant: there is some issue, something is wrong 
       flag = true; // invariant is broken 
       console.log("something bad happened ! (1)"); 
      } 

      k++; 
      // console.log("if; k, j"); 
      // console.log(k + ", " + j); 
     } else { 
      var temp_matrix = this.matrix_before[k]; 
      this.matrix_before[k] = this.matrix_before[k - 1]; 
      this.matrix_before[k - 1] = temp_matrix; 

      this.matrix_after = new gs(this.matrix_before, false).matrix; // update after vectors: perform Gram-Schmidt, but do not normalize 

      if (k === Math.max(k - 1, 1) || k >= this.dimensions || Math.max(k - 1, 1) >= this.dimensions) { // invariant: there is some issue, something is wrong 
       flag = true; // invariant is broken 
       console.log("something bad happened ! (2)"); 
      } 
      k = Math.max(k - 1, 1); 

      // console.log("else; k, j"); 
      // console.log(k + ", " + j); 
     } 

     console.log(this.matrix_before); 
     console.log("\n"); 

    } // I added this flag variable to prevent getting exceptions and terminate the loop gracefully 

    console.log("final: "); 
    console.log(this.matrix_before); 
} 

// calculated mu as been mentioned on Wikipedia 
// mu(i, j) = <b_i, b*_j>/<b*_j, b*_j> 
mu(i, j) { 
    var top = tools.dot_product(this.matrix_before[i], this.matrix_after[j], this.dimensions); 
    var bottom = tools.dot_product(this.matrix_after[j], this.matrix_after[j], this.dimensions); 

    return top/bottom; 
} 

はWikipediaであるアルゴリズムのスクリーンショットです：

---

更新＃1：私はそれを望んで質問を明確にするために、コードに多くのコメントを追加しました誰かが助けになるだろう。

コードの既に使用可能な実装について疑問がある場合は、LatticeReduce[{{0,1},{2,0}}] wolfram alphaと入力して、このコードの動作を確認してください。

更新＃2：私はより多くのコードをクリーンアップし、グラム・シュミットのコードが正しく動作されていることを確認するために検証機能を追加しましたが、まだコードは失敗し、kの値は、次元数（またはベクトルの数）を超えるdoesnのどの意味をなさない。

Answer 1

ウィキペディアのアルゴリズムの説明では、むしろ奇数表記を使用しています - ベクトルには0..n（たとえば0..n-1または1..n）の番号が付けられているため、ベクトルの総数はn +1。

ここに投稿したコードは、this.dimensionsをWikipediaの説明のnに対応するものとして扱います。今のところそれは間違っていません。

ただし、GitHubのフルソースファイルのコンストラクタはthis.dimensions = matrix[0].lengthと設定されています。このことについて2つのことが間違っています。最初は、確かにmatrix[0].lengthがm（空間の次元）よりもn（不明瞭な理由でベクトルの数から1を引いたもの）よりも似ていることです。 2番目は、nの場合は、ベクトルの数がnではなくn + 1であるため、1を減算する必要があるということです。

this.dimensionsをnとして意味する場合は、matrix.length-1として初期化する必要があります。あなたのテストケースの正方行列では、matrix[0].length-1を使っても動作しますが、非正方行列でフィードするとコードが破損すると思います。 dimensionsという名前もちょっと誤解を招きます。おそらくちょうどnをウィキペディアの説明と一致させるには？

nVectorsのように、matrix.lengthと同じにして、残りのコードを適切に変更することができます。これは、メインループの終了条件の調整を意味します。