模数线性组合C ++ [英] Linear Combination C++ in modulus
问题描述
我想计算矩阵的LU分解并从中提取线性组合.
I want to compute an LU decomposition of a matrix and extract the linear combinations out of it.
我首先使用Armadillo库问了一个问题，此处，但是正如一条评论指出的那样，犰狳无法处理模数计算.
I first asked a question using the library Armadillo here but as pointed out by one comment, Armadillo is not able to deal with modulus computation.
因此，我开始使用从头开始的质数模量来开发LU，这是我所获得的，但是仍然有一个我看不到的错误.
Thus I started to develop an LU using prime modulus from scratch, here is what I obtain but there is still a bug that I am not able to see.
这是我现在拥有的代码. (不要对Matrix类考虑太多，它只是暂时封装vector<vector<int>>的一种方法.
Here is the code that I have for now. (Do not think too much about the class Matrix, it is just a way to encapsulate for now a 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);称呼它
因此，基本上，我希望所有分解都在模数5中进行LU分解(尤其是下三角矩阵).
I call it with the object : Matrix mat({ { 2, 1, 3, 2, 0}, { 4, 3, 0, 1, 1 }},5);
So basically, I want the LU decomposition (especially the lower-triangle matrix) with all my computation done in modulus 5.
它可以提取下矩阵，但是线性组合(仅对单位矩阵执行的所有操作)是不正确的. 这是我要获得的解释的踪迹:
It works to extract the lower-matrix, however, the linear combinations (which are just all the operations done on an identity matrix) are not correct. Here is the trace that I have with an explanation of what I want to obtain:
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 +=======================================================================================================+
作为一个小总结:
- 下面的矩阵可以，结果是预期的结果.
- 输出的线性组合不是预期的.
- 在最后一个小节中给出了关于期望的解释.
问题:将修改应用于单位矩阵的方式中的错误是什么?为什么我的输出中没有正确的线性组合?
编辑
清晰了解正常情况.但是我所做的算法(LU分解)与我手工执行的算法不完全相同，即使它会导致相同的结果.这是真正的麻烦...
Clear view of what should happened normally. But the algorithm I did (the LU decomposition) is not exactly the one I do by hand, even though it should lead to the same results. That is the real trouble here...
推荐答案
让我将评论提交到实际答案中:加法和乘法模质数将达到您的期望(请注意)，而减法则是模数返回的陷阱负输入的负结果(例如(-3)％5 == -3)，对于除法，您不能仅使用整数除法，您实际上必须实现乘法的逆运算(有关提示，请参见前面链接中Demosthenes的答案)问题).
Let's put my comments into an actual answer: while addition and multiplication modulo prime will do what you expect (note below), subtraction has the pitfall where modulo will return negative results for negative input (e.g. (-3)%5 == -3) and for division you cannot just use integer division, you have to actually implement the inverse of multiplication (for hints, see the answer by Demosthenes in the linked previous question).
注意:除非您溢出，否则如果prime * prime> INT_MAX，您也有乘法的麻烦
Note: unless you overflow, if prime*prime > INT_MAX , you are in trouble for multiplication as well
这篇关于模数线性组合C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
