特征值问题的Davidson型方法及其实现技术

Davidson方法及其变型是一类非常流行的求解大规模特征值问题的方法．本文将从理论和实现两个角度,综述了Davidson型方法,包括Jacobi-Davidson方法的基本思想和发展概况．     

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

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

求解大型Stein方程的块Krylov子空间方法

本文研究利用块Krylov子空间方法对大型Stein方程降阶求解,分别基于块Arnoldi方法与非对称块Lanczos方法,提出了块Arnoldi Stein方法与非对称块Lanczos Stein方法.数值实验表明提出的方法有效.     

一种求解复Hermite矩阵特征值的方法

介绍几种求解矩阵特征值和特征向量的经典算法及各自优缺点,通过理论推导,提出了一种性能稳健的方法,可以求解信号处理中常见的复Hermite阵.将对复Hermite矩阵求特征值和特征向量的问题转化为求解实对称阵的特征值和特征向量,而实对称阵的求解采用一种改进的三对角Householder法.最后把结果与Matlab仿真结果比较,可以看出该方法有很高的精确度.     

求实对称矩阵部分特征值的并行算法

提出了并行求解实对称稠密矩阵部分特征值的反幂法的预处理方法.该方法基于带状矩阵特征问题反幂法的信息传递复杂度低的特点,采用Householder变换并行算法约化大型实对称稠密矩阵为一定带宽的带状矩阵,针对带状矩阵用反幂法求解矩阵的在某一点的近似特征值;其中针对反幂法迭代中遇到的线性方程组,采用文献中的并行预处理共轭梯度算法求解.最后在Lenovo深腾1800集群上进行数值实验,并与预处理前反幂法的计算结果进行了比较,实验结果表明,经过预处理后的并行性远高于直接采用反幂法的并行性.     

求解对称区间矩阵标准特征值的进化策略新算法

针对实对称区间矩阵的特征值问题,将区间不确定量看成是围绕区间中点的一种摄动,提出了一种基于区间扩张的对称区间矩阵特征值问题求解的进化策略算法。将区间矩阵中点作为平衡点,区间不确定量作为相应的扰动量,根据摄动公式求出区间矩阵的最大特征值和最小特征值,从而获得区间矩阵特征值问题的解。算例显示了该算法的有效性,其主要特点是收敛速度快、求解区间精度高。     

求解对称非线性矩阵特征值问题的一个三阶收敛的算法

考虑对称矩阵A(λ)∈R~(n×n),它的元素是λ的解析函数.求λ∈R,向量x≠0,使得求解(1.1)称为求解对称非线性矩阵特征值问题. 对于一般非线性矩阵特征值问题已经有了很多有效的方法.本文的目的是如何利用矩阵的对称性给出一个运算量与通常使用的二阶收敛方法的运算量相当的三阶收敛算法.     

SMP集群系统上矩阵特征问题并行求解器的有效算法

对称矩阵三对角化和三对角对称矩阵的特征值求解是稠密对称矩阵特征问题并行求解器的关键步.针对SMP集群系统的多级体系结构,基于Householder变换的矩阵三对角化和三对角矩阵特征值问题的分而治之算法,给出了它们的MPI+OpenMP混合并行算法.算法研究集中在SMP集群系统环境下的负载平衡、通信开销和性能评价.混合并行算法的设计结合了粗粒度线程并行模式和任务共享的动态调用方法,改善了MPI算法中的负载平衡问题、降低了通信开销.在深腾6800上的实验表明,基于混合并行算法的求解器比纯MPI版本的求解器具有更好的性能和可扩展性.     

一类舒尔补矩阵的条件数分析

研究了一类线性方程组系数矩阵的红黑排序方法,以及由红黑排序矩阵导出的舒尔补矩阵的条件数.利用三对角矩阵的特征值分析方法推导了一类块三对角矩阵的特征值和条件数,构造了三对角矩阵和块三对角矩阵的红黑排序排列矩阵,利用矩阵相似变换推导出红黑排序矩阵中的舒尔补的特征值和条件数表达式.理论分析和数值试验结果均表明这类舒尔补矩阵具有更好的性质.     

基于混沌映射的自适应图像加密算法

为了提高图像加密算法的鲁棒性,提出了一种新的自适应图像加密算法。首先,把任意大小的灰度或彩色图像分成2×2子块;然后,用左上角子块的像素灰度值和Chebyshev混沌映射构造与右上角子块等大的矩阵,用该矩阵对右上角子块进行像素灰度值替换;最后,按顺时针对每个子块进行加密,直到左上角子块加密完毕。该算法不依赖于图像的大小,而且适用于灰度图像和彩色图像,因而有很强的鲁棒性。同时灰度值扩散机制的引入使得该算法具有良好的扩散性和扰乱性。     

Implementation of parallel three-point block codes for solving large systems of ordinary differential equations

The three-point fully implicit block methods are developed for solving large systems of ordinary differential equations using variable step size on a parallel shared memory computer. The methods calculate the numerical solution at three points simultaneously and are suitable for parallelization across the method. The methods are in a simple form as Adams Moulton method with the specific aim of gaining efficiency. For large problems, the parallel implementation produced a good speed-up with respect to the sequential timing and hence better efficiency for the methods developed.     

Computing subdominant unstable modes of turbulent plasma with a parallel Jacobi–Davidson eigensolver

