大规模非对称线性方程组的并行计算方法研究

黄杰英

【摘要】大规模非对称线性方程组的求解在我国工程、计算机、资源探测、核爆模拟等领域都十分重要，随着我国计算机和工程领域发展，大规模非对称线性方程组求解所需时间也越来越长，正是因为求解的重要性和计算的耗时性，因此，近年来越来越多的科学研究机构组织与社会数学科学工作者，投入了大量的人力和物力，来对大规模非对称线性方程组的求解进行研究。在众多算法中，并行计算方法逐渐脱颖而出，本文就大规模非对称线性方程组的并行计算方法进行的研究，提出了多种简便的新型并行计算方法，从而缩短了非对称线性方程组的计算时间。

【关键词】梯度计算法 线性方程组 分裂叠加法 并行计算

【中图分类号】G642 【文献标识码】A 【文章编号】2095-3089（2017）15-0211-02

一、引言

目前我国侧重于大规模的发展科学技术与工程，資源探测，核爆模拟等领域。这些领域涉及了众多的复杂非对称线性方程组的计算[1-3]。在众多求解方法中，并行计算法计算法的应用范围最广，国内对并行计算求解的需求量是推动并行计算法快速发展的主要动力。在我国科学发展的道路上，对并行计算求解法的需求是无止境的，并行计算法是电子计算机工程中，自然气候，天气预报，核爆数值模拟等等领域对非对称线性方程组求解的核心技术之一。据调查显示，在部分非对称线性方程组计算领域中，方程组的求解占据了80%-90%的时间，因此，大规模非对称线性方程组并行计算方法的研究已经成为了目前十分重要的研究领域。

二、并行计算

并行计算法是指将大规模复杂的非对称线性方程组，并行到同一台计算机或系统上，然后有系统将方程组分为若干个小方程组，再将小方程组分别下发给该系统的各个子方程组处理器，由各个子处理器统一进行并行计算，各子处理器间进行计算的数据传输，交换，协调并行的各自进行计算，从而达到加快计算速度的目的。要对大规模复杂的非对称线性方程组进行并行计算就必须要满足并行计算机，并行计算算法，并行计算方程这三个条件。并行计算算法是指，进行计算的方程组必须满足并行计算的条件，通常可以进行并行计算的方程组需要满足方程组可以分解成为若干个小方程组的条件，只有可以分裂为若干个小方程组的方程组才可以进行并行计算，而将方程组分为若干个子任务的过程，我们称为并行计算算法。并行计算的编程是指，下分给个子服务器任务后，服务器在并行计算机提供的编程程序上进行独立的求解计算。

1.并行计算程序模型

并行计算程序模型通常分为内存处理系统共享型模型，并行处理器消息传输型模型，信息数据并行模型三种。 内存处理系统共享型模型主要是进行大规模复杂的非对称线性方程组并行计算程序中的进程或线程时所采用的模型。其模型可以通过对数据信息共享内存区的整体信息进行操作，从而达到使个子服务器间进行相互的数据信息传输和配合的目的。一边来说，并行计算程序的程序员只需要集中精力在并行计算子任务的分配以及映射到各子服务器的进程或线程任务的分配，而对于那些被处理掉的无用数据信息所处的位置并不需要进行共享和编程。我们较为常见内存处理系统共享型模型的编程主要可以分为共享内存模型式和自行编写模型编程式。并行处理器消息传输型模型是指各个子处理器间的并行任务之间不能通过编程程序的地址来进行相互的数据信息传输或交换，只能独立的进行计算任务。各子服务器间若想要通过访问其他子服务器来获得另一个子服务器的所进行的任务数据信息，就必须向核心任务系统提出数据相互通信请求，请求成功后才可以进行各子服务器间的数据信息传输和交流。因此，一般来说，进行并行计算系统编程程序的程序员必须在进行任务划分后将子任务映射到编程进程的实体，然后在编程程序码中加入进行数据交换的请求代码，此编程模式要求编程程序员必须关注个子服务器的数据的分布情况。一般我们较为常见的编程就归类于并行处理器消息传输型模型，编程程序号自行编写多个小进程，并通过各进程间的通信方来进行交互交换数据信息的模型方法也可以归类为此模型。信息数据并行模型是指该种模型方法可以通过在并行计算机和并行计算机上的任务分配和网络信息传递来实现大规模复杂的非对称线性方程组的求解。信息数据并行编程模型一般可以提供给编程程序员一个可观全局性的网络空间地址，程序员可以通过该地址来观察各子服务器间的数据传输交流及方程组求解情况，对不同的数据信息都可以执行相同的操作来进行数据的整体控制。常见的MICD以及FRCOLD编程都属于信息数据并行的编程模型。三种并行编程程序的模型如表一所示。

