融入几何元素的并行计算课程教学实践——以卡茨马兹型算法为例

Teaching Practice of Parallel Computing Course with Incorporated Geometric Elements—A Case Study of the Kaczmarz Algorithms

摘要: 并行计算作为数据科学与大数据技术专业的一门重要课程，以介绍各种数值并行算法原理为主要内容。本文以卡茨马兹型算法为例，采用案例教学法，将几何元素融入到并行计算课程教学实践中，旨在帮助学生能够更直观地理解卡茨马兹算法及其变种之间的联系，建立更牢固的知识结构。

Abstract: Parallel computing, as an important course of data science and big data technology, mainly introduces the principles of various numerical parallel algorithms. Taking Kaczmarz algorithm as an example, this paper uses case teaching method incorporated geometric elements into the teaching practice of parallel computing course, aiming to help students understand the relationship between Kaczmarz algorithm and its variants intuitively, and build a more solid knowledge structure.

1. 引言

数值并行计算为解决实际问题提供了有效方案，可进一步促进科学技术的发展和社会经济的进步[1]。随着计算机硬件技术的发展，单个处理器的性能已经达到了瓶颈，而并行计算技术能够充分利用多个处理器或计算节点的并行计算能力，提高计算效率。同时，数值并行计算也是计算科学和工程领域的重要分支之一，对推动学科发展具有重要意义。此外，数值并行计算还可以促进不同学科之间的交叉融合，推动学科的跨界发展[2]-[5]。

线性方程组$Ax=b$ ($A\in R^{m\times n}$ ，$x\in R^n$ ，$b\in R^m$ )的求解是并行计算课程的一个重要部分(见教材[6]第五章)。当m和n很大时，卡茨马兹算法(Kaczmarz Algorithm)因其迭代格式简单、几何意义明显、理论分析简洁，常被用来求解此类问题[7]。若用$a_i^{\text{T}}$ 表示系数矩阵A的第i行，$b_i$ 表示右端项b的第i个分量，其迭代格式在1个处理器上的代数表达式为

$x^{\left(k\right)}=x^{\left(k-1\right)}+\frac{b_{i_k}-a_{i_k}^{\text{T}}{x}^{\left(k-1\right)}}{{\Vert a_{i_k}\Vert }^2}{a}_{i_k}$ ， (1)

其中迭代步数$k=1,2,\cdots$ ，行指标$i_k=1,2,\cdots ,m$ 。

考虑一般的形式，选取$m\left(m\ge 2\right)$ 个处理器，可得多投影迭代格式

$x^{\left(k\right)}=\frac{1}{m}{\displaystyle \sum _{i=1}^m\left(x^{\left(k-1\right)}+\frac{b_i-a_i^{\text{T}}{x}^{\left(k-1\right)}}{{\Vert a_i\Vert }^2}{a}_i\right)}$ 。

经过简单计算可知，

$x^{\left(k\right)}=x^{\left(k-1\right)}+\frac{1}{m}{\displaystyle \sum _{i=1}^m\left(\frac{b_i-a_i^{\text{T}}{x}^{\left(k-1\right)}}{{\Vert a_i\Vert }^2}{a}_i\right)}=x^{\left(k-1\right)}+\frac{1}{m}{A}^{\text{T}}M\left(b-A{x}^{\left(k-1\right)}\right)$ ，

其中对角矩阵$M=diag\left(1/{\Vert a_i\Vert }^2\right)$ ，此方法称为奇米诺算法(Cimmino Algorithm)。因而，奇米诺算法是卡茨马兹算法的一种并行形式。

几何解释。若按照顺序$1,2,\cdots ,m,1,2,\cdots ,m,\cdots$ 依次选取行指标，则迭代向量$x^{\left(k\right)}$ 是$x^{\left(k-1\right)}$ 到超平面$H_{i_k}$ 上的正交投影。迭代过程如图1所示(以$m=6$ )，其中实心圆表示迭代向量，超平面$H_i=\left\{x|a_i^{\text{T}}x=b_i\right\}$ ，$i=1,2,\cdots ,6$ ，超平面的交点表示方程组的解。

