若干大型稀疏非线性矩阵方程的数值解法

随着现代科学技术的迅速发展，非线性矩阵方程越来越多地出现在许多科学与工程计算领域，如海洋物理，控制论以及噪音污染，交通运输等很多问题的解决最终往往归结为一个非线性矩阵方程。因此，研究非线性矩阵方程的解的存在性，敏感性以及如何求解是非常有意义的。特别地，对于如何有效、快速、准确的求出它们的解更是人们所关注的。非线性矩阵方程的数值求解已成为科学研究的热点之一。为使所设计的算法更具有效性和可执行性，我们希望算法适合在并行环境下运行，这就需要算法中的公式运算要基本，同时，要尽量使算法收敛速度快，计算量少，数值稳定。寻求满足上述条件的求解大型稀疏非线性矩阵方程的算法是我们将要研究的主要问题。对该问题的研究，将有利于其它相关学科的发展，也将促进计算机实用软件的开发。 2100433B

在科学与工程领域中进行数值计算时经常需要处理大型的稀疏矩阵，这些矩阵的特征一是阶数很大，二是含有大量的零元，使得无法使用传统的稠密矩阵存储方案和算法。由于矩阵阶数太大，若存储整个矩阵，将会占用大量的存储空间，甚至会超出计算系统的存储容量，因此需要设计专门的稀疏存储方案，尽可能的减少零元素的存储。

稀疏矩阵算法是以稀疏矩阵作为核心数据结构的算法。与稠密矩阵算法相比，稀疏矩阵算法的最大特点是通过只存储和处理非零元素从而大幅度降低存储空间需求以及计算复杂度，代价则是必须使用专门的稀疏矩阵压缩存储数据结构，因而在计算过程中引入了大量的离散间接寻址操作。稀疏矩阵算法是典型的不规则算法，计算访存比很低，并且计算过程中的访存轨迹与稀疏矩阵的稀疏结构相关，很难发掘计算过程中的时空局部性，因此在传统的基于Cache的处理器上稀疏矩阵算法的计算效率很低。为了提高稀疏矩阵算法的计算效率，需要从稀疏存储数据结构和稀疏矩阵算法两方面对现有算法进行改进。

按照应用领域的不同，稀疏矩阵算法分为两类，一类是非数值计算算法，典型代表是图搜索算法，包括宽度优先搜索等核心算法；另一类则是数值计算算法，典型代表是稀疏线性方程组求解，包括稀疏矩阵向量乘、稀疏三角方程组求解以及稀疏矩阵分解等核心算法。

本教材根据（全日制、在职）工程硕士研究生的特点和培养创新型人才的要求，将矩阵论与数值分析的有关理论与方法按内容体系编写.全书共6章，分别是矩阵运算与矩阵分解、线性空间与线性变换、矩阵的若尔当标准形与矩阵函数、方程与方程组的数值解法、数值逼近方法与数值微积分、常微分方程的数值解法.为提高工程硕士研究生应用数学方法和科学计算解决实际问题的能力，各章最后一节给出了一些应用案例，对一些重要的问题给出了求解问题的MATLAB程序.

本书可供工程硕士研究生以及理工科非计算数学专业的大学生阅读，也可供科技工作者参考.

面向算法加速器的稀疏矩阵算法并行化方法

由于算法加速器采用了与通用处理器完全不同的体系结构和编程模型，因此需要专门设计针对算法加速器的并行程序。与通用处理器相比，算法加速器能够运行更多的线程，因此一方面需要将计算任务划分为更多的子任务，实现细粒度并行；另一方面需要考虑线程间的负载均衡和数据局部性，特别是线程间的通信和同步开销。与通用处理器相比，算法加速器更容易受到不规则访存和计算的影响，因此必须通过矩阵预处理等手段提高计算的规则性和数据的局部性。

通用处理器与算法加速器协同计算策略

异构体系结构的计算单元包括通用处理器和算法加速器两部分。在学术研究中通常分别针对这两种计算单元设计并行算法，但在实际应用中，需要同时利用计算系统的所有计算资源以获取最高性能。然而，现有的针对通用处理器和算法加速器的并行算法分别采用了不同的编程模型和优化策略，无法直接互相迁移，并且在协同计算过程中，不但需要在两个平台上都能高效运行的并行程序，而且需要实现通信与计算的重叠以隐藏数据传输的开销，这些都要求对现有的算法针对异构平台进行重新设计。

面向稀疏结构特征的数据结构和算法映射

不同应用领域的稀疏矩阵往往具有不同的稀疏结构特征，这些特征因问题而异；具有不同稀疏结构特征的稀疏矩阵往往对应不同的最优存储方案以及不同的并行算法实现。在计算过程中，对于稀疏矩阵算法的不同计算阶段，会因稀疏结构导致的计算特征的不同而适合在通用处理器或算法加速器上运行或是由二者协同计算。因此，研究矩阵的稀疏结构并设计相应的数据结构和算法映射策略，能够有效提高算法对于不同矩阵和不同计算平台的适应性。 2100433B