2.并行计算程序设计方法

并行计算程序的设计方法主要分为并行任务的划分，并行处理器间的相互数据信息传输交流，各子任务处理器求解结果信息的汇总和最终处理结果的显示四个步骤。并行任务的划分主要是将大规模复杂的非对称线性方程组的求解计算任务划分为尽可能多的小任务，然后将这些小任务分配给各子处理器系统，由子处理器系统进行计算。折衷法方法可以充分的发展并行算法的计算并行性和计算范围的可扩展性。通常我们所采用的子任务划分方法分为两种。一是按照需要处理的大规模复杂的非对称线性方程组的数据进行小任务的分解和按照算方程组的功能来进行分解。在进行数据分解和计算功能的分解时，需要做到两种分解方式的计算数据和计算区域，计算方法相互不重复，无交集，互为独立的处理系统。

三、梯度计算法

基于大规模复杂的非对称线性方程组的并行计算方法中的方程组分解法，我们对大规模复杂的非对称线性方程组的并行计算方法进行了深入的研究，提出了一种新型的计算方法，梯度计算法，梯度计算法主要是对并行计算法中搜索方向技术进行优化，从而提出的一种新兴的简便计算方法，一般称为多方向计算方法。这种计算方法主要是对划分到每个子服务器的任务进行定向搜索，传统的并行计算方法是对所有子服务器的方向进行逐个搜索，其搜索范围广，耗时长，因此会延缓方程组的求解时间，而梯度计算法则是对子任务进行定向搜索，其搜索范围小，用时较短。无需像传统方法那样进行全方面的搜索。梯度计算方法的关键是利用对小型的线性方程组的求解取代了传统方法中对方程组整体内积的求解计算。将大规模的非对称线性方程组划分成为每个小方程组，每个小方程组的结构通常是基于划分区域的分解方式和定向搜索方向的选取，其核心主要是利用直接求解法代替传统求解法进行方程组求解。若用梯度法的近似求解，则可以得出MISD一CAG方法的一种近似与梯度求解的形式，这种近似方法仅需要对相邻两个子区域之间的数据信息进行传输，通讯和配合。从而完全去掉了方程组的整体内积的计算。我们将这种近似梯度法求解的方法称之为共轭梯度方法，共轭梯度方法特别适合大规模复杂的非对称线性方程组的计算。

1.共轭梯度法计算非对称线性方程组

