LU分解递归算法的实现

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

基于超节点LDL分解的大规模结构计算

采用列压缩稀疏(Compressed Sparse Column,CSC)矩阵存储策略对矩阵LDL分解前进行填充元优化排序;基于消去树进行LDL符号分解,使之独立于数值分解,避免多余的内存消耗,减少不必要的数值运算.利用矩阵非零元的分布特性分析并实现超节点LDL分解算法,将稀疏矩阵的分解运算变为一系列稠密矩阵运算,并使用优化的BLAS函数库加速分解.测试表明:算法在成倍地提高计算速度的同时进一步降低内存消耗,适用于大规模的结构计算.     

面向SW26010-Pro的1、2级BLAS函数众核并行优化技术

BLAS (basic linear algebra subprograms)是高性能扩展数学库的一个重要模块,广泛应用于科学与工程计算领域. BLAS 1级提供向量-向量运算, BLAS 2级提供矩阵-向量运算.针对国产SW26010-Pro众核处理器设计并实现了高性能BLAS 1、2级函数.基于RMA通信机制设计了从核归约策略,提升了BLAS 1、2级若干函数的归约效率.针对TRSV、TPSV等存在数据依赖关系的函数,提出了一套高效并行算法,该算法通过点对点同步维持数据依赖关系,设计了适用于三角矩阵的高效任务映射机制,有效减少了从核点对点同步的次数,提高了函数的执行效率.通过自适应优化、向量压缩、数据复用等技术,进一步提升了BLAS 1、2级函数的访存带宽利用率.实验结果显示, BLAS 1级函数的访存带宽利用率最高可达95%,平均可达90%以上, BLAS 2级函数的访存带宽利用率最高可达98%,平均可达80%以上.与广泛使用的开源数学库GotoBLAS相比, BLAS 1、2级函数分别取得了平均18.78倍和25.96倍的加速效果. LU分解、QR分解以及对称特征值问题通过调用...     

基于申威1621处理器的BLAS一级函数优化

BLAS (Basic Linear Algebra Subprograms)是一个基本线性代数操作的数学函数标准, 该库函数分为三个级别, 每个级别提供了向量与向量(1级)、向量与矩阵(2级)、向量与向量(三级)之间的基本运算. 本文研究了在申威1621处理器上BLAS一级函数的优化方案, 以函数AXPY为例, 充分利用平台的架构特点对其进行性能调优,设计了自动的线程分配方案. 实验结果显示优化过后的BLAS一级函数AXPY相对于GotoBLAS参考实现版本的单核和多核加速比分别高达4.36和9.50, 对于每种优化方式均得到了一定的性能提升.     

在PVM应用程序中调用ScaLAPACK库函数方法

１．引言ＳｃａＬＡＰＡＣＫ是村卫ｆａｂｌｅＬｉｎｅａｒＡｌｇｅｂｒａＭａｇｅ的缩写，是为在基于消息传递的ＭＩＭＤ并行计算机系统上解数值线性代数问题，并由美国橡树岭国家实验室和田纳西大学等联合开发．它支持对（）线性代数方程组问题（）最小二乘问题（３特征值问题（４）奇异值分解等问题的求解（参见文献［１—３１）．这些问题由于在科学与工程计算中经常出现，它们的高效求解成了应用程序获得高性能的关键．随着计算机的发展，相继开发了ＬｉｎＰａｃｋ；ＥｉｓＰａｃｋ；ＬＡＰＡＣＫ和ＳｃａＬＡＰＡＣＫ等数值软件包，利…     

国产SW26010-Pro处理器上3级BLAS函数众核并行优化

BLAS (basic linear algebra subprograms)是最基本、最重要的底层数学库之一.在一个标准的BLAS库中,BLAS 3级函数涵盖的矩阵-矩阵运算尤为重要,在许多大规模科学与工程计算应用中被广泛调用.另外, BLAS 3级属于计算密集型函数,对充分发挥处理器的计算性能有至关重要的作用.针对国产SW26010-Pro处理器研究BLAS 3级函数的众核并行优化技术.具体而言,根据SW26010-Pro的存储层次结构,设计多级分块算法,挖掘矩阵运算的并行性.在此基础上,基于远程内存访问(remote memory access, RMA)机制设计数据共享策略,提高从核间的数据传输效率.进一步地,采用三缓冲、参数调优等方法对算法进行全面优化,隐藏直接内存访问(direct memory access, DMA)访存开销和RMA通信开销.此外,利用SW26010-Pro的两条硬件流水线和若干向量化计算/访存指令,还对BLAS 3级函数的矩阵-矩阵乘法、矩阵方程组求解、矩阵转置操作等若干运算进行手工汇编优化,提高了函数的浮点计算效率.实验结果显示,所提出的并行优化技术...     

