一种GMRES（m）加速算法

求解大型稀疏线性方程组一般采用迭代法,其中GMRES（m）算法是一种非常有效的算法,然而用该算法求解线性方程组时,收敛速度较慢甚至出现停滞。文章通过对GMRES（m）算法收敛性分析,给出了一种GMRES（m）加速算法。     

GMRES算法及其加速收敛现象分析

在对于求解大型非对称线性方程组方面,社会各界已经提出许多行之有效的迭代算法。然而目前由Saad和 Schultz提出的极小残量剩余(GMRES)方法是最为流行并且有效的方法之一。本文主要讨论GMRE(m)算法理论及其收敛现象分析。特别地叙述GMRES方法的收敛率和此斜投影过程中Ritz值对特征值的逼近程度之间的联系。这是分析GMRES的实际收敛行为的有效方法。     

鲁棒极点配置的一种新算法

§1.问题描述极点配置是线性多变量控制理论中的一个重要的课题(参见[1]),问题的一般提法如下: 问题(PA):已知 A∈R~(n×m),B∈R~(n×m),秩 rankB=m, ={λ_1,λ_2,…,λ_n},其中每个λ_i是实数或者在 中成复共轭出现。求 F∈R~(m×n),使得σ(A+BF)= ,σ(·)表示(·)的谱. 对于已给的 A,B和 ,令 ={F∈R~(m×n):σ(A×BF)= }. 根据Wonham定理(参见[2]),如果矩阵对(A,B)可控,并且 如(PA)所述,则     

拉格朗日乘子的高价估计及其应用

其中A∈R~(m×n),c∈R~n,A,c是给定的,x∈R~m是未知向量,f(x)是线性的、或是凹的、或是伪凹的函数.令 S={x:A~Tx≤c,x∈R~m}.(1.3)假设S是非空有界的,且其内点集合S~0≠φ中.于是由极值问题的最优性理论可知问题(1.1)—(1.2)的最优解必在凸多面体S的一个顶点上达到.不失一般性,设其最优解为     

计算线性不等式组可行解的方法

本文考虑求解以下线性不等式组的可行解的问题 A~Ty≤C, (1.1)其中A∈R~(m×n),C∈R~n,y∈R~m.不失一般性,假设m≤n,且矩阵A的秩为m。令S={y|A~Ty≤C,y∈R~m}.若S≠φ,且存在-y∈R~m使得不等式组(1.1)严格成立,则称y是S的严格可行内点.以S~0记S的所有严格可行内点的集合. 这类问题出现在线性规划、非线性规划和其它问题之中.特别是近年来线性规划的     

求解大型非对称线性系统的一种新的预处理方法

针对大型稀疏非对称正定线性方程组,本文提出了新的预处理GMRES方法,并分析了谱半径和最优参数α的选取.最后通过数值例子比较GMRES方法,HSS预处理和新的预处理GMRES方法,发现新的预处理方法具有更好的收敛率.     

用AOR方法求解大型稀疏最小二乘问题的收敛性

在许多实际问题中,我们都希望计算以下超定线性方程组 Ax=b (1)的最小二乘解.其中A为一大型疏m×n实矩阵,m>n,b为一给定的m维实向量.这里假定Rank(A)=n. 我们知道,(1)可叙述成,求唯一向量X∈R~n,使||b—AX||_2=min||b—Ay||_2对一切y∈R~n。由于Rank(A)=n,上述最小二乘问题等价于求一个n维向量X∈R~n和     

解大规模非对称线性方程组的Lanczos方法和精化Lanczos方法

引言科学工程计算的核心问题之一是数值求解大规模线性方程组,即给定n阶非奇异的非对1期贾仲孝等:解大规模非对称线性方程组的Lanczos方法和精化Lanczos方法称矩阵A和n维向量b,求一个。维向量x,使得Ax=b.(l)观察到该问题可以转化为     

并行计算水下大尺度弹性壳体的低频声散射

有限元与边界元耦合模型是研究水下弹性壳体目标低频声散射常用的数值方法。应用该模型计算大尺度弹性目标的声散射时需要大量的计算时间与存储空间,采用并行数值的方式可以解决这一问题。首先并行计算生成有限元矩阵和边界元矩阵,然后应用并行化的广义极小残差(GMRES)迭代算法求解大型非对称线性方程组。详细叙述了并行GMRES(m)迭代算法的执行过程,并以球壳的声散射计算为例分析了迭代步数对算法收敛情况的影响。最后计算了Benchmark目标模型的低频散射声场,分析了其收发分置散射目标强度以及表面声场的分布。     

“Descriptor”系统极点配置问题的稳定算法

