一种基于消去树的LDL分解方法及其在营销优化计算中的应用

基于分解因子消去树理论，提出一种新的LDL分解计算方法，它利用消去树结构，将LDL分解过程分为非零元素结构预测和数值计算两部分，从而有效避免多余的内存开销和数值运算．并给出其应用与One to One营销优化算法的实现方法．测试结果表明，该方法能以较少的乘法运算次数快速确定分解因子，从而大幅度提高One to One营销优化算法的性能．     

稀疏限制的增量式鲁棒非负矩阵分解及其应用

针对鲁棒非负矩阵分解（RNMF）的运算规模随训练样本数量逐渐增多而不断增大的问题，提出一种稀疏限制的增量式鲁棒非负矩阵分解算法。首先，对初始数据进行鲁棒非负矩阵分解；然后，将其分解结果参与到后续迭代运算；最后，在对系数矩阵增加稀疏限制的情况下与增量式学习相结合，使目标函数值在迭代求解时下降地更快。该算法在节省运算时间的同时提高了分解后数据的稀疏度。在数值实验中，将所提算法与鲁棒非负矩阵分解算法、稀疏限制的鲁棒非负矩阵分解（RNMFSC）算法进行了比较。在ORL和YALE人脸数据库上的实验结果表明，所提算法在运算时间和分解后数据的稀疏度等方面均优于其他两个算法，并且还具有较好的聚类效果，尤其在YALE人脸数据库上当聚类类别数为3时该算法的聚类准确率达到了91.67%。     

大型稀疏线性方程组符号LU分解法

基于有限元总刚矩阵的大规模稀疏性、对称性等特性,采用全稀疏存储结构以及最小填入元算法,使得计算机的存储容量达到最少。为了节省计算机的运算时间,对总刚矩阵进行符号LU分解方法,大大减少了数值求解过程中的数据查询。这种全稀疏存储结构和符号LU分解相结合的求解方法,使大规模稀疏线性化方程组的求解效率大大提高。数值算例证明该算法在时间和存贮上都较为占优,可靠高效,能够应用于有限元线性方程组的求解。     

稀疏约束图正则非负矩阵分解的增量学习算法

针对非负矩阵分解后数据的稀疏性降低、训练样本增多导致运算规模不断增大的现象,提出了一种稀疏约束图正则非负矩阵分解的增量学习算法。该方法不仅考虑数据的几何信息,而且对系数矩阵进行稀疏约束,并将它们与增量学习相结合。算法在稀疏约束和图正则化的条件下利用上一步的分解结果参与迭代运算,在节省大量运算时间的同时提高了分解后数据的稀疏性。在ORL和PIE人脸数据库上的实验结果表明了该算法的有效性。     

基于GPU的稀疏矩阵Cholesky分解

稀疏矩阵Cholesky分解是求解大规模稀疏线性方程组的核心算法,也是求解过程中最耗时的部分.近年来,一系列并行算法通过图形处理器(GPU)获得了显著的加速比,然而,由于访存的不规则性以及任务间的大量数据依赖关系,稀疏矩阵Cholesky分解算法在GPU上的计算效率很低.文中实现了一种新的基于GPU的稀疏矩阵Cholesky分解算法.在数据组织方面,改进了稀疏矩阵超节点数据结构,通过超节点合并和分块控制计算粒度;在计算调度方面,将稀疏矩阵Cholesky分解过程映射为一系列的数据块任务,并设计了相应的任务生成与调度算法,在满足数据依赖性的前提下提高任务的并行性.实验结果表明,该算法能够显著提高稀疏矩阵Cholesky分解算法在GPU上的实现效率,在单个GPU上获得了相对4核CPU平台2.69~3.88倍的加速比.     

基于Spark的矩阵分解与最近邻融合的推荐算法

