matlab稀疏矩阵三元法,数据结构——稀疏矩阵三元组表示法+算法详解

稀疏矩阵是指其中大部分元素为零的矩阵。由于大多数矩阵都是稠密的，即大多数元素都不为零，因此通常情况下，我们使用一个二维数组来表示一个矩阵。但是，对于稀疏矩阵来说，这种方法会造成很大的浪费，因为大量的空间被用来存储零元素。为了解决这个问题，我们可以使用稀疏矩阵三元组表示法。

稀疏矩阵三元组表示法是将稀疏矩阵中每个非零元素的行、列和值存储在一个三元组中。其数据结构如下所示：

struct Triple{
    int row, col;
    double value;
};

其中，row表示非零元素所在的行，col表示非零元素所在的列，value表示非零元素的值。我们可以使用一个数组来存储所有的非零元素，这个数组就是稀疏矩阵的三元组。

稀疏矩阵三元组表示法的优点是它可以节省存储空间，缺点是它不方便进行矩阵运算。因此，在进行矩阵运算时，我们需要将稀疏矩阵转换成其他更方便进行矩阵运算的表示方法，如压缩矩阵和坐标矩阵等。

对于稀疏矩阵的求解，可以使用稀疏矩阵三元组表示法结合三元组高斯消元算法来进行求解。三元组高斯消元算法是一种针对稀疏矩阵的高斯消元算法，其基本思想是将矩阵化为上三角矩阵或下三角矩阵，然后通过回代或者前代求解方程。由于矩阵中大部分元素为零，因此在进行高斯消元时，我们只需要考虑非零元素，这样可以大大提高计算效率。

三元组高斯消元算法的基本步骤如下：

1. 将稀疏矩阵转换成三元组表示法；
2. 对三元组按照行和列的顺序进行排序；
3. 从第一个非零元素开始，进行高斯消元，将矩阵化为上三角矩阵或下三角矩阵；
4. 通过回代或者前代求解方程。

具体实现可以参考以下代码：

void SparseTripletGaussElimination(SparseTriplet& triplet, vector<double>& b)
{
    int n = triplet.rows;
    vector<Triple> A(triplet.data, triplet.data + triplet.num);
    sort(A.begin(), A.end(), [](const Triple& a, const Triple& b){
        return a.row < b.row || (a.row == b.row && a.col < b.col);
    });
    vector<int> row(n+1), col(triplet.num), diag(n);
    vector<double> val(triplet.num);
    for (int i = 0; i < triplet.num; i++) {
        row[A[i].row]++;
    }
    for (int i = 1; i <= n; i++) {
        row[i] += row[i-1];
    }
    for (int i = 0; i < triplet.num; i++) {
        int r = A[i].row, c = A[i].col;
        double v = A[i].value;
        int k = row[r]++; // 获取 r 行中下一个非零元素的位置
        col[k] = c;
        val[k] = v;
        if (r == c) {
            diag[r] = k; // 记录对角线元素的位置
        }
    }
    for (int k = 0; k < n-1; k++) {
        if (val[diag[k]] == 0) {
            // 对角线元素为零，无法消元
            throw runtime_error("zero pivot encountered");
        }
        for (int i = diag[k]+1; i < row[k+1]; i++) {
            int r = col[i];
            double factor = val[i] / val[diag[k]];
            for (int j = diag[k]+1; j < row[k+1]; j++) {
                if (col[j] == r) {
                    val[j] -= factor * val[diag[k]];
                }
            }
            b[r] -= factor * b[k];
        }
    }
    if (val[diag[n-1]] == 0) {
        // 对角线元素为零，无法消元
        throw runtime_error("zero pivot encountered");
    }
    for (int k = n-1; k >= 0; k--) {
        double sum = 0;
        for (int i = diag[k]+1; i < row[k+1]; i++) {
            sum += val[i] * b[col[i]];
        }
        b[k] = (b[k] - sum) / val[diag[k]];
    }
}

其中，SparseTriplet是稀疏矩阵三元组表示法的数据结构，b是待求解的方程的右侧向量。在实现中，我们首先将三元组按照行和列的顺序进行排序，然后将其转换成压缩矩阵的形式，接着进行高斯消元，并通过回代或者前代求解方程。