一种用于并行电路仿真器的静态负载平衡算法

模拟电路的仿真问题可以最终归结为对线性代数方程组的求解。利用分块化方法可以降低求解过程中雅可比矩阵的维数,从而有效地降低求解时间。但是在矩阵进行划分之后,如何进行负载平衡,则是最终能否有效提高加速比的重要问题。提出了相应的静态负载平衡算法,并使用具体电路应用进行评价,试验证明该负载平衡算法对提高加速比有很好的效果。     

拟牛顿法在航空发动机特性仿真中的应用

航空发动机特性仿真中常用牛顿迭代法求解非线性方程组,牛顿法每一步迭代计算都需要计算Jacobi矩阵,这需要多次发动机气动热力过程计算.因此避免大量重复计算Jacobi矩阵可以减少发动机计算整机的气动热力计算次数,从而提高发动机特性计算的速度.文中采用基于Broyden原理的拟牛顿法求解发动机非线性方程组,这种方法可以直接求出第一步迭代后的Jacobi矩阵,从而大幅度提高计算速度.将拟牛顿法应用于某型涡喷和涡扇发动机特性计算,通过分析计算结果,证明了采用拟牛顿法可以提高发动机特性模拟的计算速度.     

轻量级迭代MDS矩阵的构造

随着具有最大分支数的扩散层在分组密码和hash函数中的应用,轻量级MDS矩阵的构造受到广泛关注.基于迭代构造是实现低成本MDS矩阵的一种有效方法.将低成本的矩阵通过迭代一定次数后成为MDS矩阵,通过实现该低成本的矩阵来实现MDS性质.但是这种方法需要以增加迭代次数个时钟周期等待时间为代价.本文通过减少矩阵迭代次数,从而降低矩阵实现的延迟,来构造更加轻量的迭代MDS矩阵.在迭代次数小于等于阶数时,本文给出了有限域F_{2^m}上4阶矩阵在不同迭代次数下,能够成为迭代MDS矩阵所含非零元个数的下界;进一步地,通过矩阵置换相似分类及MDS条件,不断减小可行空间,实现了非零元个数达到下界的迭代MDS矩阵的穷搜,从而找到在该迭代次数下异或数达到下界的4阶迭代MDS矩阵.     

基于Jacobi方法的线性离散时间系统的迭代学习控制

提出线性离散时间系统基于Jacobi方法的迭代学习控制问题.通过构建线性迭代学习控制问题与线性方程组之间的联系,将Jacobi方法引入到迭代学习控制中,并由此构建得到迭代学习控制律.借助于矩阵运算,证明这种学习律能使得系统的输出跟踪误差经有限次迭代后为零.数值例子说明了算法的可适用性.     

轻量级迭代MDS矩阵的构造

随着具有最大分支数的扩散层在分组密码和hash函数中的应用,轻量级MDS矩阵的构造受到广泛关注.基于迭代构造是实现低成本MDS矩阵的一种有效方法.将低成本的矩阵通过迭代一定次数后成为MDS矩阵,通过实现该低成本的矩阵来实现MDS性质.但是这种方法需要以增加迭代次数个时钟周期等待时间为代价.本文通过减少矩阵迭代次数,从而降低矩阵实现的延迟,来构造更加轻量的迭代MDS矩阵.在迭代次数小于等于阶数时,本文给出了有限域F_{2^m}上4阶矩阵在不同迭代次数下,能够成为迭代MDS矩阵所含非零元个数的下界;进一步地,通过矩阵置换相似分类及MDS条件,不断减小可行空间,实现了非零元个数达到下界的迭代MDS矩阵的穷搜,从而找到在该迭代次数下异或数达到下界的4阶迭代MDS矩阵.     

大规模数据集下谱聚类算法的求解

谱聚类算法是一种流行的数据聚类方法,该算法使用特征分解技术计算邻接矩阵的特征解,但是在大规模数据集的情况下,因储存和计算的问题而无法进行求解。基于线性代数中对称矩阵的性质,提出使用部接矩阵的每一列作为迭代算法的输入样本,通过迭代计算出部接矩阵的特征解。所提算法的空间复杂度只有O(m),时间复杂度也降低为O(pkm)。实验结果验证了算法的有效性。     

