Wdrażanie algorytmu LLL, jak już powiedziano na Wikipedii, ale wpadnięcie w poważne problemy

Question

Nie jestem pewien, czy mój problem jest związany z programowaniem lub związany z koncepcją algorytmu LLL i co zostało wspomniane na Wikipedii.

Postanowiłem zaimplementować algorytm LLL, tak jak został napisany na Wikipedia (step-by-step/line-by-line), aby rzeczywiście nauczyć się algorytmu i upewnić się, że naprawdę działa, ale otrzymuję nieoczekiwane lub nieprawidłowe wyniki.

Używam JavaScript (język programowania) i node.js (silnik JavaScript), aby go wdrożyć, i this is the git repository, aby uzyskać pełny kod.

Krótka historia, wartość K wychodzi poza zakres, na przykład, gdy mamy tylko 3 wektory (rozmiar tablicy to 3, zatem maksymalna wartość indeksu wynosi 2), ale k staje się 3 i jest nonsensem.

Mój kod jest krok po kroku implementacją algorytmu wymienionego na Wikipedia, a to, co zrobiłem, było tylko jego implementacją. Więc nie wiem, o co chodzi.

// ** 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; 
} 

Oto zrzut ekranu z algorytmu, który jest na Wikipedii:

---

Aktualizacja # 1: Dodałem więcej komentarzy do kodu, aby wyjaśnić kwestię, mając nadzieję, że ktoś by pomógł.

W przypadku, gdy zastanawiasz się nad już dostępną implementacją kodu, możesz wpisać: LatticeReduce[{{0,1},{2,0}}] wolfram alpha, aby sprawdzić, jak zachowuje się ten kod.

Aktualizacja # 2: ja oczyścić kod bardziej i dodano funkcję sprawdzania poprawności, aby kod Gram Schmidt działa poprawnie, ale kod nie powiedzie się i wartość k przekracza liczbę wymiarów (lub liczbę wektorów), który robi To ma sens.

Answer 1

Opis algorytmu w Wikipedii wykorzystuje dość nieparzystą notację - wektory są ponumerowane 0..n (zamiast, powiedzmy 0..n-1 lub 1..n), więc całkowita liczba wektorów wynosi n +1.

Kod, który tutaj zamieściłeś, traktuje this.dimensions tak, jakby odpowiadał n w opisie Wikipedii. Jak dotąd nic złego się nie stało.

Jednak konstruktor w pełnym pliku źródłowym na GitHub ustawia this.dimensions = matrix[0].length. Dwie rzeczy o tym nie tak. Pierwszym z nich jest to, że z pewnością matrix[0].length jest bardziej podobny do m (rozmiar przestrzeni) niż n (liczba wektorów, minus 1 z niejasnych przyczyn). Po drugie, jeśli ma być n, to należy odjąć 1, ponieważ liczba wektorów wynosi n + 1, a nie n.

Więc jeśli chcesz użyć this.dimensions do oznaczenia n, myślę, że musisz go zainicjować jako matrix.length-1. Mając kwadratową matrycę w twoim teście testowym, użycie matrix[0].length-1 zadziała, ale myślę, że kod zostanie przerwany, kiedy wprowadzisz macierz inną niż kwadratowa. Nazwa dimensions jest również wprowadzająca w błąd; może tylko n pasuje do opisu Wikipedii?

Albo możesz to nazwać tak, jak nVectors, niech to będzie równe matrix.length, i odpowiednio zmień resztę kodu, co po prostu oznacza korektę warunków zakończenia dla głównej pętli.