随着当前移动互联网的快速发展,人们所面临的信息过载问题变得尤为严重,大数据场景下对特定用户的个性化推荐面临着巨大挑战. 为了进一步提高推荐的时效性、准确度以及缓解面临的大数据量. 提出了一种矩阵分解推荐算法在大数据环境下的优化算法模型. 该模型通过在传统矩阵分解推荐算法的基础上融合了用户以及物品的相似性计算,在训练目标函数的过程中,即融入用户以及物品的前k个最近邻居的相似性计算,增强了算法的推荐准确度. 利用Spark在内存计算以及迭代计算上的优势,设计了一种Spark框架下的矩阵分解与最近邻融合的推荐算法. 通过在经典数据集—MovieLens数据集上的实验结果表明,该算法与传统的矩阵分解推荐算法相比,可以很好的缓解数据稀疏性,提高推荐算法的准确度,并且在计算效率方面也优于现有的矩阵分解推荐算法.     

应用稀疏约束的非负正则矩阵学习算法

针对非负矩阵分解后的数据稀疏性较低,训练样本偏多导致运算规模持续增大的普遍现象,本文提出基于稀疏约束的非负正则矩阵学习算法,本文算法是在样本几何结构信息条件上执行非负矩阵分解操作,并且与学习算法结合,不仅能够有效保持样本局部结构,还能够充分利用前期分解结果参加迭代运算,从而达到降低运算时间目的. 本文实验表明与其他算法比较来说,本文方法在ORL人脸数据库上最多节省时间14.84 s,在COIL20数据集上为136.1 s;而在分解后数据的稀疏性上,本文方法在ORL人脸数据库上的稀疏度提高0.0691,在COIL20数据集上为0.0587. 实验结果表明了算法有效性.     

一种基于GPU的预计算辐射度传递全频阴影算法

针对基于CPU的实时渲染全频阴影算法中内存使用效率低下、CPU运算能力消耗严重等问题，提出了基于GPU的改进算法．在预计算过程中使用基于小波变换的预计算辐射度传递（PRT）算法生成PRT矩阵，然后将其编码为易于被GPU使用的稀疏形式；在渲染过程中使用具有高度并行性的片断渲染器程序进行稀疏矩阵向量快速乘法计算，以求得最终渲染结果．相对于目前基于CPU的相应算法，算法充分利用了GPU的并行计算能力，平衡了CPU与GPU之间的负载，并同时降低了内存消耗．在一般情况下，算法可以获得超过一个数量级的性能提升．     

稀疏约束下非负矩阵分解的增量学习算法

非负矩阵分解(NMF)是一种有效的子空间降维方法。为了改善非负矩阵分解运算规模随训练样本增多而不断增大的现象,同时提高分解后数据的稀疏性,提出了一种稀疏约束下非负矩阵分解的增量学习算法,该算法在稀疏约束的条件下利用前一次分解的结果参与迭代运算,在节省大量运算时间的同时提高了分解后数据的稀疏性。在ORL和CBCL人脸数据库上的实验表明了该算法降维的有效性。     

分布式系统可靠性的一种计算方法

分析了分布式程序可靠性问题及其在分布式系统应用时的局限性,提出了分布式系统程序可靠性的计算问题.通过采用ECP分解算法对连接矩阵进行迭代分解并实时判断终止条件,可以直接计算出分布式系统可靠性结果.同时对算法中使用的存储结构进行优化,使得算法占用较少的内存.最后给出了例子来论证算法.     

大数据环境下基于概率矩阵分解的个性化推荐

概率矩阵分解是近几年广泛应用的协同过滤推荐方法。针对如何利用矩阵分解技术提高推荐质量以及在大数据环境下如何突破计算时间、计算资源瓶颈等问题进行研究,提出了Improved Probabilistic Matrix Factorization(IPMF)融入邻居信息的概率矩阵分解算法,并且提出了parallel-IPMF (p-IPMF)算法来解决融入邻居信息后计算复杂度高和难以并行化等问题。 在MapReduce并行计算框架下将p-IPMF算法加以实现,并在真实数据集上进行验证。实验结果表明,所提算法能有效提高推荐质量并缩短计算时间。     

LU分解递归算法的研究

将递归方法引入稠密线性代数的计算，能产生自动的矩阵分块，使算法适合于当今分级存储高性能计算机的结构，提高运算速度。文中对解线性代数方程组的LU分解递归算法进行了研究，给出了算法的详细推导过程。     

