大规模结构化二次规划并行算法

在内点算法(IPM)框架基础上,分析具有分块带边结构系数矩阵与箭形结构二次项的二次规划(QP)问题,导出其既约与最简既约修正方程.对既约修正方程系数矩阵进行置换,使其具有箭形分块结构,并结合该结构与解耦技术给出修正方程的并行求解算法,设计QP问题的并行IPM结构.在集群环境下的数值实验结果表明,该算法具有较好的加速比和...     

无约束最优化问题的BFGS松弛异步并行算法

为解决大规模非线性最优化问题的串行求解速度慢的问题,提出应用松弛异步并行算法求解无约束最优化问题。根据无约束最优化问题的BFGS串行算法,在PC机群环境下将其并行化。利用CHOLESKY方法分解系数为对称正定矩阵的线性方程组,运用无序松弛异步并行方法求解解向量和Wolfe-Powell非线性搜索步长,并行求解BFGS修正公式,构建BFGS松弛异步并行算法,并对算法的时间复杂性、加速比进行分析。在PC机群的实验结果表明,该算法提高了无约束最优化问题的求解速度且负载均衡,算法具有线性加速比。     

一种求解线性方程组的SOR并行算法

逐次松弛迭代算法(SOR)是求解线性方程组的一种常用迭代算法,当系数矩阵正定时,它具有较快的收敛速度。但是,由于每个迭代步内存在数据相关,它难以实现并行计算。目前的SOR并行算法采用数据分解的方法,但由于该法并行区域过小,同步通讯代价大,并行效率低。本文提出了SOR的一种新型并行算法,该算法与传统SOR方法等价,具有相同的收敛性和迭代结果。该并行算法通过矩阵分块增大了可并行计算的区域,并引入流水线技术,利用各处理器间通讯与计算时间的重叠,获得较理想的并行加速效率。通过多核微机以及小规模集群上的数值实验证明,本文提出的SOR并行算法在求解大型稠密线性方程组时具有较好的并行效率。     

利用并行方法解AX+XB=C型线性矩阵方程

提出了一种新的递推算法用于求解AX+XB=C型线性矩阵方程,这种算法可以用脉 动阵列结构并行实现,该算法和结构还可求解其它几种类似的线性矩阵方程,特殊情况下求解 方程的阵列结构可进一步简化.仿真结果表明,这种并行方法有较高的加速比及效率.     

对称矩阵三对角化的有效并行块算法设计

在矩阵数值计算中,块算法通常比非块算法更有效,但这也增加了并行算法设计和实现的难度．在广义稠密对称矩阵特征问题并行求解器中,并行块算法的构造可应用到正定对称矩阵的Choleski分解、对称矩阵的三对角化和回代转化(back-transiation)操作中．本文将并行块算法的讨论集中在具有代表性的对称矩阵三对角化上,给出在非块存储方式下对称矩阵三对角化的并行块算法设计方法．分析块算法大小同矩阵规模和处理器数量的关系．在深腾6800上的试验表明,我们的算法具有很好的性能,并得到了比ScaLAPACK更高的性能．     

带状线性方程组的并行交替方向算法

提出了分布式存储环境下求解带状线性方程组的并行交替方向迭代算法。充分利用系数矩阵的结构特点,给出了在系数矩阵分别为Hermite正定矩阵和M-矩阵时算法的充分条件,并针对采用的分裂方式,讨论了参数的收敛范围,最后在HPrx2600集群系统上进行了数值计算,结果表明实算与理论相一致,算法简便可行且具有良好的并行性。     

解不定信赖域子问题的Heun三阶算法

针对信赖域子问题,当Hessian矩阵不正定时,利用Bunch-Parlett法对矩阵进行修正,构造了对称正定的矩阵,将不定子问题转化为正定子问题,用新的折线来逼近最优解曲线,给出了求解的Heun三阶算法。通过对Heun三阶折线路径性质的分析,理论上证明了算法的适定性。利用两个测试函数进行了数值实验,结果表明该算法有效。     

Transputer上正定方程组并行求解算法

本文分析了影响Transputer并行处理效率的因素,给出了正定矩阵在Transputer上并行分解和正定方程组并行求解的算法。在T800-20上分别用OC-CAM语言和并行FORTRAN语言编程实现,给出了测试结果并进行分析比较。     

基于GPU的并行Cholesky分解及其应用

在OpenCL并行计算框架的clMAGMA库中,Cholesky分解算法采用大尺寸分块并行方法,不能充分利用GPU的高速局部存储器,且在计算过程中存在多次GPU-CPU间的数据传递。为此,提出采用小尺寸分块并行方法,充分利用GPU中的高速局部存储器,使矩阵子块的逆矩阵得到复用,完成对称正定矩阵的高效Cholesky分解,并且其能够应用于三维视觉光束平差问题中的大型正定矩阵的分解。实验结果表明,该方法的Cholesky分解速度比clMAGMA提升50%以上,针对光束平差问题,比Ceres Solver中使用的Eigen库速度提升约38倍。     

求解带状线性方程组的一种并行算法

提出了一种在MIMD分布式存储环境下求解带状线性方程组的交替方向迭代并行算法。利用系数矩阵的结构特点分裂矩阵,使整个计算过程只在相邻处理机间通信两次。给出了系数矩阵分别为Hermite正定矩阵和M-矩阵时算法收敛的充分条件。最后,在HP rx2600集群系统上进行的数值计算表明,该算法与多分裂方法相比具有较高的加速比和并行效率。     

A bound to the condition number of canonical rank-two corrections and applications to the variable metric method