In the numerical solution of large‐scale eigenvalue problems, Davidson‐type methods are an increasingly popular alternative to Krylov eigensolvers. The main motivation is to avoid the expensive factorizations that are often needed by Krylov solvers when the problem is generalized or interior eigenvalues are desired. In Davidson‐type methods, the factorization is replaced by iterative linear solvers that can be accelerated by a smart preconditioner. Jacobi–Davidson is one of the most effective variants. However, parallel implementations of this method are not widely available, particularly for non‐symmetric problems. We present a parallel implementation that has been included in SLEPc, the Scalable Library for Eigenvalue Problem Computations, and test it in the context of a highly scalable plasma turbulence simulation code. We analyze its parallel efficiency and compare it with a Krylov–Schur eigensolver. Copyright © 2011 John Wiley & Sons, Ltd.     

Efficiently preconditioned inexact Newton methods for large symmetric eigenvalue problems

In this paper, we propose an efficiently preconditioned Newton method for the computation of the leftmost eigenpairs of large and sparse symmetric positive definite matrices. A sequence of preconditioners based on the BFGS update formula is proposed, for the preconditioned conjugate gradient solution of the linearized Newton system to solve Au=q(u) u, q(u) being the Rayleigh quotient. We give theoretical evidence that the sequence of preconditioned Jacobians remains close to the identity matrix if the initial preconditioned Jacobian is so. Numerical results onto matrices arising from various realistic problems with size up to one million unknowns account for the efficiency of the proposed algorithm which reveals competitive with the Jacobi–Davidson method on all the test problems.     

基于非线性模型的混合分形图像编码方法

提出一个非线性模型,将典型分形块编码的8种对称变换推广到64种,并通过定义特征值的方法对域块选择以及几何变换方式选择进行加速.基于区块邻域匹配的快速匹配策略,对匹配效果不佳的区块进行块截取编码,对平滑块采用均值和三级四叉树编码,使得综合压缩性能良好,编码速度有较大提高.     

Parallel implementations of the trace minimization scheme TraceMIN for the sparse symmetric eigenvalue problem

Eigenvalue problems arise in many computational science and engineering applications: in structural mechanics, nanoelectronics, and Google’s PageRank link analysis, for example. Often, the large size of these eigenvalue problems requires the development of eigensolvers that scale well on parallel computing platforms. In this paper, we compare the effectiveness and robustness of our eigensolver for the symmetric generalized eigenvalue problem, the trace minimization scheme TraceMIN–developed in the early 1980s–against today’s well-known sparse eigensolvers including: the LOBPCG and block Krylov–Schur implementations in Trilinos; ARPACK; and several methods in the PRIMME package such as the Jacobi–Davidson one. In addition, we demonstrate the parallel scalability of two variants of TraceMIN on multicore nodes as well as on large clusters of such nodes. Our results show that TraceMIN is more robust and has higher parallel scalability than the above-mentioned competing eigensolvers.     

模拟集成电路二维Stack生成及模块合并算法

在模拟集成电路设计中,关于X轴和y轴同时对称的Stack,以及模块之间的合并,对于增加器件之间的匹配和控制寄生是至关重要的.描述了模拟集成电路二轴对称Stack生成算法和模块合并算法.通过对于对称欧拉图和对称欧拉路径的研究,得出了多项理论结果.在此基础上,提出了时间复杂度为O(n)的伪器件插入算法、对称欧拉路径构造算法和二轴对称Stack生成算法.生成的Stack,不但关于X轴和y轴对称,而且具有公共质心(commoncentroid)的结构.还描述了模块合并算法,给出了计算最大合并距离的公式.该算法本质上是独立于任何拓扑表示的.实验结果验证了算法的有效性.     

Solving delay differential equations by the five-point one-step block method using Neville's interpolation

A five-point one-step block method based on the Newton backward divided difference formulae for the solution of first-order delay differential equations is derived. The proposed block method will approximate the solutions of initial value problems at five points simultaneously using variable step size. The approximation of the delay term is calculated using Neville's interpolation. The block method will be formulated in terms of linear multistep method, but the method is equivalent to one-step method. The order of the block method will be discussed. The P-stability and Q-stability regions of the block method using Neville's interpolation for the delay term are presented for a fixed step size. Numerical results are given to show the efficiency of the proposed method and compared with the existing method.     

Modified alternating direction-implicit iteration method for linear systems from the incompressible Navier–Stokes equations

In order to solve the large sparse systems of linear equations arising from numerical solutions of two-dimensional steady incompressible viscous flow problems in primitive variable formulation, Ran and Yuan [On modified block SSOR iteration methods for linear systems from steady incompressible viscous flow problems, Appl. Math. Comput. 217 (2010), pp. 3050–3068] presented the block symmetric successive over-relaxation (BSSOR) and the modified BSSOR iteration methods based on the special structures of the coefficient matrices. In this study, we present the modified alternating direction-implicit (MADI) iteration method for solving the linear systems. Under suitable conditions, we establish convergence theorems for the MADI iteration method. In addition, the optimal parameter involved in the MADI iteration method is estimated in detail. Numerical experiments show that the MADI iteration method is a feasible and effective iterative solver.     

分块带边结构线性规划并行算法

基于内点算法((Interior Point Method,IPM)框架,导出具有分块带边结构系数矩阵的线性规划(Linear Programming, I_P)问题的简化和最简修正方程,并证明最简修正方程的对角分块具有正定性。结合正定矩阵的Cholcsky分解和解藕技术设计了修正方程的并行求解方法,给出了LP的并行内点算法结构。集群环境下的数值实验表明,所提算法具有很好的加速比和可扩展性,适合求解大规模结构化工尹问题。