基于S域NMF的模拟电路故障特征提取新方法

针对提取的模拟电路故障特征向量信息不够充分的问题,提出了一种将S时频变换(ST,S-transform)和非负矩阵分解(NMF,non-negative matrix factorization)相结合的特征选取新方法.该方法先对模拟电路故障响应信号应用S时频变换建立时频图谱矩阵,再用NMF算法构造时频图谱数据集合的子空间基矩阵,有效降低了投影特征向量的维数,保留了足够多的故障隐含特征信息,进而提高模拟电路故障识别率.最后,在Sallen-Key高通滤波器电路中验证了文中方法的有效性.     

静态输出反馈控制的一种数值解法

在基于目标函数线性化的序列线性规划矩阵方法（SLPMM）的框架下,研究了线性时不变系统静态 输出反馈（SOF）H￥ 控制问题的数值解法,提出了一种改进的SLPMM 算法：通过求解一个LMI 特征值问题得到 SLPMM 算法的初始解,减少了运算的迭代次数,并同时给出了对H￥ 范数的一个初始估计．文中给出了基于该算法 的静态输出反馈H￥ 控制问题的详细求解步骤,最后用一个飞机纵向控制器的设计实例说明算法的有效性．     

H-矩阵方程组的预条件迭代法

针对系数矩阵A为H-矩阵的线性方程组Ax=b,引入了预条件矩阵I＋S_α~β,通过对系数矩阵施行初等行变换,提出了求解线性方程组Ax=b的一种新的预条件Gauss-Seidel方法.论文中首先证明了若A为H-矩阵,则（I＋S_α~β）A仍然是H-矩阵;其次,以定理的形式给出了新的预条件Gauss-Seidel方法收敛的充分条件,即给出了为保证新的预条件Gauss-Seidel方法收敛时参数所需满足的条件;然后从理论上证明了新的预条件Gauss-Seidel迭代方法较经典的Gauss-Seidel迭代方法收敛速度快,论文中提出的新的预条件Gauss-Seidel迭代方法推广了文[1-2]中提出的预条件方法;最后又通过数值算例说明了新的预条件Gauss-Seidel迭代方法的有效性.     

Lyapunov指数计算算法的设计与实现

为了定量分析混沌系统的动力学特性,论文研究了计算Lyapunov指数的Jacobi矩阵算法,并采用Matlab6.5软件平台设计了基于该算法的Lyapunov指数计算软件,算法程序简洁、可读性强、易于移植,GUI编程技术使人机交换能力增强,制作的Lyapunov指数工具箱能够求解非线性动力学系统的Lyapunov指数谱和分数维。最后,分析了迭代次数、计算步长、解法器和初值等因素对计算精度的影响。     

The SOR-k method for linear systems with p-cyclic matrices

Let the system matrix of a linear system be p-cyclic and consistently ordered. Under the assumption that the pth power of the associated Jacobi matrix has only non-positive eigenvalues, it is known that the optimal spectral radius of the SOR-k iteration matrix is strictly increasing as k increases from 2 to p. In this paper, we first show that the optimal parameter of the SOR-k method as a function of k is strictly increasing. The behaviour of the spectral radius of the SOR-k method (for fixed parameter) is then studied.     

Gradient based iterative solutions for general linear matrix equations

In this paper, we present a gradient based iterative algorithm for solving general linear matrix equations by extending the Jacobi iteration and by applying the hierarchical identification principle. Convergence analysis indicates that the iterative solutions always converge fast to the exact solutions for any initial values and small condition numbers of the associated matrices. Two numerical examples are provided to show that the proposed algorithm is effective.     

Reducing the number of multiplikations in iterative processes

