并行求解多维递归方程组的三种Krylov子空间迭代方法

多维递归方程组在并行求解时存在串并行不一致问题,提供三种Krylov子空间迭代求解方法———PCG/ATCG和GMRES来解决这一问题,并采用典型算例对这三种Krylov子空间迭代方法进行正确性验证和加速比测试.试验表明这三种Krylov子空间迭代法在并行规模较大的情况下,均能够正确求解多维递归方程组,并且加速特性良好.     

一种GMRES与GMERR的混和算法

近年来Krylov子空间类算法得到了很大的发展，其中GMRES算法已成为求解大型稀疏非对称线性系统的一种成熟并且很有效的解法，但该算法有时会出现停滞，并且它是以残量来判断收敛，并不能很好地衡量近似解的精确程度，而GMERR算法是最近几年出现的另一种Krylov子空间类算法，它和GMRES算法相比是各有千秋，文章结合两种算法的优点，提出了一种组合算法，它对求解大型稀疏非对称线性系统相当有效。     

三维热传导方程的Krylov子空间方法并行分析

热传导方程在地下水流动数值模拟、油藏数值模拟等工程计算中有着广泛应用,其并行实现是加速问题求解速度、提高问题求解规模的重要手段,因此热传导方程的并行求解具有重要意义。对Krylov子空间方法中的CG和GMRES算法进行并行分析,并对不同的预处理CG算法作了比较。在Linux集群系统上,以三维热传导模型为例进行了数值实验。实验结果表明,CG算法比GMRES算法更适合建立三维热传导模型的并行求解。此外,CG算法与BJACOBI预条件子的整合在求解该热传导模型时,其并行程序具有良好的加速比和效率。因此,采用BJACOBI预处理技术的CG算法是一种较好的求解三维热传导模型的并行方案。     

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

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

利用近似解加速求解SAT问题的启发式完全算法

结合DPLL完全算法能够证明可满足性(SAT)问题的不可满足性和局部搜索算法快速的优点,提出利用近似解加速求解SAT问题的启发式完全算法.首先利用局部搜索算法快速地得到一个近似解,并将该近似解作为完全算法的初始输入,用于其中分支变量的相位决策.该算法引导完全算法优先搜索近似解所在的子空间,加速解决器找到可满足解的过程,为SAT问题的求解提供了一种新的有效途径.实验结果表明,该算法有效地提高了决策的精度和SAT解决器的效率,对很多实例非常有效.     

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

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

面向多目标流水车间调度的多种群多目标遗传算法

针对制造型企业普遍存在的流水车间调度问题,建立了以最小化最迟完成时间和总延迟时间为目标的多目标调度模型,并提出一种基于分解方法的多种群多目标遗传算法进行求解.该算法将多目标流水车间调度问题分解为多个单目标子问题,并分阶段地将这些子问题引入到算法迭代过程进行求解.算法在每次迭代时,依据种群的分布情况选择各子问题的最好解及与其相似的个体分别为当前求解的子问题构造子种群,通过多种群的进化完成对多个子问题最优解的并行搜索.通过对标准测试算例进行仿真实验,结果表明所提出的算法在求解该问题上能够获得较好的非支配解集.     

蚁群算法求解连续空间优化问题的一种方法

针对蚁群算法不太适合求解连续性优化问题的缺陷,提出用蚁群算法求解连续空间优化问题的一种方法.该方法将解空间划分成若干子域,在蚁群算法的每一次迭代中,首先根据信息量求出解所在的子域,然后在该子域内已有的解中确定解的具体值.以非线性规划问题为例所进行的计算结果表明,该方法比使用模拟退火算法、遗传算法具有更好的收敛速度.     

迭代张量高阶奇异值分解的图像恢复方法

为了有效地对图像缺失数据进行恢复, 提出一种迭代张量高阶奇异值分解（HOSVD）图像缺失数据恢复方法。该方法首先利用拉格朗日乘子方法将张量核范数目标函数进行子问题分解操作, 简化了求解过程, 然后迭代地采用张量高阶奇异值分解阈值方法进行子问题求解, 最终得到恢复后的图像缺失数据。将矩阵奇异值阈值算法进行扩展而得的HOSVD阈值方法充分利用了图像内部和图像与图像之间的多重约束关系, 大大提高了恢复精度。模拟实验和真实图像实验结果显示该方法具有良好的缺失数据的恢复性能。     

