迭代模型Smith预估控制:算法和稳定性

为了解决Smith预估控制算法建立模型不精确的问题,并针对一类可重复运行的时滞过程,在模糊相轨迹模型Smith预估控制算法的基础上提出迭代模型Smith预估控制。该算法在不设计自适应的前提下,可以自适应得到精确的预估模型,同时辨识过程的时滞时间。证明指出只要原系统闭环稳定则迭代预估模型Smith预估控制系统稳定,且给出了算法的收敛性判据。仿真表明,所提方法不需要已知过程的模型,通过一定次数的"迭代"即可得到精确的预估模型,从而克服了常规算法控制品质依赖精确数学模型的缺陷。同时该算法具有较强的鲁棒性。     

3-D寄生电容直接边界元提取的预条件方法

集成电路密度的不断提高对寄生电容提取的精度和速度提出了越来越高的要求,文章应用直接边界元法提取互连电容,对一种GMRES预条件算法做出修改并应用于实际计算中。两个典型算例的理论分析和实际计算表明,这种预条件方法可以降低方程的迭代次数约30%,明显减少方程求解时间。     

基于水平集理论的图像分割

图像分割要求同一区域中的象素要具有某些相同的特性,不同的子区域具有不同的特性.本文算法利用水平集理论的曲线演化方法,提出了一种新的图像分割算法.该算法利用区域内方差描述区域一致性,区域间灰度均值之差的平方描述区域间差异性,对能量函数用梯度最陡下降法,推导出曲线演化方程.实验结果表明,该算法分割结果更符合实际情况,并随着迭代次数的增加,轮廓曲线边界平滑;当达到一定的迭代次数时,图像分割结果稳定.     

适用于GRAPES数值天气预报软件的ILU预条件子

探讨了一种适用于我国自主研发的数值天气预报模式软件GRAPES的不完全LU(ILU)分解预条件子.针对GRAPES模式所特有的具有对角优势结构的赫姆霍兹方程系数矩阵,提出了一种有效的ILU分解方案,并将分解得到的预条件子应用到模式核心的动力积分计算迭代算法中,从而达到加速算法收敛,提高模式软件整体性能的目的.     

求解Maxwell线性元鞍点系统的基于HX预条件子的Uzawa算法

首先对含跳系数的H~1型和H(curl)型椭圆问题的线性有限元方程,分别设计了基于AMG预条件子和基于节点辅助空间预条件子(HX预条件子)的PCG法.数值实验表明,算法的迭代次数基本不依赖于系数跳幅和离散网格"尺寸".然后以此为基础,对Maxwell方程组鞍点问题的第一类N(e)d(e)lec线性棱元离散系统设计并分析了一种基于HX预条件子的Uzawa算法.当系数光滑时,理论上证明了算法的收敛率与网格规模无关.数值实验表明,新算法对跳系数情形也是高效和稳定的.     

Kronecker积重构卷积核矩阵的图像迭代复原方法

图像复原实际上是反卷积问题,其中的卷积核矩阵属于大尺寸的Toeplitz矩阵。为了降低迭代复原算法的计算复杂度,通过分析该Toeplitz系统的病态性及常见快速求解方法,提出一种基于卷积核矩阵重构的预条件共轭梯度迭代算法。首先根据Toeplitz矩阵可分解为Kronecker积的和的性质,对点扩散函数进行奇异值分解,将各奇异值对应的左右向量构造子Toeplitz矩阵,子矩阵作Kronecker积并加和,从而得到卷积核矩阵的分解式,然后根据Kronecker乘积的性质,将该分解式用于构造预条件算子,最后利用预条件共轭梯度法求解。计算复杂度分析及实验表明该方法有助于加速迭代的收敛并得到稳定结果。     

Krylov子空间方法在一类PDE上的数值实验与分析

１．引言本文重点进行迭代算法的数值比较,利用数值实验来分析求解非对称线性系统的Ｋｒｙｌｏｖ子空间方法（如：ＧＭＲＥＳ,Ｏｒｔｈｏｍｉｎ,ＱＭＲ,ＣＧＳ,ＢＩＣＧＳＴＡＢ等）及其预条件算法（ＩＬＵ（一１）,ＩＬＵ（０）;ＩＬＵ（１）;ＩＬＵ（２）,左预条件,右预条件）的迭代求解效果（收敛速度）;迭代收敛行为的比较（剩余向量ＬＺ模的下降速度及下降曲线的光滑性）,迭代参数的选取（正交向量的个数的选取及对算法的影响）;迭代收敛速度受问题规模的影响等等．目的是对各种预条件算法的优缺点进行数值分析和评价,为…     