并行代数多重网格算法:大规模计算应用现状与挑战

代数多重网格(AMG)是求解偏微分方程离散线性代数方程组最有效的算法之一,广泛应用于科学与工程计算领域实际问题的大规模数值模拟.随着超级计算机性能不断提升,实际数值模拟的计算规模和并行规模越来越大,同时,实际问题应用特征和计算机体系结构特征越来越复杂,AMG面临并行可扩展、算法可扩展和浮点性能优化的严峻挑战.本文结合大规模计算的发展趋势,特别是面向即将到来的百亿亿次(E级)计算,分析AMG算法在这三个方面的挑战,总结研究现状与进展,展望未来研究重点.     

基于申威1621的通用矩阵向量乘法的性能分析与优化

通用矩阵向量乘法（GEMV）函数是整个二级基础线性代数子程序（BLAS）函数库的构建基础,BLAS作为关键基础计算软件之一,目前在申威处理器上却没有一个高性能实现的版本。针对上述问题,为充分发挥申威1621平台的高性能BLAS库计算优势,提出一种基于申威1621的通用矩阵向量乘法的性能分析与优化方法。首先对GEMV函数进行计算重排序、循环分块的改进;然后采取单指令多数据流（SIMD）以及指令重排的优化方式;最后对内存分配方式进行择优选择。测试结果表明,GEMV函数平均性能达到GotoBLAS版的2.17倍。在使用堆栈分配内存空间或增加对y向量步长的判断分支两种方案后,相较于GotoBLAS,小规模矩阵的平均性能由2.265倍提升至2.875倍。为提高大规模矩阵的性能,以及发挥申威1621多核处理器并行机制,在开启4线程后,平均性能达到单核的3.57倍。因此,优化后的GEMV函数在申威平台上较好的体现了并行效果。     

BLAS 库在多核处理器上的性能测试与分析

BLAS 库是高性能计算中最基本的数学库,它的性能对超级计算机的性能有着极大的影响.而且随着CPU多核化的发展,BLAS 的多核并行性能已经变得比与体系结构相关的单核性能更加重要.实验以流行于高性能计算的Xeon、Opteron 系列多核X86 处理器为例,全面测试了GotoBLAS、Atlas、MKL 和ACML 四种主流的BLAS 库的所有1,2,3 级函数,并覆盖了不同计算规模和多核并行方面的测试.通过测试结果,分析源代码、BLAS 库资料和论文的方式,分析BLAS 有效的优化和并行方法,以及它们所适合的平台.为BLAS 的优化、使用,甚至高性能处理器的发展上提供有益的建议.实验结果表明,比起一个逻辑处理强大但是复杂的处理器,一个cache 更大、性能更好,内存带宽更宽、延迟更小,主频更高的处理器往往能在高性能计算中取得更好的性能.同时,X86 平台上的状况对其他体系结构也有巨大的借鉴意义.     

一种无矩阵求逆的最优滤波计算方法

本文回顾了在改善卡尔曼滤波数值稳定性，提高计算效率等数值计算方面的主要研究与发展，包括平方根协方差、U—D分解、奇异值分解(SVD)等计算方法。这些算法都存在不同程度地通过牺牲计算效率换取数值稳定性的不足。本文提出了一种无矩阵求逆的最优卡尔曼滤波计算方法，该算法数值稳定性强，且计算量也比较小。     

Cholesky分解递归算法与改进

递归算法是计算稠密线性代数的一种新的有效方法。递归产生自动、变化的矩阵分块,能充分发挥当今分级存储高性能计算机的效率。对Cholesky分解递归算法进行了研究,给出了算法的详细推导过程,用具有递归功能的Fortran90实现了算法,并通过矩阵元素顺序重排的方法,进一步提高了递归算法的运算速度。研究产生的算法比目前常用的分块算法快15％－25％。     

An algorithm for RLS identification parameters that vary quicklywith time

An alternative to the standard recursive least-squares (RLS) algorithm for fixed-order systems with exponential data weighting is presented. The approach uses Givens orthogonal transformations to update the Cholesky factor of the information matrix without ever needing to form it. The resulting algorithm gives higher-precision control and is less sensitive to ill-conditioning when compared to other reported approaches. It is demonstrated by an example that ill-conditioned problems with parameters that vary quickly can be modified to stabilize erratic parameter fluctuations     

Pivot tightening for direct methods for solving symmetric positive definite systems of linear interval equations