Properties of rank-two symmetric corrections to a positive definite matrix are considered in the context of canonical forms. The conditions for maintenance of positive definitess are given and a new bound to the condition number of the corrected matrix is obtained. Some applications to the variable metric method are presented and the performance of the new bound is compare numerically with that of a bound proposed by Brodlie, Gourlay and Greenstadt. Part of this work was done while the author was visiting researcher at the Economic System Engeneering Department of the Stanford University and was financially supported by CNR.     

基于高斯混合模型的分量对称正定矩阵模型

高斯混合模型(GMM)可以利用多个高斯分量捕捉图像集的变化信息,是一种良好的图像集描述方法.结合分量对称正定矩阵表示方法(CSPD),文中提出基于GMM的CSPD模型(G-CSPD).模型将图像集分成大小相同的子图像集,使用GMM描述每个子图像集,最终得到一个G-CSPD矩阵,该矩阵中元素描述子图像集之间相似性.在3个图像集上的实验表明,G-CSPD是具有鉴别性的图像集描述方法.     

A finite element method for plane strain deformations of incompressible solids

A finite element method for incompressible deformation is formulated from the virtual work equation based on deviatoric quantities. Particular emphasis is given to nonlinear material behavior. The incompressibility constraint is imposed on the admissible displacement field by direct elimination of nodal displacements. The resulting stiffness matrix is symmetric and positive definite. Once a convergent solution for the displacement is obtained, the hydrostatic stress is determined from the principle of virtual work. A variety of illustrative examples are presented. The efficiency, economy and limitations of the method are discussed.     

Algebraic multigrid methods based on element preconditioning

This paper presents a new algebraic multigrid (AMG) solution strategy for large linear systems with a sparse matrix arising from a finite element discretization of some self-adjoint, second order, scalar, elliptic partial differential equation. The AMG solver is based on Ruge/Stübens method. Ruge/Stübens algorithm is robust for M-matrices, but unfortunately the “region of robustness“ between symmetric positive definite M-matrices and general symmetric positive definite matrices is very fuzzy.

For this reason the so-called element preconditioning technique is introduced in this paper. This technique aims at the construction of an M-matrix that is spectrally equivalent to the original stiffness matrix. This is done by solving small restricted optimization problems. AMG applied to the spectrally equivalent M-matrix instead of the original stiffness matrix is then used as a preconditioner in the conjugate gradient method for solving the original problem.

The numerical experiments show the efficiency and the robustness of the new preconditioning method for a wide class of problems including problems with anisotropic elements.     

在镇定理论中控制系统与具有滞后的控制系统的等价性

本文由勒卡提矩阵方程与勒卡提矩阵微分方程的正定对称解构造了正定二次型函数,给出了在镇定理论中定常及时变线性控制系统与具有滞后的定常及时变线性控制系统的等价性。同时给出了滞后界限的估计公式。     

Preconditioned conjugate residual methods for the solution of spectral equations

Conjugate residual methods for the solution of spectral equations are described. An inexact finite-difference operator is introduced as a preconditioner in the iterative procedures. Application of these techniques is limited to problems for which the symmetric part of the coefficient matrix is positive definite. (The symmetric part of the coefficient matrix A is defined by (A + A^T)/2.) Although the spectral equation is a very ill-conditioned and full matrix problem, the computational effort of the present iterative methods for solving such a system is comparable to that for the sparse matrix equations obtained from the application of either finite-difference or finite-element methods to the same problems. Numerical experiments are shown for a self-adjoint elliptic partial differential equation with Dirichlet boundary conditions, and comparison with other solution procedures for spectral equations is presented.     

多组多滞后中立型线性时变关联控制系统的结构与关联镇定

建立了具有扰动参数的多组多滞后中立型线性时变关联控制系统的结构与关联镇定新概念，采用李雅普诺夫函数鲁棒镇定等价法，给出了由无滞后无扰动参数线性时变控制系统的关联镇定，蕴含了具有扰动结构参数的多组多不足后中立型线性时变关联控制系统的关联镇定的充分性判据，同时给出了扰动参数与滞后项界限的估计公式。     

离散时间代数Riccati方程解矩阵的特征值分析

针对离散时间代数Riccati方程DTARE的唯一对称正定解X的特征值,通过矩阵的恒等变形,给出了一种新的分析方法.最后获得解X的极值特征值的上界和下界,以及解X的特征值的和———迹的一个下界.     

基于GPU-CUDA的共轭斜量法实现及性能对比

偏微分方程数值解法(包括有限差分法、有限元法)以及大量的数学物理方程数值解法最终都会演变成求解大型线性方程组。因此,探讨快速、稳定、精确的大型线性方程组解法一直是数值计算领域不断深入研究的课题且具有特别重要的意义。在迭代法中,共轭斜量法(又称共轭梯度法)被公认为最好的方法之一。但是,该方法最大缺点是仅适用于线性方程组系数矩阵为对称正定矩阵的情况,而且常规的CPU算法实现非常耗时。为此,通过将线性方程组系数矩阵作转换成对称矩阵后实施基于GPU-CUDA的快速共轭斜量法来解决一般性大型线性方程组的求解问题。试验结果表明:在求解效率方面,基于GPU-CUDA的共轭斜量法运行效率高,当线性方程组阶数超过3000时,其加速比将超过14;在解的精确性与求解过程的稳定性方面,与高斯列主元消去法相当。基于GPU-CUDA的快速共轭斜量法是求解一般性大型线性方程组快速而非常有效的方法。