javascript - 按照维基百科上的说法实现 LLL 算法，但遇到了严重的问题

Question

我不确定我的问题是否与编程有关或与 LLL 算法的概念以及维基百科上提到的内容有关。

我决定实现 LLL 算法，因为它已写在 Wikipedia (step-by-step / line-by-line) 上实际学习算法并确保它真正有效，但我得到了意外或无效的结果。

因此，我使用了 JavaScript(编程语言)和 node.js(JavaScript 引擎)来实现它并且 this is the git repository获取完整代码。

长话短说，K 的值超出范围，例如当我们只有 3 个向量时(数组大小为 3，因此索引的最大值为 2)，但 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;
}

这是维基百科上的算法截图:

---

更新 #1:我在代码中添加了更多注释以澄清问题，希望有人能提供帮助。

以防万一你想知道代码的已经可用的实现，你可以输入:LatticeReduce[{{0,1},{2,0}}] wolfram alpha查看此代码的行为方式。

更新 #2:我进一步清理了代码并添加了一个验证函数以使 Gram Schmidt 代码正常工作，但代码仍然失败并且 k 的值超过维数(或维数向量)这没有意义。

Answer 1

维基百科中的算法描述使用了相当奇怪的符号——向量编号为 0..n(而不是 0..n-1 或 1..n)，因此向量总数为 n+ 1.

您在此处发布的代码将 this.dimensions 视为对应于维基百科描述中的 n。到目前为止没有任何问题。

但是，GitHub 上完整源文件中的构造函数设置了 this.dimensions = matrix[0].length。有两点看起来不对劲。首先是 matrix[0].length 肯定更像 m(空间的维数)而不是 n(向量的数量, 负 1，原因不明)。第二个是，如果它是 n，那么您需要减去 1，因为向量的数量是 n+1，而不是 n。

所以如果你想用this.dimensions来表示n，我认为你需要将它初始化为matrix.length-1。对于测试用例中的方阵，使用 matrix[0].length-1 会起作用，但我认为当您输入非方阵时代码会中断。 dimensions 这个名字也有点误导；也许只是 n 来匹配维基百科的描述？

或者您可以将其命名为nVectors，让它等于matrix.length，并适当更改其余代码，这仅意味着对终止进行调整主循环的条件。