最好的大型稀疏矩阵求解器

	高性能计算 --- 高效、稳定、通用 ---	gsp@grusoft.com

主页 \| GSS \| 文档 \| 资源 \| 案例 \| 流媒体 \| BLOG \| 关于

GSS(GRUS SPARSE SOLVER)是目前最优秀的大型稀疏矩阵求解器。主要性能如下：

? 1、速度明显优于同类求解器，其中分解时间不到UMFPACK的一半。

?2、稳定，精度高，有些矩阵只有GSS可求解。

?3、支持各种操作平台，支持32位与64位系统。

?4、并行性良好，支持最多32个CPU。

?5、尤擅长超大规模矩阵，病态矩阵。

6、10万阶免费试用版。试用申请
7、多种应用模式，可根据客户需求定制。

GSS 针对不同类型的稀疏矩阵采用不同的解法。

1.1 对称正定矩阵

GSS采用LL^T分解（cholesky 分解）。即对称正定阵A存在如下分解,其中L为下三角矩阵。

A=LL^T

cholesky 算法理论成熟，表现稳定，解的精度很高。稀疏求解中有多种高性能的实现，例如可分为Left-looking，Right–looking及Crout 三类。GSS采用Right–looking multi-frontal 算法，灵活、高效、并行性好。对某些正定矩阵，采用多波前/波前混合算法，以减少数据移动量，进一步提高速度。

1.2 对称不定矩阵

GSS采用对称置换的LDL^T分解。即

PA P^T =LDL^T

其中L是单位下三角阵，D由阶数为1或2的对角块构成，P是置换阵。

对称不定求解在理论上比较成熟，但具体实现还待提高。表现在稳健的算法性能较差，而高性能的算法不够稳健，无法解出各种类型的不定矩阵。例如Bunch-Parlett算法可以很好的解决满阵问题，但应用到稀疏矩阵上时，效率与稳定无法兼顾。GSS正致力更高效稳健的不定阵算法。

1.3 不对称矩阵

GSS采用不对称置换的LU分解。其基本形式如下：

PAQ=LU

其中L是单位下三角阵，U是上三角阵，P,Q是置换阵。

不对称矩阵的求解理论还在发展，还有很多可以改进的地方。GSS在确保通用可靠的基础上，尽量提高效率。在符号分析中采用block upper triangular排序，QUOTIENT-GRAPH模型，在数值分解中灵活运用多种主元方法。对于困难矩阵，并采用矩阵平衡, refine等技术。实测中，综合性能较其它求解器有明显的优势，有一些矩阵只有GSS可以求解。

通过不对称置换把“大元素”置换到对角元，可提高速度和精度。GSS采用网络流算法，这也是该算法首次用于“大元素”置换问题。

通过block upper triangular排序，可以得到一系列具有特殊性质的对角块，即strong hall matrix。随后的分析中充分利用这个特性，以提高效率。

依据矩阵的一些性质，GSS采用SIMPLE和HARD两种策略。HARD策略适用于非常不对称、对角元很多都是零、条件数很大等困难矩阵。在求解时会采用矩阵平衡技术，主元置换算法，动态符号分析及iterative refine等以提高解的精度，需要更多的时间。其它的矩阵采用SIMPLE策略，速度更快。

不对称矩阵数值分解过程中，仍需要一些符号分析，而符号分析算法的flops是很低的。GSS采用很多技巧，将所需的符号分析工作减到最少。