1.引 言 极点配置是控制理论中研究得较多的一个课题.近年来,引起了数值计算工作者浓厚的兴趣.极点配置问题的数学提法为 问题(P):给定矩阵 A∈R~(n×n),B∈R~(n×m),A={λ_1,…,λ_n},〈A,B〉可控,A共轭封     

Simpler GMRES with deflated restarting

In this paper we consider the simpler GMRES method augmented by approximate eigenvectors for solving nonsymmetric linear systems. We modify the augmented restarted simpler GMRES proposed by Boojhawon and Bhuruth to obtain a simpler GMRES with deflated restarting. Moreover, we also propose a residual-based simpler GMRES with deflated restarting, which is numerically more stable. The main advantage over the augmented version is that the simpler GMRES with deflated restarting requires less matrix-vector products per restart cycle. Some details of implementation are also considered. Numerical experiments show that the residual-based simpler GMRES with deflated restarting is effective.     

Restarted GMRES augmented with harmonic Ritz vectors for shifted linear systems

Frommer and Glassner [Frommer, A. and Glassner, U., 1998, Restarted GMRES for shifted linear systems, SIAM Journal on Scientific Computing, 19, 15–26.] develop a variant of the restarted GMRES method for shifted linear systems at the expense of only one matrix–vector multiplication per iteration. However, restarting slows down the convergence, even stagnation. We present a variant of the restarted GMRES augmented with some approximate eigenvectors for the shifted systems. The convergence can be much faster at little extra expense. Numerical experiments show its efficiency.     

Accelerate weighted GMRES by augmenting error approximations

By augmenting error approximations at every restart cycle, this paper presents an accelerating strategy for restarted weighted generalized minimum residual (GMRES) method. We show that the procedure can effectively correct the occurrence of small skip D-angles, which indicates a slow convergent phase. Numerical results show that the new method converges much regular and faster than the weighted GMRES method. Finally, comparisons are made between the new and the recently proposed LGMRES methods.     

Restarted Gmres Augmented With Eigenvectors For Shifted Linear Systems * Supported by the National Natural Science Foundation of China and the Science and Technology Developing Foundation of University in Shanghai of China

Shifted matrices, which differ by a multiple of the identity only, generate the same Krylov subspaces with respect to any fixed vector. Frommer and Glassner [5] develop a variant of the restarted GMRES method for such shifted systems at the expense of only one matrix-vector multiplication per iteration. However, restarting slows down the convergence, even stagnation. We present a variant of the restarted GMRES augmented with some eigenvectors for the shifted systems. The convergence can be much faster at little extra expense. Numerical experiments show its efficiency.     

基于Deflation技术的预调制Restarted GMRES算法

电学层析成像的图像重建需要对逆问题进行求解,而求解过程中存在着非线性、欠定性以及病态性严重等难题,使得图像重建可能不收敛,或者致使收敛,但获得的图像分辨率较低。针对现有的一些图像重建算法,提出基于Deflation技术的预调制Restarted GMRES算法,在原有full GMRES算法基础上,提高了收敛速度以及图像成像分辨率,并通过仿真实验证明。     

一种GMRES与GMERR的混和算法

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

Parallelizable restarted iterative methods for nonsymmetric linear systems. part I: Theory

Large sparse nonsymmetric problems of the form A u = b are frequently solved using restarted conjugate gradient-type algorithms such as the popular GCR and GMRES algorithms. In this study we define a new class of algorithms which generate the same iterates as the standard GMRES algorithm but require as little as half of the computational expense. This performance improvement is obtained by using short economical three-term recurrences to replace the long recurrence used by GMRES. The new algorithms are shown to have good numerical properties in typical cases, and the new algorithms may be easily modified to be as numerically safe as standard GMRES. Numerical experiments with these algorithms are given in Part II, in which we demonstrate the improved performance of the new schemes on different computer architectures.     

A Pseudospectral Multi-Domain Method for the Incompressible Navier–Stokes Equations

A pseudospectral method for the solution of incompressible flow problems based on an iterative solver involving an implicit treatment of linearized convective terms is presented. The method is designed for moderately complex geometries by means of a multi-domain approach. Key components are a Chebyshev collocation discretization, a special pressure-correction scheme and a restarted GMRES method with a preconditioner derived from a fast direct solver. The performance of the method with respect to the multi-domain functionality is investigated and compared to finite-volume approaches.     

Large sparse linear systems arising from mimetic discretization

In this work we perform an experimental study of iterative methods for solving large sparse linear systems arising from a second-order 2D mimetic discretization. The model problem is the 2D Poisson equation with different boundary conditions. We use GMRES with the restarted parameter and BiCGstab as iterative methods. We also use various preconditioning techniques including the robust preconditioner ILUt. The numerical experiments consist of large sparse linear systems with up to 643 200 degrees of freedom.