论文部分内容阅读
作为代数运算的基石，矩阵的分解和求逆在科学计算、数据挖掘、机器学习等诸多领域有着广泛的应用。然而大规模矩阵的分解和求逆运算难以在当下流行的Hadoop、Spark等分布式计算平台上很好地并行，以至于Apache Mahout里对于Cholesky分解目前都只有单机的实现。其中一个重要的原因是矩阵分解与求逆运算结果中的一个元素往往依赖于输入矩阵的若干个元素。针对这一问题，本文基于Spark平台研究优化了大规模分布式稠密矩阵的LU分解、Cholesky分解以及求逆的并行化运算方法。本文首先采用分而治之的并行化设计思路对大规模矩阵进行分块，将整个计算任务划分为更小的计算任务，最终实现高效的并行化矩阵分解和矩阵求逆运算。然后，本文研究了计算过程中的一些优化方法，例如利用高性能本地库、缩小工作集等。实验结果表明，本文提出的并行化算法具有较高的效率，所提的优化方法总体平均能提升约60％的性能。此外，本并行化算法具有近线性的数据与节点可扩展性和受益于Spark平台的高容错性。据我们所知，本文是第一个基于Spark设计实现分布式大规模矩阵LU、Cholesky分解以及求逆算法的工作。