一种平衡策略下网络多输入多输出系统的预编码方案

针对在多小区多输入多输出（MIMO）系统预处理中,最大化目标用户信干噪比与最小化干扰泄露之间存在的相互矛盾,提出一种基于平衡策略的预编码算法,构建预编码算法数学模型,引入干扰代价函数,并借助拉格朗日方程对所提算法的预编码向量进行求解,同时对算法的实现步骤进行了说明。最后在仿真中,对效用函数的收敛速度与迭代次数的关系进行了仿真,并基于系统最大和速率对该算法与现有算法的性能进行了比较,仿真结果验证了该算法在收敛速度与系统吞吐量方面的优越性能。     

基于预条件共轭梯度法的混凝土层析成像

根据常规图像重建的共轭梯度迭代算法,提出一种预条件共轭梯度法。用一种新的预条件子M来改善系数矩阵的条件数,结合一般的共轭梯度法,导出预条件共轭梯度法。实验结果表明,预条件共轭梯度算法比共轭梯度算法具有更好的CT重建效果和消噪能力,可提高计算的精度和图像的重建质量。     

一种针对大波数Helmholtz方程的高性能并行预条件迭代求解算法

针对传统串行迭代法求解大波数Helmholtz方程存在效率低下且受限于单机内存的问题,提出了一种基于消息传递接口(Message Passing Interface,MPI) 的并行预条件迭代法。该算法利用复移位拉普拉斯算子对Helmholtz方程进行预条件处理,联合稳定双共轭梯度法和基于矩阵的多重网格法来求解预条件方程离散后的大规模线性系统,在Linux集群系统上基于 MPI环境实现了求解算法的并行计算,重点解决了多重网格的并行划分、信息传递和多重网格组件的构建问题。数值实验表明,对于大波数问题,提出的算法具有良好的并行加速比,相较于串行算法极大地提高了计算效率。     

Specialized Parallel Algorithms for Solving Lyapunov and Stein Equations

Lyapunov and Stein matrix equations arise in many important analysis and synthesis applications in control theory. The traditional approach to solving these equations relies on the QR algorithm which is notoriously difficult to parallelize. We investigate iterative solvers based on the matrix sign function and the squared Smith iteration which are highly efficient on parallel distributed computers. We also show that by coding using the Parallel Linear Algebra Package (PLAPACK) it is possible to exploit the structure in the matrices and reduce the cost of these solvers. While the performance improvements due to the optimizations are modest, so is the coding effort. One of the optimizations, the updating of a QR factorization, has important applications elsewhere, e.g., in applications requiring the solution of a linear least-squares problem when the linear system is periodically updated. The experimental results on a Cray T3E attest to the high efficiency of these parallel solvers.     

Compatible coarsening in the multigraph algorithm

We present some heuristics incorporating the philosophy of compatible relaxation into an existing algebraic multigrid method, the so-called multigraph solver of Bank and Smith [Bank Randolph E., Kent Smith R. An algebraic multilevel multigraph algorithm. SIAM J Sci Comput 2002;25:1572–92]. In particular, approximate left and right eigenvectors of the iteration matrix for the smoother are used in computing both the sparsity pattern and the numerical values of the transfer matrices that correspond to restriction and prolongation. Some numerical examples illustrate the effectiveness of the procedure.     

Reduction of Smith Normal Form Transformation Matrices

Smith normal form computations are important in group theory, module theory and number theory. We consider the transformation matrices for the Smith normal form over the integers and give a presentation of arbitrary transformation matrices for this normal form. Our main contribution is an algorithm that replaces already computed transformation matrices by others with small entries. We combine methods from lattice basis reduction with a procedure to reduce the sum of the squared entries of both transformation matrices. This algorithm performs well even for matrices of large dimensions.     

An iterative algorithm for approximate orthogonalisation of symmetric matrices

In a previous article, one of the authors presented an extension of an iterative approximate orthogonalisation algorithm, due to Z. Kovarik, for arbitrary rectangular matrices. In the present article, we propose a modified version of this extension for the class of arbitrary symmetric matrices. For this new algorithm, the computational effort per iteration is much smaller than for the initial one. We prove its convergence and also derive an error reduction factor per iteration. In the second part of the article, we show that we can eliminate the matrix inversion required by the previous algorithm in each iteration, by replacing it with a polynomial matrix expression. Some numerical experiments are also presented for a collocation discretisation of a first kind integral equation.     