The paper considers systems of linear interval equations, i.e., linear systems where the coefficients of the matrix and the right hand side vary between given bounds. We focus on symmetric matrices and consider direct methods for the enclosure of the solution set of such a system. One of these methods is the interval Cholesky method, which is obtained from the ordinary Cholesky decomposition by replacing the real numbers by the related intervals and the real operations by the respective interval operations. We present a method by which the diagonal entries of the interval Cholesky factor can be tightened for positive definite interval matrices, such that a breakdown of the algorithm can be prevented. In the case of positive definite symmetric Toeplitz matrices, a further tightening of the diagonal entries and also of other entries of the Cholesky factor is possible. Finally, we numerically compare the interval Cholesky method with interval variants of two methods which exploit the Toeplitz structure with respect to the computing time and the quality of the enclosure of the solution set.     

Backstepping design with local optimality matching

In nonlinear H^∞-optimal control design for strict-feedback nonlinear systems, our objective is to construct globally stabilizing control laws to match the optimal control law up to any desired order, and to be inverse optimal with respect to some computable cost functional. Our recursive construction of a cost functional and the corresponding solution to the Hamilton-Jacobi-Isaacs equation employs a new concept of nonlinear Cholesky factorization. When the value function for the system has a nonlinear Cholesky factorization, we show that the backstepping design procedure can be tuned to yield the optimal control law     

An effective method for simulating conditional Gaussian processes in the problems of geological modeling

In problems of geological modeling, methods are often employed for generating the implementations of stationary Gaussian fields under preset values in the wells. Basic simulation algorithms for Gaussian processes are the correction of unconditional Gaussian fields by taking into account the residuals in the wells, sequential Gaussian simulation, and the Cholesky decomposition of the covariance matrix. Neither of these methods, however, is free from drawbacks. Implementations by the first two techniques have an incorrect correlation function, which can lead eventually to incorrect values of hydrocarbon flow rates. The Cholesky decomposition, despite its high accuracy, is not applicable to geological modeling problems due to the high computational complexity of the algorithm. In this paper, we have developed a method based on the generation of the Fourier transform of Gaussian random process implementations. It is shown in this work that in Fourier space the covariance of two harmonics of a random process can be represented as a product of functions of these harmonics. In this case, the Cholesky decomposition algorithm can be significantly simplified. A distinctive feature of the algorithm is its accuracy and relatively low computational complexity.     

差分模型参数递推估计的Householder变换法

本文提出了利用Householder变换进行差分模型参数递推估计的新方法.并由该方法导 出了新的递推最小二乘法、递推增广矩阵法、递推广义最小二乘法、递推极大似然法. 文中分单变量、多变量两种情况重点讨论了新递推最小二乘法及其与传统递推最小二乘 法的比较,并给出了计算实例.     

递归算法的参数设置

递归算法参数的设置是至关重要的,基于递归算法的特征,提出一种通用的递归算法的设计模式．在此基础上进一步讨论参数的设置的方式及其效果,为研究递归算法提供有效的解决方案,具有很强的实用性,并结合经典实例给以说明。     

基于改进极限学习机算法的行为识别

重点研究了极限学习机ELM对行为识别检测的效果。针对在线学习和行为分类上存在计算复杂性和时间消耗大的问题,提出了一种新的行为识别学习算法(ELM-Cholesky)。该算法首先引入了基于Cholesky分解求ELM的方法,接着依据在线学习期间核函数矩阵的更新特点,将分块矩阵Cholesky分解算法用于ELM的在线求解,使三角因子矩阵实现在线更新,从而得出一种新的ELM-Cholesky在线学习算法。新算法充分利用了历史训练数据,降低了计算的复杂性,提高了行为识别的准确率。最后,在基准数据库上采用该算法进行了大量实验,实验结果表明了这种在线学习算法的有效性。     

递归算法的参数设置

递归算法参数的设置是至关重要的,基于递归算法的特征,提出一种通用的递归算法的设计模式,在此基础上进一步讨论参数的设置的方式及其效果,为研究递归算法提供有效的解决方案,具有很强的实用性,并结合经典实例给以说明。     

基于任务的Cholesky分解多核并行化研究

针对Cholesky分解算法采用OpenMP并行程序设计时的并行性开销增大和线程负载不平衡的问题,利用并行性能分析工具对串行程序进行热点分析,提出了一种基于任务的Cholesky分解多核并行算法。该算法将大循环问题划分成各个相互独立的小任务,并运用任务窃取技术和动态负载均衡算法使多个任务能够并行完成。采用ParallelAmplifier对并行程序进行调试和优化,实验结果表明,其性能得到较大幅度的提升。