0 引 言
　　
　　在工业、金融、经济、物理和工程应用中存在着相当一类非线性问题,在这些问题中,尽管控制方程是由线性椭圆算子决定,但由于解被限制在Banach空间的某一子凸集而非子空间上,使得其相应的变分原理是用关于椭圆算子和障碍容许函数的凸集变分不等方程来描述,从而这一类非线性问题的求解可以转化为求解一个非线性变分不等式.这一情况的典型例子是“障碍问题”.
　　随着变分不等式在各学科、各领域的广泛应用,有效数值算法的研究也日益变得重要.在过去几十年里,已提出了许多数值方法,包括投影法及其变分形式、Wiener-Hopf方程、辅助原理、分解法、动态系统法等[1].但由于在投影类方法中,计算投影本身很困难,而且,投影法和Wiener-Hopf方程不能拓广到含有非线性微分(不可微)函数的一类变分不等式,所以没有得到广泛应用.于是研究者们考虑先把连续问题离散化.常用的离散法主要有差分法和有限元法.差分法不能用于存在障碍和其他非线性变分约束条件的问题,例如,障碍问题和自由、移动边界问题;而有限元法对线性和非线性问题都适用,且允许区域几何形状和边界条件的改变,因此研究者们首选有限元离散变分不等式.本文所要做的工作是:考虑分片线性三角有限元离散的椭圆型变分不等式的数值算法.
　　如果把有限元离散后的变分不等式写成极小化问题,形式上与约束二次规划问题相似,所以用最优化方法求解离散的变分不等式是自然的[2-6],其中比较有效的是投影法、线性逼近法、松驰法和罚函数法.然而,源于椭圆型变分不等方程自身的数学特性,使得相应的有限维代数不等方程式与一般的规划问题相比,系数矩阵具有对称、正定、稀疏、带状等特点.基于此,对于离散的变分不等式,往往不采用最优化方法,而是把求解一般变分有限元方程的解法加以修正后用于有限维代数不等方程式.例如投影点松驰法和块松驰法是至今仍广泛应用的经典方法[7].文献[8]指出,如果变分不等式是用分片线性三角元离散的,则当三角剖分不断加密时,上述迭代法的收敛率会迅速下降,导致它们不收敛.而基于三角剖分分层的多层次方法可以克服这一困难.例如区域分解法和多重网格(MG)法,近年来也被广泛用于离散变分不等方程的数值分析中[8-21].其中文献[20-21]中的多重网格法本质上是一种基于积极集策略(active-set strategy)[21]之上的线性化方法.该方法源于离散变分不等方程所具有的线性互补性,其主要思想是:在每一迭代步预先指定一组积极约束,再为新迭代的计算求解一个建立在非积极集上的线性子问题.具体说来,由内、外两重迭代构成,外迭代即积极集策略,内迭代是求解线性子问题的多重网格求解器.因为子问题的系数矩阵对称正定,且为了利用自适应有限元提高解的精度,文献[26]用了适合自适应的预条件共轭梯度(PCG)法代替文献[21]中MG法做内迭代.文献[22]已证明MG法在求解大规模方程组时具有收敛快、省时等优点,问题越复杂越能体现其优越性,尤其是代数多重网格(AMG)法,它应用于正定线性方程组时是健壮和灵活的,且比几何多重网格法应用更广泛,例如,三维问题、任意区域的问题、非一致网格等等,同时它更容易与其他非多重网格软件结合.据笔者所知,在现有的多重网格法文献中,还没有将AMG算法应用于求解非线性变分不等式的例子[22].本文旨在用文献[21]提出的积极集策略将标准线性方程组的AMG求解器修正后,求解离散变分不等式.作为模型问题,笔者考虑了一个最基础、最重要的变分不等式——具有自共轭椭圆算子的障碍问题.数值结果表明,修正的AMG算法在一致网格和h-自适应网格上求解离散变分不等方程时均能快速收敛.但要达到特别高的精度,所花计算时间较长.笔者考虑将算法并行化.
　　多重网格算法发展的20年,也是并行计算机发展的20年.由于多重网格的数值高效性,自它诞生以来,人们就致力于其原理并行度的探讨,在各种类型的机器上对经典多重网格算法的并行化进行了大量实验,提出了一些有效的实现方法[23-25].
　　目前,多重网格算法中成熟的并行化工作主要集中在串行程序的并行化,在尽量不影响算法收敛性的前提下考虑并行,这样能保持原有算法的数值高效性.本文将根据修正的AMG算法中块迭代自身的并行度,将其算法并行化.数值算例表明了并行算法的有效性.
　　文章安排如下:第1节,定义模型问题的有限元离散;第2节在简明介绍文献[21]提出的积极集策略思想后,详细介绍了修正AMG算法;第3节提出算法的Master-Slave并行格式;第4节给出数值实验,以说明算法的有效性和并行的效率.