过刊浏览
摘要：对一维抛物型方程ut=au（a是常数），本文构造一类新型并行算法，此类算法实现按时间方向并行计算，打破空间并行、时间步进的传统并行算法，并行度高，简便快捷，有重大理论意义和实用价值。文中给出两个具体并行新算法，它们都绝对稳定，并行度都为m，精度分别是O(mt+h2)和，m可根据需要适当选取。最后数值结果验证了理论分析的正确性。
关键词：抛物型方程；并行算法；截断误差；稳定性条件
中图分类号：O246.1 文献标识码：A
引言
在渗透、扩散、热传导等许多自然科学领域中,都是用抛物型方程或方程组描绘的，更广泛的，在某些生物形态、化学反应、粒子间相互作用等等领域也与抛物型有关，因此经常会遇到求解如下一维抛物型方程初边值问题. 在大多数偏微分方程中，抛物型方程中的定解问题很难用解析式来表示，通常必须通过近似方法来求解，或者利用计算机进行数值求解。有限差分方法是计算机数值模拟最早采用的方法，至今被广泛的应用到各个领域，该方法是将求解域划分为差分网格，用有限个网格节点代替连续的求解域，用泰勒级数展开等方法，把方程中导数用网格节点上的函数值的差商代替并进行离散，从而建立以网格节点上的值为未知数的代数方程组。
近年来，一些快速需要计算的大型复杂的科学工程计算问题中，需要利用它们内部的并行性，设计合理的并行算法，将其分解成彼此独立的，又有联系的若干子问题，然后再分配给各台处理机，最后，将所有的处理机按事先编制好的并行算法在并行机上来完成。通常这些方程必须通过有限差分法求解，因此我们需要对已有的有限差分格式进行优化改造或重新构造，针对生活实践中的实际问题构造合理可行的并行算法。随着并行处理功能的高效计算机不断更新换代，极大推动并行数值方法的迅猛发展，一些传统的差分方法需要受到检验，需要在并行环境下比较它们的并行性和计算精度。因此不断完善已有的并行算法和构造出更合理的具有并行性的新算法是数值分析工作者的一项重要的工作。已有的显式和隐式差分方法中，显式差分格式适合于并行计算但稳定性条件差，必须使用较小的时间步长来计算，隐式差分格式一般无条件稳定，但需要求解线性方程组，实现并行算法有一定的困难，这些并行算法需要单独的研究。关于微分方程并行有限差分算法的研究，上世纪70年代有学者曾经提出“在此设计新算法的动力和意义几乎没有，并且确实没有新算法出现”，说明在80年代以前，计算并行领域并没有得到太多计算数学学者关注，包括抛物型方程在内的偏微分方程并行有限差分方法的研究没有得到足够的重视。随着高性能计算的出现和发展，并行算法逐渐成为一种求解偏微分方程的重要方法。
目前对该问题的并行算法有较大发展，上世纪八十年代D.J.Evans和A.R.Abdullah巧妙利用Saulyev非对称格式设计了交替分组显式格式，此方法具有较好的并行性和稳定性。随后，张宝琳等人根据其思想设计了分组显隐式格式，此方法不但具有明显的并行性，而且绝对稳定，他们又把具有二阶精度的格式引入到对流扩散问题中去，提出了分段交替格式。不过，分段交替格式和隐格式都需要求解三对角方程组，而求解三对角方程组不便于直接和有效的在并行机上应用，所以我们还需要通过不断的研究，构造具有良好稳定性、并行性和精度的新型并行算法。但传统的这些并行算法[1-5]，仅在空间上并行，在时间层上步进，如AGE、AGE-3、ASE-1、ASE-N等方法[2]。在ASC-N方法构造中, 是在两个相邻时间层利用交替技术设计出若干“段隐式”, 形成若干独立的方程组, 实现这两个时间层上的空间并行计算, 而在时间层上逐层步进计算。在这些方法构造中, “段隐式”和交替技术的应用是关键。利用交替方向技术得到的无条件稳定的区域分解方法，该方法不仅适用于并行算法而且无条件稳定，然而不尽人意的，交替分段算法计算精度不令人满意。本文从另一角度，以现有的两层绝对稳定为基础，把串行格式并行化，构造出两层绝对稳定、高精度的一类并行算法，并例举了其中两个具体算法，精度分别是O(mt+h2)和O((mt)2+h2)，并行度为m。该类算法的显著特点是打破传统实现时间层上并行计算，同时并行度可根据需要适当选择，方便快捷，这对以后构造新类型的时空并行算法具有重大启发意义。
1 并行算法的构造思想
定理：有限差分法构造的两层绝对稳定的差分格式对应能得到绝对稳定的并行算法，若原格式的截断误差为O(ta+hb)，则对应并行算法的截断误差为O((mt)a+ha)。
证明：不妨以最简隐格式[6]为例，取时间步长为t，空间步长为 h=L/M(M为正整数)，局部节点集：p￠=，其中：xj=jh,tn，并=u(xj,tn)，是的近似解。
令tk=kt，n￠=， 则rk=,
即P=P￠=. 从而就把建立在n,n+k两层上的差分格式：转化为在nii,n+1两层上的差分格式。 ，此为最简隐格式，所以得n,n+k两层上的绝对稳定的差分格式
其中：证毕
由此可知，以绝对稳定的两层差分格式为基础，实现串行格式并行化，构造出它们对应的绝对稳定的并行算法。该类并行算法的并行度为m，可根据实际需要，实现并行计算，方便快捷。下面就以古典隐格式和传统的C-N格式为基础，给出两个具体的时间方向的并行算法。
2 两个具体的并行算法
2.1 向后并行算法
在局部节点集上，可得如下算法：
其中，k=1,2,Lm,m=1,2,L.
计算过程：n=0层开始并行计算n=1,L L,n=m，而后以n=m层为基点并行计算n=m+1,L L,n=2m的值，继续下去. 如下：
；这样即把求解区域在时间方向上划分为若干小块，n=1,L L,n=m为一块，n=m+1,L L,n=2m为一块，L. 在每个小块内可实现并行计算，每步计算并行度为m.
2.2 C-N并行算法
在局部节点集上，可得到如下算法：
其中：k=1,2,L,m.m?Z+计算过程如上述.
3 数值例子
设抛物型方程的初边值问题为：，
已知该问题的精确解为:u(x,t)=e-tsinx,表1、表2分别给出向后并行算法、C-N并行算法和精确解的差，每步可并行计算m层的值，算例结果与理论分析结果相吻合.表中只列出偶数层节点jh,m-处的误差值：
表1：r=5 m=10
Table1: r=5 m=10
表2：r=5 m=10
Table2: r=5 m=10
4 结束语
从以上分析和数值例子可以看出，本文介绍的方法实现了两层绝对稳定的差分格式并行化计算，并行度可根据需要适当选取，方便快捷，具有较好的理论意义和应用价值，同时本方法对以后构造并行度更高的时空双方向并行算法具有重大启发意义。
没有PDF文件供下载
关键词：抛物型方程；并行算法；截断误差；稳定性条件
中图分类号：O246.1 文献标识码：A
引言
在渗透、扩散、热传导等许多自然科学领域中,都是用抛物型方程或方程组描绘的，更广泛的，在某些生物形态、化学反应、粒子间相互作用等等领域也与抛物型有关，因此经常会遇到求解如下一维抛物型方程初边值问题. 在大多数偏微分方程中，抛物型方程中的定解问题很难用解析式来表示，通常必须通过近似方法来求解，或者利用计算机进行数值求解。有限差分方法是计算机数值模拟最早采用的方法，至今被广泛的应用到各个领域，该方法是将求解域划分为差分网格，用有限个网格节点代替连续的求解域，用泰勒级数展开等方法，把方程中导数用网格节点上的函数值的差商代替并进行离散，从而建立以网格节点上的值为未知数的代数方程组。
近年来，一些快速需要计算的大型复杂的科学工程计算问题中，需要利用它们内部的并行性，设计合理的并行算法，将其分解成彼此独立的，又有联系的若干子问题，然后再分配给各台处理机，最后，将所有的处理机按事先编制好的并行算法在并行机上来完成。通常这些方程必须通过有限差分法求解，因此我们需要对已有的有限差分格式进行优化改造或重新构造，针对生活实践中的实际问题构造合理可行的并行算法。随着并行处理功能的高效计算机不断更新换代，极大推动并行数值方法的迅猛发展，一些传统的差分方法需要受到检验，需要在并行环境下比较它们的并行性和计算精度。因此不断完善已有的并行算法和构造出更合理的具有并行性的新算法是数值分析工作者的一项重要的工作。已有的显式和隐式差分方法中，显式差分格式适合于并行计算但稳定性条件差，必须使用较小的时间步长来计算，隐式差分格式一般无条件稳定，但需要求解线性方程组，实现并行算法有一定的困难，这些并行算法需要单独的研究。关于微分方程并行有限差分算法的研究，上世纪70年代有学者曾经提出“在此设计新算法的动力和意义几乎没有，并且确实没有新算法出现”，说明在80年代以前，计算并行领域并没有得到太多计算数学学者关注，包括抛物型方程在内的偏微分方程并行有限差分方法的研究没有得到足够的重视。随着高性能计算的出现和发展，并行算法逐渐成为一种求解偏微分方程的重要方法。
目前对该问题的并行算法有较大发展，上世纪八十年代D.J.Evans和A.R.Abdullah巧妙利用Saulyev非对称格式设计了交替分组显式格式，此方法具有较好的并行性和稳定性。随后，张宝琳等人根据其思想设计了分组显隐式格式，此方法不但具有明显的并行性，而且绝对稳定，他们又把具有二阶精度的格式引入到对流扩散问题中去，提出了分段交替格式。不过，分段交替格式和隐格式都需要求解三对角方程组，而求解三对角方程组不便于直接和有效的在并行机上应用，所以我们还需要通过不断的研究，构造具有良好稳定性、并行性和精度的新型并行算法。但传统的这些并行算法[1-5]，仅在空间上并行，在时间层上步进，如AGE、AGE-3、ASE-1、ASE-N等方法[2]。在ASC-N方法构造中, 是在两个相邻时间层利用交替技术设计出若干“段隐式”, 形成若干独立的方程组, 实现这两个时间层上的空间并行计算, 而在时间层上逐层步进计算。在这些方法构造中, “段隐式”和交替技术的应用是关键。利用交替方向技术得到的无条件稳定的区域分解方法，该方法不仅适用于并行算法而且无条件稳定，然而不尽人意的，交替分段算法计算精度不令人满意。本文从另一角度，以现有的两层绝对稳定为基础，把串行格式并行化，构造出两层绝对稳定、高精度的一类并行算法，并例举了其中两个具体算法，精度分别是O(mt+h2)和O((mt)2+h2)，并行度为m。该类算法的显著特点是打破传统实现时间层上并行计算，同时并行度可根据需要适当选择，方便快捷，这对以后构造新类型的时空并行算法具有重大启发意义。
1 并行算法的构造思想
定理：有限差分法构造的两层绝对稳定的差分格式对应能得到绝对稳定的并行算法，若原格式的截断误差为O(ta+hb)，则对应并行算法的截断误差为O((mt)a+ha)。
证明：不妨以最简隐格式[6]为例，取时间步长为t，空间步长为 h=L/M(M为正整数)，局部节点集：p￠=，其中：xj=jh,tn，并=u(xj,tn)，是的近似解。
令tk=kt，n￠=， 则rk=,
即P=P￠=. 从而就把建立在n,n+k两层上的差分格式：转化为在nii,n+1两层上的差分格式。 ，此为最简隐格式，所以得n,n+k两层上的绝对稳定的差分格式
其中：证毕
由此可知，以绝对稳定的两层差分格式为基础，实现串行格式并行化，构造出它们对应的绝对稳定的并行算法。该类并行算法的并行度为m，可根据实际需要，实现并行计算，方便快捷。下面就以古典隐格式和传统的C-N格式为基础，给出两个具体的时间方向的并行算法。
2 两个具体的并行算法
2.1 向后并行算法
在局部节点集上，可得如下算法：
其中，k=1,2,Lm,m=1,2,L.
计算过程：n=0层开始并行计算n=1,L L,n=m，而后以n=m层为基点并行计算n=m+1,L L,n=2m的值，继续下去. 如下：
；这样即把求解区域在时间方向上划分为若干小块，n=1,L L,n=m为一块，n=m+1,L L,n=2m为一块，L. 在每个小块内可实现并行计算，每步计算并行度为m.
2.2 C-N并行算法
在局部节点集上，可得到如下算法：
其中：k=1,2,L,m.m?Z+计算过程如上述.
3 数值例子
设抛物型方程的初边值问题为：，
已知该问题的精确解为:u(x,t)=e-tsinx,表1、表2分别给出向后并行算法、C-N并行算法和精确解的差，每步可并行计算m层的值，算例结果与理论分析结果相吻合.表中只列出偶数层节点jh,m-处的误差值：
表1：r=5 m=10
Table1: r=5 m=10
| 层数 Number of layers |
节点j Nodal point j |
||||
| 30 | 70 | 110 | 150 | 190 | |
| n=10002 | 1.0638e-007 | 2.7851e-007 | 3.4425e-007 | 2.7851e-007 | 1.0638e-007 |
| n=10004 | 1.0613e-007 | 2.7785e-007 | 3.4345e-007 | 2.7785e-007 | 1.0613e-007 |
| n=10006 | 1.0589e-007 | 2.7723e-007 | 3.4267e-007 | 2.7723e-007 | 1.0589e-007 |
| n=10008 | 1.0566e-007 | 2.7662e-007 | 3.4193e-007 | 2.7662e-007 | 1.0566e-007 |
| n=10010 | 1.0544e-007 | 2.7605e-007 | 3.4121e-007 | 2.7605e-007 | 1.0544e-007 |
表2：r=5 m=10
Table2: r=5 m=10
| 层数 Number of layers |
节点j Nodal point j |
||||
| 30 | 70 | 110 | 150 | 190 | |
| n=10002 | 1.3150e-010 | 3.4426e-010 | 4.2553e-010 | 3.4426e-010 | 1.3150e-010 |
| n=10004 | 1.3123e-010 | 3.4356e-010 | 4.2467e-010 | 3.4356e-010 | 1.3123e-010 |
| n=10006 | 1.3094e-010 | 3.4281e-010 | 4.2374e-010 | 3.4281e-010 | 1.3094e-010 |
| n=10008 | 1.3063e-010 | 3.4198e-010 | 4.2271e-010 | 3.4198e-010 | 1.3063e-010 |
| n=10010 | 1.3027e-010 | 3.4105e-010 | 4.2156e-010 | 3.4105e-010 | 1.3027e-010 |
从以上分析和数值例子可以看出，本文介绍的方法实现了两层绝对稳定的差分格式并行化计算，并行度可根据需要适当选取，方便快捷，具有较好的理论意义和应用价值，同时本方法对以后构造并行度更高的时空双方向并行算法具有重大启发意义。
没有PDF文件供下载