A local construction of the Smith normal form of a matrix polynomial

We present an algorithm for computing a Smith form with multipliers of a regular matrix polynomial over a field. This algorithm differs from previous ones in that it computes a local Smith form for each irreducible factor in the determinant separately and then combines them into a global Smith form, whereas other algorithms apply a sequence of unimodular row and column operations to the original matrix. The performance of the algorithm in exact arithmetic is reported for several test cases.     

An Efficient Algorithm for Matrix-Valued and Vector-Valued Optimal Mass Transport

We present an efficient algorithm for recent generalizations of optimal mass transport theory to matrix-valued and vector-valued densities. These generalizations lead to several applications including diffusion tensor imaging, color image processing, and multi-modality imaging. The algorithm is based on sequential quadratic programming. By approximating the Hessian of the cost and solving each iteration in an inexact manner, we are able to solve each iteration with relatively low cost while still maintaining a fast convergence rate. The core of the algorithm is solving a weighted Poisson equation, where different efficient preconditioners may be employed. We utilize incomplete Cholesky factorization, which yields an efficient and straightforward solver for our problem. Several illustrative examples are presented for both the matrix and vector-valued cases.     

Numerical methods for the QCD overlap operator: III. Nested iterations

The numerical and computational aspects of chiral fermions in lattice quantum chromodynamics are extremely demanding. In the overlap framework, the computation of the fermion propagator leads to a nested iteration where the matrix vector multiplications in each step of an outer iteration have to be accomplished by an inner iteration; the latter approximates the product of the sign function of the hermitian Wilson fermion matrix with a vector.In this paper we investigate aspects of this nested paradigm. We examine several Krylov subspace methods to be used as an outer iteration for both propagator computations and the Hybrid Monte-Carlo scheme. We establish criteria on the accuracy of the inner iteration which allow to preserve an a priori given precision for the overall computation. It will turn out that the accuracy of the sign function can be relaxed as the outer iteration proceeds. Furthermore, we consider preconditioning strategies, where the preconditioner is built upon an inaccurate approximation to the sign function. Relaxation combined with preconditioning allows for considerable savings in computational efforts up to a factor of 4 as our numerical experiments illustrate. We also discuss the possibility of projecting the squared overlap operator into one chiral sector.     

大型Lyapunov方程的并行求解

借鉴于求解大型矩阵主特征对方法中子空间迭代的概念,给出了求解Lyapunov方程的 新方法,进而推导出Lyapunov方程直接迭代的高效并行算法,同时也给出了算法的收敛性证 明和解的误差分析.     

Finite iterative algorithms for the generalized Sylvester-conjugate matrix equation {AX+BY=E\overline{X}F+S}

This paper investigates the generalized Sylvester-conjugate matrix equation, which includes the normal Sylvester-conjugate, Kalman–Yakubovich-conjugate and generalized Sylvester matrix equations as its special cases. An iterative algorithm is presented for solving such a kind of matrix equations. This iterative method can give an exact solution within finite iteration steps for any initial values in the absence of round-off errors. Another feature of the proposed algorithm is that it is implemented by original coefficient matrices. By specifying the proposed algorithm, iterative algorithms for some special matrix equations are also developed. Two numerical examples are given to illustrate the effectiveness of the proposed methods.     

Learning and design of principal curves

Principal curves have been defined as “self-consistent” smooth curves which pass through the “middle” of a d-dimensional probability distribution or data cloud. They give a summary of the data and also serve as an efficient feature extraction tool. We take a new approach by defining principal curves as continuous curves of a given length which minimize the expected squared distance between the curve and points of the space randomly chosen according to a given distribution. The new definition makes it possible to theoretically analyze principal curve learning from training data and it also leads to a new practical construction. Our theoretical learning scheme chooses a curve from a class of polygonal lines with k segments and with a given total length to minimize the average squared distance over n training points drawn independently. Convergence properties of this learning scheme are analyzed and a practical version of this theoretical algorithm is implemented. In each iteration of the algorithm, a new vertex is added to the polygonal line and the positions of the vertices are updated so that they minimize a penalized squared distance criterion. Simulation results demonstrate that the new algorithm compares favorably with previous methods, both in terms of performance and computational complexity, and is more robust to varying data models