使用自定义运算符进行高斯消除

Question

当运算符是自定义运算符而不是标准算术运算符时,实现高斯消元法的好方法是什么？

以下是运营商:

加成:

0 + 0 = 0
0 + 1 = 1
1 + 1 = 0

减法:

0 - 0 = 0
0 - 1 = 1
1 - 1 = 0

乘法:

0 * 0 = 0
0 * 1 = 0
1 * 1 = 1

师:

0 / 0 = illegal
0 / 1 = 0
1 / 1 = 1

以下是作为增广矩阵的一组示例方程,其中RHS位于最右侧列:

1, 1, 0, 1, 0, 0, 0, 0, 0, 1
0, 1, 0, 1, 1, 0, 0, 0, 0, 1
0, 1, 1, 0, 0, 1, 0, 0, 0, 1
1, 0, 0, 1, 0, 0, 0, 0, 0, 1
0, 1, 0, 1, 1, 0, 0, 0, 0, 1
0, 0, 0, 0, 0, 1, 0, 0, 0, 1
0, 0, 0, 1, 0, 0, 1, 0, 0, 1
0, 0, 0, 1, 1, 0, 1, 1, 0, 1
0, 0, 0, 0, 0, 1, 0, 0, 1, 1

该套装的解决方案是:

x1 = 1
x2 = 0
x3 = 0
x4 = 0
x5 = 1
x6 = 1
x7 = 1
x8 = 1
x9 = 0

当我在这套装置上尝试时,高斯消除失败了.

方程将有9,16,25或36项.如果算法可以很容易地扩展到更大的方块,那将是很好的.我正在寻找一种算法,最好是伪代码或JavaScript.

Answer 1

伪码中的高斯消元算法可以在这里找到.

如果您使用"普通"数字或者如果您使用Z ₂环,则无关紧要,算法保持不变.

您可以做的是实现一个结构来保存您正在操作的值并使所有必需的运算符超载.然后,您需要做的就是将伪代码重写为您要使用的语言.

不幸的是,因为你提到了JavaScript,你不能用这种语言覆盖运算符,所以这会变得有点复杂.我想你可以定义将执行操作员作业的函数,并使用它们而不是标准运算符.

function add(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    }

    return (v1 + v2) % 2;
}

function subtract(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    }

    return Math.abs((v1 - v2) % 2);
}

function multiply(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    }

    return v1 * v2;
}

function divide(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    } else if (v2 == 0) {
        alert('Divider cannot be zero');
        return;
    }

    return v1 / v2;
}