c++ - 模数中的线性组合 C++

Question

我想计算矩阵的 LU 分解并从中提取线性组合。

我首先使用库 Armadillo 问了一个问题 here但正如一条评论所指出的， Armadillo 无法处理模数计算。

因此我开始从头开发一个使用质数模数的逻辑单元，这是我得到的，但仍然有一个我看不到的错误。

这是我目前拥有的代码。 (不要对 Matrix 类考虑太多，它只是目前封装 vector<vector<int>> 的一种方式。

Matrix* Matrix::triangulation(Matrix & ident)
{
    unsigned int n = getNbLines();
    unsigned int m = getNbColumns();

    vector<vector<int>> mat = getMat();

    vector<vector<int>> identity = ident.getMat();
    vector<vector<int>> lower;
    vector<vector<int>> upper;

    /* ------------------------------------------------------------ */  

    /**
     * @brief
     * This code initialize a 'lower' matrix of size 'n x n'.
     * The matrix is fill with only '0'.
     */
    for(unsigned int i = 0; i < n; i++) {   
        vector<int> v(m);
        lower.push_back(v);

        for(unsigned int j = 0; j < m; j++) lower[i][j] = 0;            
    }   

    /**
     * @brief
     * This code initialize an 'upper' matrix of size 'n x m'.
     * The matrix is fill with only '0'.
     */
    for(unsigned int i = 0; i < n; i++) {   
        vector<int> v(m);
        upper.push_back(v);
        for(unsigned int j = 0; j < m; j++) upper[i][j] = 0;
    }

    /**
     * @brief
     * This code initialize an 'identity' matrix of size 'm x m'.
     * The matrix is fill with only '0'.
     */
    for(unsigned int i = 0; i < m; i++) {
        vector<int> v2(m);
        identity.push_back(v2);
        for(unsigned int j = 0; j < m; j++) identity[i][j] = 0;

        identity[i][i] = 1;
    }

    /* ------------------------------------------------------------ */

    // Decomposing matrix into Upper and Lower triangular matrix 
    for (unsigned int i = 0; i < n; i++) { 

        // Upper Triangular 
        for (unsigned int k = 0; k < m; k++) { 

            // Summation of L(i, j) * U(j, k) 
            int sum = 0; 
            for (unsigned int j = 0; j < n; j++) 
                sum = sum + ((lower[i][j] * upper[j][k])); 

            // Evaluating U(i, k)
            upper[i][k]    = (mat[i][k] - sum) % prime;
            identity[i][k] = (mat[i][k] - sum) % prime;
        } 

        // Lower Triangular 
        for (unsigned int k = 0; k < n; k++) { 
            if (i == k) {

                lower[i][i] = 1; // Diagonal as 1 
            }
            else { 

                // Summation of L(k, j) * U(j, i) 
                int sum = 0; 
                for (unsigned int j = 0; j < n; j++) 
                    sum = sum + ((lower[k][j] * upper[j][i])); 

                // Evaluating L(k, i) 
                lower[k][i] =    (((mat[k][i] - sum)) / upper[i][i]) % prime; 
                identity[k][i] = (((mat[k][i] - sum)) / upper[i][i]) % prime;                   
            } 
        } 
    }  

    ident.setMat(identity);

    return new Matrix(lower,prime);
}

我用对象调用它:Matrix mat({ { 2, 1, 3, 2, 0}, { 4, 3, 0, 1, 1 }},5); 所以基本上，我想要 LU 分解(尤其是下三角矩阵)，所有计算都在模数 5 中完成。

它可以提取下矩阵，但是，线性组合(这只是对单位矩阵执行的所有操作)不正确。 这是我对我想要获得的东西的解释的痕迹:

c |-------------------------------------------------------------------------------------------------------|
c | Prime Number: 5

c |-------------------------------------------------------------------------------------------------------|
c | Input Matrix: 

2 1 3 2 0 
4 3 0 1 1 

c |-------------------------------------------------------------------------------------------------------|
c | Lower Matrix: 

1 0 0 0 0 
2 1 0 0 0 

c |-------------------------------------------------------------------------------------------------------|
c | Linear Combination Matrix:

2 0 3 2 0 
0 1 0 3 1 
0 0 1 0 0 
0 0 0 1 0 
0 0 0 0 1 

c |-------------------------------------------------------------------------------------------------------|
c | Expected Solution: 

3 2 3 0 3
0 1 1 3 4
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

c |-------------------------------------------------------------------------------------------------------|
c | Explanations: 

c | 3 * c1 + 0 * c2 + 0 * c3 + 0 * c4 + 0 * c5 = c1 of Lower-Matrix
c | 2 * c1 + 1 * c2 + 0 * c3 + 0 * c4 + 0 * c5 = c2 of Lower-Matrix
c | 3 * c1 + 1 * c2 + 1 * c3 + 0 * c4 + 0 * c5 = c3 of Lower-Matrix
c | 0 * c1 + 3 * c2 + 0 * c3 + 1 * c4 + 0 * c5 = c4 of Lower-Matrix
c | 3 * c1 + 4 * c2 + 0 * c3 + 0 * c4 + 1 * c5 = c5 of Lower-Matrix

c +=======================================================================================================+

所以作为一个小总结:

• 下矩阵OK，结果符合预期。
• 输出的线性组合不是预期的。
• 在最后一小节中给出了对预期结果的解释。

问题:我在单位矩阵上应用修改的方法中的错误在哪里，为什么我没有输出正确的线性组合？

编辑

清楚地了解正常情况下应该发生什么。但是我做的算法(LU 分解)并不完全是我手工做的，即使它应该导致相同的结果。这才是真正的麻烦...

Answer 1

让我们把我的评论放到一个实际的答案中:虽然加法和乘法模素数会做你期望的事情(注意下面)，但减法有一个陷阱，模数会为负输入返回负结果(例如 (-3)%5 = = -3) 而对于除法，您不能只使用整数除法，您必须实际实现乘法的逆运算(有关提示，请参阅 Demosthenes 在上一个链接问题中的回答)。

注意:除非你溢出，如果 prime*prime > INT_MAX ，你也有乘法的麻烦