LU分解递归算法的实现

§1.引言 以LU分解, Cholesky分解等为代表的线性代数问题的数值计算在现代科学研究和工程技术中得到广泛应用.随着计算机技术的发展,实现这些线性代数数值计算的计算机算法和软件也在不断发展.目前,具有多级存储结构的高性能RISC计算机已占据了数值计算领域的主导地位. RSIC处理器的运算速度非常快,它们与存储器之间的速度差距很大.计算机的性能能不能充分发挥,多级存储结构与高缓能否得到有效利用成为关键.为此,现行的     

基于异步多速率观测的噪声去相关融合算法

对于异步多传感器观测数据,基于先同步,再去相关的思想,提出了一种改进的左同步提升异步观测融合算法。采用左同步法避免了右同步过程中的系统状态矩阵求逆和可能出现的非因果问题;对同步后的系统基于Cholesky分解进行噪声去相关处理,理论上分析了去相关处理前后的算法计算量;用信息滤波器进行预测估计,简化了滤波增益的计算过程。仿真结果表明：改进算法能够在不减小跟踪精度的基础上减小计算量,增强了算法的实时性。     

Achieving numerical accuracy and high performance using recursive tile LU factorization with partial pivoting

The LU factorization is an important numerical algorithm for solving systems of linear equations in science and engineering and is a characteristic of many dense linear algebra computations. For example, it has become the de facto numerical algorithm implemented within the LINPACK benchmark to rank the most powerful supercomputers in the world, collected by the TOP500 website. Multicore processors continue to present challenges to the development of fast and robust numerical software due to the increasing levels of hardware parallelism and widening gap between core and memory speeds. In this context, the difficulty in developing new algorithms for the scientific community resides in the combination of two goals: achieving high performance while maintaining the accuracy of the numerical algorithm. This paper proposes a new approach for computing the LU factorization in parallel on multicore architectures, which not only improves the overall performance but also sustains the numerical quality of the standard LU factorization algorithm with partial pivoting. While the update of the trailing submatrix is computationally intensive and highly parallel, the inherently problematic portion of the LU factorization is the panel factorization due to its memory‐bound characteristic as well as the atomicity of selecting the appropriate pivots. Our approach uses a parallel fine‐grained recursive formulation of the panel factorization step and implements the update of the trailing submatrix with the tile algorithm. Based on conflict‐free partitioning of the data and lockless synchronization mechanisms, our implementation lets the overall computation flow naturally without contention. The dynamic runtime system called QUARK is then able to schedule tasks with heterogeneous granularities and to transparently introduce algorithmic lookahead. The performance results of our implementation are competitive compared to the currently available software packages and libraries. For example, it is up to 40% faster when compared to the equivalent Intel MKL routine and up to threefold faster than LAPACK with multithreaded Intel MKL BLAS. Copyright © 2013 John Wiley & Sons, Ltd.     

A Toeplitz algorithm for polynomial J-spectral factorization

A block Toeplitz algorithm is proposed to perform the J-spectral factorization of a para-Hermitian polynomial matrix. The input matrix can be singular or indefinite, and it can have zeros along the imaginary axis. The key assumption is that the finite zeros of the input polynomial matrix are given as input data. The algorithm is based on numerically reliable operations only, namely computation of the null-spaces of related block Toeplitz matrices, polynomial matrix factor extraction and linear polynomial matrix equations solving.     

A preconditioner for solving large-scale variational inequality problems by a semismooth inexact approach

The numerical solution of a large-scale variational inequality problem can be obtained using the generalization of an inexact Newton method applied to a semismooth nonlinear system. This approach requires a sparse and large linear system to be solved at each step. In this work we obtain an approximate solution of this system by the LSQR algorithm of Paige and Saunders combined with a convenient preconditioner that is a variant of the incomplete LU–factorization. Since the computation of the factorization of the preconditioning matrix can be very expensive and memory consuming, we propose a preconditioner that admits block-factorization. Thus the direct factorization is only applied to submatrices of smaller sizes. Numerical experiments on a set of test-problems arising from the literature show the effectiveness of this approach.