几何解释能够与实际情境相联，学生通过视觉感知理解概念，这种直观性可以帮助学生对图形化的抽象概念有更好的理解[8]。

2. 卡茨马兹算法及案例分析

卡茨马兹算法及其变种具有明显的几何意义，本节将结合具体案例，将此类算法蕴含的几何元素融入到教学实践中。

Figure 1. Demonstration of the iterative process for the Kaczmarz algorithm

图1. 卡茨马兹算法的迭代过程演示

2.1. 教学案例

考虑用卡茨马兹算法求解下列线性方程组

$\left[\begin{array}{cc}1& 2\\ 1& 3\\ 2& 3\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}3\\ 4\\ 5\end{array}\right]\iff Ax=b$ 。

每个方程看作是一个约束条件，而求解线性方程组就是要找到一个满足所有约束条件的点$x^{\ast }={\left[\begin{array}{cc}1& 1\end{array}\right]}^{\text{T}}$ 。

2.2. 案例分析

第一步：当$k=1$ 时，取行指标$i=1$ ，根据迭代公式(1)计算

$x^{\left(1\right)}=x^{\left(0\right)}+\frac{b_1-a_1^{\text{T}}{x}^{\left(0\right)}}{{\Vert a_1\Vert }_2^2}{a}_1={\left[\begin{array}{cc}\frac{7}{5}& \frac{4}{5}\end{array}\right]}^{\text{T}}$ ，

其中初值向量$x^{\left(0\right)}={\left[\begin{array}{cc}2& 2\end{array}\right]}^{\text{T}}$ 。记$X_0\left(2,2\right)$ 和$X_1\left(\frac{7}{5},\frac{4}{5}\right)$ ，易验证$x_1^{\left(1\right)}+2x_2^{\left(1\right)}=3$ ，说明X₁在第一个超平面H₁上；同时，$\overrightarrow{X_0{X}_1}$ 与第一个方程的法向量a₁共线，因而X₁是X₀在H₁上的投影。此时误差为${\Vert x^{\left(1\right)}-x^{\ast }\Vert }_2\approx 0.447<{\Vert x^{\left(0\right)}-x^{\ast }\Vert }_2\approx 1.414$ 。

第二步：当$k=2$ 时，取行指标$i=2$ ，根据迭代公式(1)计算

$x^{\left(2\right)}=x^{\left(1\right)}+\frac{b_2-a_2^{\text{T}}{x}^{\left(1\right)}}{{\Vert a_2\Vert }_2^2}{a}_2={\left[\frac{71}{50}\frac{43}{50}\right]}^{\text{T}}$ 。

记$X_2\left(\frac{71}{50},\frac{43}{50}\right)$ ，易验证$x_1^{\left(2\right)}+3x_2^{\left(2\right)}=4$ ，说明X₂在第二个超平面H₂上；同时，$\overrightarrow{X_1{X}_2}$ 与第二个方程的法向量a₂共线，因而X₂是X₁在H₂上的投影。此时误差为${\Vert x^{\left(2\right)}-x^{\ast }\Vert }_2\approx 0.443<0.447$ 。

第三步：当$k=3$ 时，取行指标$i=3$ ，根据迭代公式(1)计算

$x^{\left(3\right)}=x^{\left(2\right)}+\frac{b_3-a_3^{\text{T}}{x}^{\left(2\right)}}{{\Vert a_3\Vert }_2^2}{a}_3={\left[\frac{881}{650}\frac{496}{650}\right]}^{\text{T}}$ 。

记$X_3\left(\frac{881}{650},\frac{496}{650}\right)$ ，易验证$2x_1^{\left(3\right)}+3x_2^{\left(3\right)}=5$ ，说明X₃在第三个超平面H₃上；同时，$\overrightarrow{X_2{X}_3}$ 与第三个方程的法向量a₃共线，因而X₃是X₂在H₃上的投影。此时误差为${\Vert x^{\left(3\right)}-x^{\ast }\Vert }_2\approx \text{0}\text{.427}<0.443$ 。

