正如在维基百科上所说的那样实现LLL算法,但是遇到了严重的问题

Question

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

我决定实施LLL算法,因为它已经在维基百科上编写(逐步/逐行),以实际学习算法并确保它真正有效,但我得到意外或无效的结果.

所以,我使用JavaScript(编程语言)和node.js(JavaScript引擎)来实现它,这是获取完整代码的git存储库.

长话短说,K的值超出范围,例如当我们只有3个向量(数组大小为3,因此索引的最大值为2)时,k变为3并且它是无意义的.

我的代码是维基百科上提到的算法的逐步(逐行)实现,我所做的只是实现它.所以我不是什么问题.

// ** 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.dimensionsn 表示，我认为您需要将其初始化为matrix.length-1。对于测试用例中的方阵，使用matrix[0].length-1可以工作，但我认为当您输入非方阵时代码将会中断。这个名字dimensions也有点误导；也许只是n为了符合维基百科的描述？

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