Lab 3 - 实现稀疏矩阵以及 Gauss-Seidel 迭代法

实验课上所使用的课件同步在学在浙大发布。

本次实验内容为课程作业,计算成绩。你需要将C++ 源代码和实验文档打包并上传至学在浙大,压缩包名称为Lab3-学号-姓名.zip/7z。请在 README 中注明代码编译方法。

本次作业提交截止时间:2025年3月18日 23:59:59,逾期将要扣分。

编程语言

请使用 C++ 语言作为编程语言。

稀疏矩阵

对于一个 (m, n) 的矩阵,若矩阵中的零元素的数目远多于非零元素的数目,则称该矩阵为稀疏矩阵。本实验要求自行实现一种稀疏矩阵。推荐的稀疏矩阵存储方式包括:

  1. Compressed Row Storage (CRS)
  2. Compressed Sparse Column (CSC)
  3. 其他形式的稀疏矩阵存储方式

这里简单介绍一下压缩行存储 (CRS) 的朴素实现。CRS 维护三个数组,分别是:

  1. val:按行优先顺序存储所有非零元素的值。
  2. col_ind:存储每个非零元素对应的列索引。
  3. row_ptr:长度为 m+1 的数组,其中索引为 i (i < m)的元素存储第 i 行第一个非零元素在 val 数组中的索引;索引为 m 元素存储矩阵中非零元素的总数。

对于简单的矩阵 A:

A=(1012011113211010318) A=\begin{pmatrix} 5 & 1 & 0 & 0 \\ 0 & 8 & 0 & 0 \\ 0 & 0 & 0 & 2\\ 0 & 0 & 3 & 0 \end{pmatrix}

其 CRS 表示为:

val = {5,1,8,2,3}
col_ind = {0,1,1,3,2}
row_ptr = {0,2,3,4,5}

请同学们基于 sparse.h 实现 Sparse 类,并在实验报告中明确指出自己实现的稀疏矩阵方式。要求保证实现的 Sparse 类至少具备以下的几种最基本的 public 成员函数:

  1. at(row, col): 根据rowcolumn的系数来查询矩阵里面的元素的数值,即查询矩阵 A 的元素 A[row][col]
  2. insert(val, row, col): 将 val 替换/插入到 (row, col) 这个位置去
  3. initializeFromVector(rows, cols, vals): 根据向量来初始化一个稀疏矩阵。其中 rows, cols, vals 皆为等长度的向量。rows 里面存的是行系数,cols 里面存的是列系数,vals 里面存的是数值。例如,vals[i] 对应的就是 A[rows[i]][cols[i]] 的值
  4. 其余的基本功能可以参考Matlab里面的 sparse 函数,或者 Eigen Library 里面的 Sparse Matrix 的介绍。

为了便于同学们的实现,对矩阵做出以下约定:

备注:关于 CRS 与 CSC 的实现实现方式可以参考下面的网站:

此外,有兴趣的同学也可以尝试将自己的实现与 Eigen LibrarySparse Matrix 进行比较,看是自己的实现比较高效还是 Eigen Library 的实现比较高效。

稀疏矩阵的 Gauss-Seidel 迭代法

本实验要求在自己实现的稀疏矩阵的表达的基础上,实现 Gauss-Seidel 方法,以求解大规模的稀疏线性方程组。

关于 Gauss-Seidel 方法的介绍已经在 课件中进行了详细的介绍。这里帮大家贴上算法的伪代码:

Gauss-Seidel Algorithm

请同学们参照课件,基于 hw3_solve.h 所定义的接口 Gauss_Seidel(A, b, error) 进行代码的编写,其中参数

x k + 1 x k error

此外还有一些额外的辅助资料提供参考:

为了方便同学们验证实现的正确性,这里给出一个小的Test Case:
A=(1012011113211010318) A=\begin{pmatrix} 10 & -1 & 2 & 0 \\ -1 & 11 & -1 & 3 \\ 2 & -1 & 10 & -1\\ 0 & 3 & -1 & 8 \end{pmatrix}
b=(6,25,11,15)T b=(6,25,-11,15)^T
求解得到的结果应该为:

x = [1, 2, -1, 1];

Bonus: 实现共轭梯度法

有余力的同学可以参考相关资料实现共轭梯度法求解线性方程组。

维基百科上有比较详细的共轭梯度法的介绍:Conjugate gradient method

希望完成该 bonus 的同学请基于 hw3_solve.h 所定义的接口 Conjugate_Gradient(A, b, error, kmax) 进行代码的编写,其中有

r 2 2 = b A x 2 2 error

自主测试

实验提供 main.cpp 对稀疏矩阵的实现、G-S 迭代(和共轭梯度法,可选)求解进行基础的正确性验证。 同时,我们也提供了一个参考的 makefile 文件,方便同学们编译测试。

你需要完善自己的测试样例,并在实验报告中说明。在作业批改时,将会对你的实现进行更复杂的测试,包括最高 30000 × 30000 的随机矩阵求解。 当然,非常也欢迎大家提交自己补充的测试代码。

在这里重新列出所有提供的模板代码:

这些代码被打包在 code.zip 中。此外,这里有一些问题,帮助同学们更好地理解和完成实验:

  • CRS 和 CCS 分别擅长处理什么任务?对于本实验的方程组求解,更适合使用哪种实现方式?
  • 初始化的 cols 和 rows 不一定是递增给出的,应该如何处理?
  • Gauss-Seidel迭代和共轭迭代的收敛条件有什么区别?观察你的实验结果,尝试解释两种方法迭代步数差别存在的原因。