论文部分内容阅读
随着互联网的快速发展,网络信息量呈现出快速增长的趋势。人们当前所面临的问题是,如何从当前的海量数据中获取有价值的信息。奇异值分解(SVD)技术在信息分析应用方面表现出强大的生命力,在众多科学计算领域中具备极高的应用价值。然而,由于SVD算法的计算效率问题,使其难以在很多对于系统实时性要求较高的工程应用中直接使用。虽然硬件技术一直在发展,计算机的计算能力在不断提高。但是,计算机硬件发展的速度远远跟不上信息的增长速度。面对海量数据的分析任务,单机计算模式已经无法满足应用的需求。MapReduce分布式并行编程模型在时代背景的需求下应运而生。MapReduce编程模型擅长处理海量数据的分析和计算问题,能够有效地利用集群计算的优势缩短算法的计算时间。 针对分治策略求解SVD算法的特点,提出了一种适用于MapReduce编程模型的两阶段式的任务调度策略。对不同规模的矩阵分别采用逐层迭代以及多Job流水线式的任务调度策略,结合两种方式各自的优点,有效提高算法的运行效率。 分治法SVD算法分为分治和合并两个大步骤。设计了一种基于行索引的快速矩阵分治算法。并针对合并过程的每个数学推导步骤,设计了有效的并行化方法。矩阵相乘是整个算法执行过程中时间复杂度最高的计算步骤,提出了一种适用于分治法SVD的分块矩阵相乘方法。 通过开展多项实验来评估上述方法,实验结果验证了上述方法的有效性。在处理大规模的矩阵奇异值分解的计算时,相对单机版的分治法SVD算法获得了较高的加速比。实验结果进一步表明,基于MapReduce的分治法SVD算法具有高度的可扩展性。