大规模的非对称线性方程组求解，耗时的主要问题在于方程组的不对称性。对于传统并行计算方法中的方程组的正对称问题上，传统的并行计算方法很难讲划分到各个子服务器的小方程组进行正对称的计算，因此一般来说求解匹配结果时间过长，会造成方程组的求解效率降低。因此，在对大规模的非对称线性方程组进行求解时，我们最需要解决的就是方程组的正对称问题对于对称问题，因此，我们采取共轭梯度的方法来对对称的线性方程组进行求解计算。共辘梯度方法可以非常有效的解决非对称线性方程组中的子空间搜索方法。一般来说，共轭梯度法对大规模的非对称线性方程组的计算难点主要在于，对各个子任务的并行化和对子任务空间的内积进行计算。对子服务器方程组整体内积的计算在大规模非对称线性方程组的并行计算中显得尤为重要，因为在对方程组进行并行计算过程中，子方程组的内积总是担当同步存贮点并需要整体数据信息进行相互的交流，传输和存贮。对于子服务器内积的计算，我们既需要对子服务器方程组的计算方法进行优化，也需要对聚集在子方程组上的数据信息进行整理和计算。因为多有的子服务器都需要知道处理结果，再根据数据信息的处理结果进行进一步的求解计算。对各个子服务器方程组的求值结果进行进一步的计算，主要取决于进行并行计算的计算机和进行并行计算的花销。当子服务器方程组计算花销较大时，整体的子服务器通讯占领了计算的主导地位。对并行计算处理系统已经造成了严重的限制。因此，解决子服务器内积的问题尤为重要。

共轭梯度处理方法每步只需两个子服务器的内积计算，在并行计算机的处理系统中，一般来说每并行一个方程组，只需要对其中的五个元素进行矩形列阵的计算。当自服务器处理系统的元素量超过200时，子服务器的内积就占领了主导地位，共轭梯度法主要是通过控制自服务器内积的方法来对子服务器进行控制，确保其计算的流畅性。共轭梯度处理方法每步只需要对两个子服务器内积进行计算，计算依次进行，成梯度方式，确保内积不会占领数据的主导地位。通过降低子计算机之间的同步点数来提高子计算机与计算开销的比值。将两个分离的子计算机内积用三个连续的小内积进行代替计算，这三个小内积可以进行并行计算，从而可组合它们的计算数据，对小内积間的计算数据进行对比分析和取值。从而提高了计算效率，减小了子计算机内积对大规模的非对称线性方程组求解的影响。

2.分裂叠加法

分裂叠加法计算大规模的非对称线性方程组主要是通过对主并行计算机的分裂来实现。进行并行计算的各子计算机之间是相互独立的，因此，对于一台主计算机控制多台子计算机进行计算的方法可以通过分裂叠加法来实现。在计算的每一步，每一个子计算机都会进行一次局部的数据信息传输，将数据信息统一传输到主计算机上，集中由主计算机进行数据的计算。然后将计算后的数值传输回各子计算机上，再由子计算机进行下一步的计算。计算后将数据信息在此传输到主计算机中，由主计算机进行数据信息的计算，再将两次计算的结果进行叠加，将叠加出的新数据信息传输回子服务器，由子服务器进行计算。以开始下一步的叠加计算，以此类推，最终叠加出的数据则为该方程组的求值。采用缩小计算规模的方式，来减小大规模的非对称线性方程组的计算时间，从而达到计算的高效性。

四、结论

随着科学技术的不断发展，越来越多的科学和工程领域需要进行对大规模的非对称线性方程组进行并行计算。本文就并行计算法的基础上提出了新型的更适合对非对称线性方程组的计算方法。首先，我们先对并行计算法的计算模型进行了分析。得出了并行计算系统程序的建立方法，从而设计了解非对称线性方程组的系统程序。之后我们提出了共轭梯度的方法来对非对称线性方程组进行并行计算，共轭梯度法主要是对传统梯度法中的子计算机内积进行优化，从而增大计算效率。最后提出了分裂叠加法，通过对主计算机的方程组进行分裂，然后依次对数据进行叠加和新数据的计算，传输，叠加。从而减小计算难度，增加计算效率。本文所提出的计算方法，解决了大规模非对称线性方程组的计算难度。

参考文献：

[1]白中治，王德人.异步并行矩阵多分裂多参数松弛方法，高校计算数学学报，1994，16（2）：107-115.

[2]吴建平，王正华.李晓梅线性方程组的高效求解与并行计算湖南：湖南科学技术出版社，2004.

[3]王驰，刘羽.GPU优化的大规模线性方程组并行求解的研究与比较[J].信息通信，2016，6（12）：23-30.