引导学生发现规律：当k增大时，$x^{\left(k\right)}$ 将不断趋近$x^{\ast }$ 。上述计算利用具体的几何形状或者图形来演示抽象的理论和概念，不仅将卡茨马兹算法的迭代过程可视化，也说明了卡茨马兹算法的收敛性。

案例教学是一种实践性很强的教学方法，在向量序列$x^{\left(k\right)}$ 的计算中，学生掌握了卡茨马兹算法的基本过程，提升了学生实际应用能力，也有助于学生将理论知识转化为实际操作的能力。教学过程中使用的案例要求具有情节性或故事性，如卡茨马兹算法具有几何背景，在案例讲述中，学生更容易投入到学习中，积极参与讨论和思考。在线性方程组的求解中，若按照不同方式选取行指标，要求学生对卡茨马兹算法的收敛性进行评估，这种过程培养了学生的批判性思维，提升了学生的分析能力。本文采用的案例涉及到了代数和几何等多个学科领域的知识，通过对交叉学科的学习和思考，有助于学生理解各学科知识的联系。在共同分析案例、讨论解决方案、协调分工等教学实践中，学生的团队合作和沟通能力也得到了培养。

2.3. 案例延申

案例延申是对问题的深入探索，通过教师与学生的讨论，学生可以从不同的角度思考和理解新概念，有助于培养学生创新思维和创新能力。按照“选择适当的案例”–“确定延申的方向”–“引导学生分析和讨论”–“探索相关知识”–“总结和反思”等基本步骤进行案例延申，得到如下所述的松弛卡茨马兹算法。

若在卡茨马兹迭代格式中引入松弛参数，即

$x^{\left(k\right)}=x^{\left(k-1\right)}+\boxed{\lambda }\frac{b_i-a_i^{\text{T}}{x}^{\left(k-1\right)}}{{\Vert a_i\Vert }^2}{a}_i$ 。 (2)

当$\lambda =1$ 时，即为卡茨马兹迭算法，计算过程为正交投影；当$\lambda =2$ 时，计算过程变为反射运算，如图2所示(以$m=2$ 为例)，超平面的交点表示方程组的解。

Figure 2. Demonstration of the iterative process for the reflection algorithm

图2. 反射运算的迭代过程演示

考虑第2.1节中的教学案例，当$k=1$ 时，取初值$x^{\left(0\right)}={\left[\begin{array}{cc}2& 2\end{array}\right]}^{\text{T}}$ ，以及行指标$i=1$ ，计算

$x^{\left(1\right)}=x^{\left(0\right)}+2\frac{b_1-a_1^{\text{T}}{x}^{\left(0\right)}}{{\Vert a_1\Vert }_2^2}{a}_1={\left[\frac{4}{5}-\frac{2}{5}\right]}^{\text{T}}$ ，

由此可知，$\frac{1}{2}\left(x^{\left(0\right)}+x^{\left(1\right)}\right)={\left[\begin{array}{cc}\frac{7}{5}& \frac{4}{5}\end{array}\right]}^{\text{T}}$ 。易验证$\frac{7}{5}+\frac{4}{5}\times 2=3$ ，说明$X_0\left(2,2\right)$ 和$X_1\left(\frac{4}{5},-\frac{2}{5}\right)$ 的中点在第一个方程上，又因为$\overrightarrow{X_0{X}_1}$ 与第一个方程的法向量a₁共线，因而$x^{\left(1\right)}$ 是$x^{\left(0\right)}$ 关于H₁的对称点，即说明上述过程是一个反射运算。

以上步骤可以根据具体教学目标和案例特点进行灵活调整和组合，以实现最佳的教学效果。

3. 基于卡茨马兹算法的延拓式教学

延拓式教学旨在学生在已有知识基础上的延伸和拓展，促进学生对新知识的深入理解和应用，本节将继续引导学生对卡茨马兹算法做进一步的学习。

