Implementare l'algoritmo LLL come detto su Wikipedia, ma entrare in gravi problemi

Question

Non sono sicuro che il mio problema sia legato alla programmazione o al concetto di algoritmo LLL e che cosa è stato menzionato su Wikipedia.

Ho deciso di implementare l'algoritmo LLL in quanto è stato scritto su Wikipedia (step-by-step/line-by-line) per imparare effettivamente l'algoritmo e verificare che funzioni veramente, ma ottengo risultati inattesi o non validi.

Quindi, ho utilizzato JavaScript (linguaggio di programmazione) e node.js (motore JavaScript) per implementarlo e this is the git repository per ottenere il codice completo.

Per farla breve, il valore di K diventa fuori intervallo, ad esempio quando abbiamo solo 3 vettori (la dimensione dell'array è 3, quindi il valore massimo dell'indice sarebbe 2), ma k diventa 3 e non ha senso.

Il mio codice è un'implementazione passo passo (riga per riga) dell'algoritmo menzionato su Wikipedia e quello che ho fatto è stato solo implementandolo. Quindi non so qual è il problema.

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

Ecco lo screenshot dell'algoritmo che si trova su Wikipedia:

---

Update # 1: ho aggiunto altri commenti al codice di chiarire la questione nella speranza che qualcuno potrebbe aiutare.

Nel caso in cui vi stiate chiedendo dell'implementazione già disponibile del codice, è possibile digitare: LatticeReduce[{{0,1},{2,0}}] wolfram alpha per vedere come si comporta questo codice.

Update # 2: Ho pulito il codice sempre aggiunto una funzione di convalida per rendere il codice Gram Schmidt funziona correttamente, ma ancora codice non riesce e il valore di k supera il numero di dimensioni (o numero di vettori) che doesn ha senso

Answer 1

La descrizione dell'algoritmo in Wikipedia utilizza una notazione piuttosto strana - i vettori sono numerati 0..n (piuttosto che, 0..n-1 o 1..n), quindi il numero totale di vettori è n +1.

Il codice che hai postato qui considera this.dimensions come se corrispondesse a n nella descrizione di Wikipedia. Niente di male in questo fino ad ora.

Tuttavia, il costruttore nel file sorgente completo su GitHub imposta this.dimensions = matrix[0].length. Due cose su questo aspetto sbagliato. Il primo è che sicuramente matrix[0].length è più simile a m (la dimensione dello spazio) rispetto a n (il numero di vettori, meno 1 per motivi non chiari). Il secondo è che se è pensato per essere n allora devi sottrarre 1 perché il numero di vettori è n + 1, non n.

Quindi, se si desidera utilizzare this.dimensions per significare n, penso che sia necessario inizializzarlo come matrix.length-1. Con la matrice quadrata nel tuo caso di test, l'utilizzo di matrix[0].length-1 funzionerebbe, ma penso che il codice verrà interrotto quando si alimenta una matrice non quadrata. Anche il nome dimensions è fuorviante; forse solo n per abbinare la descrizione di Wikipedia?

Oppure si può chiamare qualcosa come nVectors, lasciarlo uguale a matrix.length e modificare il resto del codice in modo appropriato, il che significa semplicemente una regolazione nella condizione di terminazione per il ciclo principale.