Summary In any iteration scheme, such as v ^k=f(Qv ^k–1), where a fixed matrix multiplies a vector that depends on the iteration number, Winograd's method for computing inner products can be used in a straightforward manner to reduce the number of multiplications required at the cost of more additions. The key observation is that certain quantities required by Winograd's method have to be computed only at the first iteration. In the Jacobi method for solving systems of linear equations, f is linear. Gauss-Seidel iteration often converges faster than Jacobi iteration, but it cannot be put in the above form. A simple trick is necessary to apply Winograd's method in an efficient recursive manner. Our proposed method is better than the naive method when it is faster to add than to multiply. Versions of Jacobi and Gauss-Seidel iteration appropriate for optimization (as in Markov decision problems) are presented. The analysis specializes easily to the linear equation case.This research was supported by NRC grant A8565.     

Some basic results on M-matrices in connection with the Accelerated Overrelaxation (AOR) method

This paper extends some recent results by Varga concerning the theory of M-matrices, in connection with the well known iterative methods of Jacobi, of Extrapolated Jacobi and of Successive Over-relaxation, in two directions: i) The iteration matrix of the iterative scheme considered is more general than that of the aforementioned methods and may include a diagonal part and ii) the theory is presented in such a way that the number of equivalent statements given in the text covers the Accelerated Overrelaxation (AOR) method introduced by the present author not long ago.     

预条件的平方Smith法求解大型Sylvester矩阵方程

提出了一种预条件的平方Smith算法求解大型连续Sylvester矩阵方程,该算法利用交替方向隐式迭代(ADI)来构造预条件算子,将原方程转换为非对称Stein方程,并在Krylov子空间中应用平方Smith法迭代产生低秩逼近解。数值实验表明,与已知的Jacobi迭代法等算法相比,该算法有更好的迭代效率和收敛精度。     

Finite elements using long vectors of the DAP

The Finite Element Method for solving partial differential equations using the long vector mode of the DAP is presented. This work was developed on a 32 × 32 version of the DAP attached to a Perq scientific workstation.

First, the implementation of finite elements using the long vector mode of the DAP is given, followed by the treatment of boundary conditions and the solution of the finite element equations using a parallel conjugate gradient method. Two solution procedures for the parallel conjugate gradient method, first without global matrix assembly and second with global matrix assembly, are presented and their advantages and disadvantages are discussed. Preconditioners for the conjugate gradient method based on iteration methods are also discussed and results include a 1-step point Jacobi preconditioner, a m-step point Jacobi preconditioner and a m-step multi-colour preconditioner. Finally long vector implementations for a larger system which stores multinodes per processor using a sliced mapping technique and domain decomposition are included.     

A stencil of the finite-difference method for the 2D convection diffusion equation and its new iterative scheme

The paper gives the numerical stencil for the two-dimensional convection diffusion equation and the technique of elimination, and builds up the new iterative scheme to solve the implicit difference equation. The scheme's convergence and its higher rate of convergence than the Jacobi iteration are proved. And the numerical example indicates that the new scheme has the same parallelism and a higher rate of convergence than the Jacobi iteration.     

基于MPI的Jacobi迭代算法的并行化

Jacobi迭代算法是解线性方程组的最常用的方法,具有广泛的应用。Jacobi迭代属于计算密集型[1],将并行计算技术应用到Jacobi迭代中,具有重要的意义。通过使用消息传递编程模型mpi提供的向量数据类型和虚拟进程拓扑来实现Jacobi迭代的并行化。     

求解二维对流扩散方程的投影迭代法

鉴于目前流行的求解大型稀疏代数方程组的投影迭代法中,为提高迭代效率,在迭代前通常需要对稀疏矩阵进行预处理,改善迭代矩阵的条件数,从而减少迭代次数,这使得发展稀疏矩阵的存储技术变得尤为关键。基于二维对流扩散方程的四阶紧致差分格式,将其转化为代数方程组,得到其三对角块形式的系数矩阵,利用稀疏矩阵存储技术和预条件迭代法进行求解,并与传统的中心差分格式所得数值解进行比较,充分说明了方法的高效性和可靠性。