1) 知识评估。通过课堂或小组讨论、问答等方式评估学生对卡茨马兹算法的理解程度。

2) 情境引入。引导学生思考如何对卡茨马兹算法并行化，这有助于激发学生的学习兴趣和提高学生的学习动机。

3) 总结规律。通过解释、示范、演示等方式对卡茨马兹算法进行总结，帮助学生理解和应用新知识。

几何解释。首先将$x^{\left(k-1\right)}$ 依次投影到第$i_1,\cdots ,i_p$ 个超平面$H_{i_1},\cdots ,H_{i_p}$ ，分别得到$x^{\left(k-1,1\right)},\cdots ,x^{\left(k-1,p\right)}$ ；然后取其平均值，得到下一个迭代向量$x^{\left(k\right)}$ 。迭代过程如图3所示(以$m=2,t=2$ 为例)，超平面的交点表示方程组的解。

Figure 3. Demonstration of the iterative process for the Average Block Kaczmarz Algorithm

图3. 平均块卡茨马兹算法的迭代过程演示

4) 循序善诱。通过理论分析与实践等方式，鼓励学生积极参与到学习中，探索和发现新知识，培养学生的自主学习能力。

若处理器个数为p，选取系数矩阵A的第$i_1,i_2,\cdots ,i_p$ 行，可得迭代格式

$x^{\left(k\right)}=\frac{1}{p}{\displaystyle \sum _{t=1}^p\left(x^{\left(k-1\right)}+\frac{b_{i_t}-a_{i_t}^{\text{T}}{x}^{\left(k-1\right)}}{{\Vert a_{i_t}\Vert }^2}{a}_{i_t}\right)}$ ， (3)

或等价地表示为$x^{\left(k\right)}=\left(x^{\left(k-1,1\right)}+x^{\left(k-1,2\right)}+\cdots +x^{\left(k-1,p\right)}\right)/p$ ，其中

$x^{\left(k-1,t\right)}=x^{\left(k-1\right)}+\frac{b_{i_t}-a_{i_t}^{\text{T}}{x}^{\left(k-1\right)}}{{\Vert a_{i_t}\Vert }^2}{a}_{i_t}$ ，$t=1,2,\cdots ,p$ 。

此方法称为平均块卡茨马兹算法(Average Block Kaczmarz Algorithm) [9]。

5) 组织讨论。以小组活动或实践任务的形式组织学生参与讨论，帮助学生共同探讨和应用延拓内容，以第2.1节中的教学案例为例。

第一步(1)：当$k=1$ 时，取行指标$i_1=1$ ，$i_2=2$ ，根据迭代公式(3)计算

$x^{\left(0,1\right)}=x^{\left(0\right)}+\frac{b_1-a_1^{\text{T}}{x}^{\left(0\right)}}{{\Vert a_1\Vert }_2^2}{a}_1={\left[\begin{array}{cc}\frac{7}{5}& \frac{4}{5}\end{array}\right]}^{\text{T}}$ 和$x^{\left(0,2\right)}=x^{\left(0\right)}+\frac{b_2-a_2^{\text{T}}{x}^{\left(0\right)}}{{\Vert a_2\Vert }_2^2}{a}_2={\left[\begin{array}{cc}\frac{8}{5}& \frac{4}{5}\end{array}\right]}^{\text{T}}$ ，

其中初值向量$x^{\left(0\right)}={\left[\begin{array}{cc}2& 2\end{array}\right]}^{\text{T}}$ 。

第一步(2)：计算

$x^{\left(1\right)}=\frac{1}{2}\left(x^{\left(0,1\right)}+x^{\left(0,2\right)}\right)={\left[\begin{array}{cc}\frac{15}{10}& \frac{8}{10}\end{array}\right]}^{\text{T}}$ ，

以及误差${\Vert x^{\left(1\right)}-x^{\ast }\Vert }_2\approx \text{0}\text{.539<}{\Vert x^{\left(0\right)}-x^{\ast }\Vert }_2\approx 1.414$ 。