车辆路径问题的禁忌搜索算法研究

简要回顾了车辆路径问题的禁忌搜索算法的发展现状,提出了一种改进的禁忌搜索算法。该算法将路径问题按不同的车辆-顾客分配结构分解成若干子问题,然后用禁忌搜索算法求解每个子问题,最后从所有子问题的最优解中选出全局最优解。理论分析和实验结果表明该算法比以往的算法有以下优点：拓展了搜索空间,提高了最优解的效果;是一种将问题进行空间分解的并行算法,可采用多台计算机同时运算以减少整体运行时间。     

GMRES implementations and residual smoothing techniques for solving ill-posed linear systems

There are verities of useful Krylov subspace methods to solve nonsymmetric linear system of equations. GMRES is one of the best Krylov solvers with several different variants to solve large sparse linear systems. Any GMRES implementation has some advantages. As the solution of ill-posed problems are important. In this paper, some GMRES variants are discussed and applied to solve these kinds of problems. Residual smoothing techniques are efficient ways to accelerate the convergence speed of some iterative methods like CG variants. At the end of this paper, some residual smoothing techniques are applied for different GMRES methods to test the influence of these techniques on GMRES implementations.     

一种改进的图像迭代盲反卷积算法

针对传统迭代盲反卷积算法收敛速度慢、容易出现解模糊等问题,提出一种改进的图像迭代盲反卷积算法。利用动量矩求解图像的有限支持域,在支持域中使频率域和空间域交替迭代,从而实现图像的盲复原。仿真结果表明,与传统迭代盲反卷积算法和基于小波变换的盲反卷积算法相比,该算法的收敛速度较快,具有较好的图像恢复效果。     

Improving Medical CT Image Blind Restoration Algorithm Based on Dictionary Learning by Alternating Direction Method of Multipliers

In this paper, the medical CT image blind restoration is translated into two sub problems, namely, image estimation based on dictionary learning and point spread function estimation. A blind restoration algorithm optimized by the alternating direction method of multipliers for medical CT images was proposed. At present, the existing methods of blind image restoration based on dictionary learning have the problem of low efficiency and precision. This paper aims to improve the effectiveness and accuracy of the algorithm and to improve the robustness of the algorithm. The local CT images are selected as training samples, and the K-SVD algorithm is used to construct the dictionary by iterative optimization, which is beneficial to improve the efficiency of the algorithm. Then, the orthogonal matching pursuit algorithm is employed to implement the dictionary update. Dictionary learning is accomplished by sparse representation of medical CT images. The alternating direction method of multipliers (ADMM) is used to solve the objective function and realize the local image restoration, so as to eliminate the influence of point spread function. Secondly, the local restoration image is used to estimate the point spread function, and the convex quadratic optimization method is used to solve the point spread function sub problems. Finally, the optimal estimation of point spread function is obtained by iterative method, and the global sharp image is obtained by the alternating direction method of multipliers. Experimental results show that, compared with the traditional adaptive dictionary restoration algorithm, the new algorithm improves the objective image quality metrics, such as peak signal to noise ratio, structural similarity, and universal image quality index. The new algorithm optimizes the restoration effect, improves the robustness of noise immunity and improves the computing efficiency.     

基于曲线波和稀疏表达的卡通—纹理模型

CT图像去噪恢复是医学影像图像处理的基础环节。为解决卡通—纹理模型在医学图像去噪应用中计算困难和精度低的问题,对卡通—纹理模型分解方法进行了扩展。首先,以曲线波变换描述图像卡通—纹理模型中的结构部分;其次,以更稀疏的对偶树复小波变换描述图像卡通—纹理模型中的纹理部分;最后,建立了结合曲线波和稀疏表达的图像卡通—纹理分解模型,并讨论了模型的分解算法。仿真实验结果表明,新方法可有效地解决医学影像图像去噪算法中迭代计算量大的问题,并可提高处理后图像的质量。     

图像恢复的正则化混合GMRES(m)方法