第二步(1)：当$k=2$ 时，取行指标$i_1=3$ ，$i_2=1$ ，根据迭代公式(3)计算

$x^{\left(1,1\right)}=x^{\left(1\right)}+\frac{b_3-a_3^{\text{T}}{x}^{\left(1\right)}}{{\Vert a_3\Vert }_2^2}{a}_3={\left[\begin{array}{cc}\frac{187}{130}& \frac{92}{130}\end{array}\right]}^{\text{T}}$ 和$x^{\left(1,2\right)}=x^{\left(1\right)}+\frac{b_1-a_1^{\text{T}}{x}^{\left(1\right)}}{{\Vert a_1\Vert }_2^2}{a}_1={\left[\begin{array}{cc}\frac{37}{25}& \frac{19}{25}\end{array}\right]}^{\text{T}}$ 。

第二步(2)：计算

$x^{\left(2\right)}=\frac{1}{2}\left(x^{\left(1,1\right)}+x^{\left(1,2\right)}\right)={\left[\begin{array}{cc}\frac{1897}{1300}& \frac{954}{1300}\end{array}\right]}^{\text{T}}$ ，

以及误差${\Vert x^{\left(2\right)}-x^{\ast }\Vert }_2\approx 0.531<0.539$ 。

第三步：当$k=3$ 时，取行指标$i_1=2$ ，$i_2=3$ ，根据迭代公式(3)计算$x^{\left(2,1\right)}$ ，$x^{\left(2,2\right)}$ 和$x^{\left(3\right)}$ ，计算过程与上述类似，不再赘述。

6) 反馈评价。及时提供反馈和评价，帮助学生了解自己的学习进展并指导学生进一步学习。例如，若取$p=m$ ，即可得到引言中的奇米诺算法，因而说明平均块卡茨马兹算法也是卡茨马兹算法的一种并行形式。

7) 总结反思。在学习过程结束时，帮助学生总结所学内容，并鼓励学生将新知识应用到实际问题中，例如，行指标的选取顺序对算法误差大小的影响；算法收敛速率的理论分析；若对系数矩阵的列做运算应该如何设计算法。巩固学习成果、梳理思路、反思与启发可进一步深化学生对知识的理解和记忆，并提高学生的学习成果转化能力。

4. 小结

几何解释在不同学科的案例教学中应用广泛，例如数学、物理、工程、生物等领域，几何都能提供一种通用的语言和工具，帮助学生跨学科地理解和应用所学知识。几何解释往往能够激发学生的好奇心和求知欲，因为几何化教学可以呈现出一些有趣的形态或者规律，促使学生更积极地参与到案例教学中，并通过自己的思考和探索来深化对知识的理解。本文以卡茨马兹型算法为例，将几何元素融入到并行计算课程教学实践中，旨在帮助学生能够更直观地感受到卡茨马兹算法及其变种算法之间的联系，能够建立更牢固的知识结构，并容易地将所学知识与实际问题联系起来。

融入延拓式教学，深挖卡茨马兹型算法与逐次超松弛迭代法(参考文献[6]第五章)之间的联系是本课程的一个研究方向，这有助于理解卡茨马兹型算法收敛速度、收敛条件、有效性等方面的性质；结合机器学习和优化方法，可以进一步提高卡茨马兹型算法的性能，如利用机器学习技术来预测迭代过程中需要更新的行指标，从而加速收敛过程。

在教学实践中，及时更新教学资源，引入最新的研究成果，保持教学内容的前沿性是本课程的一个改进内容。结合教学大纲，紧贴重点和难点，提取和整合具体的问题个案，如Google的网页排序模型计算大规模矩阵的特征值和特征向量(参考文献[6]第六章)、拟合高维数据求解大规模线性方程组(参考文献[6]第五章)等，建立一个具有一定关联性、典型性和真实性的案例库是本课程的另一个改进内容。

基金项目

中南民族大学校级教研项目“《并行计算》课程教学案例库的建设路径与实践”(项目编号：JYX23017)。