为了充分利用广义极小化残量方法在处理大规模线性问题时的优势,将其同正则化技术相结合应用于图像恢复领域,提出了一种新的图像恢复方法。该方法基于Arnoldi过程,用一系列规模远小于原不适定问题的最小二乘问题来逼近原问题,并应用截断奇异值分解正则化技术保证稳定求解这些最小二乘问题。其中,根据图像恢复问题的具体特点,在确定截断奇异值分解的截断次数时,对传统的L-曲线准则进行了少许修改。数值试验结果表明,试验数据与肉眼观察恢复图像的清晰程度相吻合,说明新方法是有效的。     

Iterative lavrentiev regularization for symmetric kernel-driven operator equations: with application to digital image restoration problems

~~Iterative Lavrentiev regularization for symmetric kernel-driven operator equations: with application to digital image restoration problems1. Roggemann, M. C, WeJsh, B., Imaging Through Turbulence. New York. CRC Press, 1996. 2. Bertero, M., Boccacci, P., Introduction to Inverse Prolems in Imaging, Bristol: IOP Publishing, 1998. 3. George, S., Nair, M. T., A class of discrepancy principles for the simplified regularization of ill-posed problems, J. Austral. Math. Soc, Ser.…     

A real‐time algorithm for nonlinear receding horizon control using multiple shooting and continuation/Krylov method

In this paper, we propose a real‐time algorithm for nonlinear receding horizon control using multiple shooting and the continuation/GMRES method. Multiple shooting is expected to improve numerical accuracy in calculations for solving boundary value problems. The continuation method is combined with a Krylov subspace method, GMRES, to update unknown quantities by solving a linear equation. At the same time, we apply condensing, which reduces the size of the linear equation, to speed up numerical calculations. A numerical example shows that both numerical accuracy and computational speed improve using the proposed algorithm by combining multiple shooting with condensing. Copyright © 2008 John Wiley & Sons, Ltd.     

Convergence analysis of modified PGSS methods for singular saddle-point problems

Recently, variants of shift-splitting iteration method have been proposed for solving singular saddle-point problems. However, these methods can only be proved to converge to one of the solutions of the consistent singular linear system, not knowing any further information about this solution. In this work, we consider a modified preconditioned generalized shift-splitting (MPGSS) iteration method for solving both consistent and inconsistent singular saddle-point problems. This method is proved to converge to the best least squares solution. Moreover, based on the iteration form, a preconditioner is obtained to accelerate Krylov subspace methods. Theoretical analysis shows that the preconditioned GMRES method also converges to the best least squares solution of the consistent singular saddle-point problem. In addition, numerical results are presented to show the effectiveness and robustness of the proposed iteration method and preconditioner.     

Parallel Krylov Methods for Econometric Model Simulation

This paper investigates parallel solution methods to simulate large-scalemacroeconometric models with forward-looking variables. The method chosen isthe Newton-Krylov algorithm, and we concentrate on a parallel solution to thesparse linear system arising in the Newton algorithm. We empirically analyzethe scalability of the GMRES method, which belongs to the class of so-calledKrylov subspace methods. The results obtained using an implementation of thePETSc 2.0 software library on an IBM SP2 show a near linear scalability forthe problem tested.     

Adaptive contourlet-wavelet iterative shrinkage/thresholding for remote sensing image restoration

In this paper, we present an adaptive two-step contourlet-wavelet iterative shrinkage/thresholding （TcwlST） algorithm for remote sensing image restoration. This algorithm can be used to deal with various linear inverse problems （LIPs）, including image deconvolution and reconstruction. This algorithm is a new version of the famous two-step iterative shrinkage/thresholding （TWIST） algorithm. First, we use the split Bregrnan Rudin-Osher-Fatemi （ROF） model, based on a sparse dictionary, to decompose the image into cartoon and texture parts, which are represented by wavelet and contourlet, respectively. Second, we use an adaptive method to estimate the regularization parameter and the shrinkage threshold. Finally, we use a linear search method to find a step length and a fast method to accelerate convergence. Results show that our method can achieve a signal-to-noise ratio improvement （ISNR） for image restoration and high convergence speed.