A preconditioned and extrapolation-accelerated GMRES method for PageRank

In this paper, we propose and analyze GMRES-type methods for the PageRank computation. However, GMRES may converge very slowly or sometimes even diverge or break down when the damping factor is close to 1 and the dimension of the search subspace is low. We propose two strategies: preconditioning and vector extrapolation accelerating, to improve the convergence rate of the GMRES method. Theoretical analysis demonstrate the efficiency of the proposed strategies and numerical experiments show that the performance of the proposed methods is very much better than that of the traditional methods for PageRank problems.     

欧氏看涨期权定价问题的一种有效七点差分GMRES方法

用有限差分方法研究欧氏看涨期权定价问题.首先,将Black-Scholes方程通过等价代换化成一个标准的抛物型偏微分方程.其次,在求解区域构造时间精度为O（△τ^3）、空间精度为O（h^6）的差分格式,并通过Fourier分析方法证明该差分格式是无条件稳定的;边界区域选用精度较高、稳定性好的Crank-Nicolson格式,建立迭代方程.然后,用GMRES（generalized minimal residual）方法求解该方法.最后,给出一个欧氏看涨期权的数值算例,并与解析解进行比较,验证差分格式的有效性.     

An extension of the Gegenbauer pseudospectral method for the time fractional Fokker‐Planck equation

The time fractional Fokker‐Planck equation has been used in many physical transport problems which take place under the influence of an external force field. In this paper we examine pseudospectral method based on Gegenbauer polynomials and Chebyshev spectral differentiation matrix to solve numerically a class of initial‐boundary value problems of the time fractional Fokker‐Planck equation on a finite domain. The presented method reduces the main problem to a generalized Sylvester matrix equation, which can be solved by the global generalized minimal residual method. Some numerical experiments are considered to demonstrate the accuracy and the efficiency of the proposed computational procedure.     

A matrix‐free preconditioned Newton/GMRES method for unsteady Navier–Stokes solutions

The unsteady compressible Reynolds‐averaged Navier–Stokes equations are discretized using the Osher approximate Riemann solver with fully implicit time stepping. The resulting non‐linear system at each time step is solved iteratively using a Newton/GMRES method. In the solution process, the Jacobian matrix–vector products are replaced by directional derivatives so that the evaluation and storage of the Jacobian matrix is removed from the procedure. An effective matrix‐free preconditioner is proposed to fully avoid matrix storage. Convergence rates, computational costs and computer memory requirements of the present method are compared with those of a matrix Newton/GMRES method, a four stage Runge–Kutta explicit method, and an approximate factorization sub‐iteration method. Effects of convergence tolerances for the GMRES linear solver on the convergence and the efficiency of the Newton iteration for the non‐linear system at each time step are analysed for both matrix‐free and matrix methods. Differences in the performance of the matrix‐free method for laminar and turbulent flows are highlighted and analysed. Unsteady turbulent Navier–Stokes solutions of pitching and combined translation–pitching aerofoil oscillations are presented for unsteady shock‐induced separation problems associated with the rotor blade flows of forward flying helicopters. Copyright © 2000 John Wiley & Sons, Ltd.     

NGLM:一类全局收敛的Newton-GMRES方法

本文提出了一类具有全局收敛性质的Newton-GMRES方法—NGLM方法．该方法是对经典Newton—GMRES方法的推广．NGLM方法的全局策略是当在非精确Newton方向上后退不能成功时，转而在一个子空间上运用信赖域方法确定迭代步长．理论分析与数值实验均表明，NGLM方法改善了Newton—GMRES方法的强健性．     

Block Krylov Subspace Methods for Solving Large Sylvester Equations

In the present paper, we propose block Krylov subspace methods for solving the Sylvester matrix equation AX–XB=C. We first consider the case when A is large and B is of small size. We use block Krylov subspace methods such as the block Arnoldi and the block Lanczos algorithms to compute approximations to the solution of the Sylvester matrix equation. When both matrices are large and the right-hand side matrix is of small rank, we will show how to extract low-rank approximations. We give some theoretical results such as perturbation results and bounds of the norm of the error. Numerical experiments will also be given to show the effectiveness of these block methods.     

ON BLOCK PRECONDITIONERS FOR PDE-CONSTRAINED OPTIMIZATION PROBLEMS

Recently, Bal proposed a block-counter-diagonal and a block-counter-triangular precon- ditioning matrices to precondition the GMRES method for solving the structured system of linear equations arising from the Galerkin finite-element discretizations of the distributed control problems in （Computing 91 （2011） 379-395）. He analyzed the spectral properties and derived explicit expressions of the eigenvalues and eigenvectors of the preconditioned matrices. By applying the special structures and properties of the eigenvector matrices of the preconditioned matrices, we derive upper bounds for the 2-norm condition numbers of the eigenvector matrices and give asymptotic convergence factors of the preconditioned GMRES methods with the block-counter-diagonal and the block-counter-triangular pre- conditioners. Experimental results show that the convergence analyses match well with the numerical results.     

An Investigation of Restarted GMRES Method by Using Flexible Starting Vectors

<正>We discuss a variant of restarted GMRES method that allows changes of the restarting vector at each cycle of iterations.The merit of the variant is that previously generated information can be utilized to select a new starting vector,such that the occurrence of stagnation be mitigated or the convergence be accelerated.The more appealing utilization of the new method is in conjunction with a harmonic Ritz vector as the starting vector,which is discussed in detail.Numerical experiments are carried out to demonstrate that the proposed procedure can effectively mitigate the occurrence of stagnation due to the presence of small eigenvalues in modulus.     

EFFECTS OF IMPLICIT PRECONDITIONERS ON SOLUTION ACCELERATION SCHEMES IN CFD

Several solution acceleration techniques, used to obtain steady state CFD solutions as quickly as possible, are applied to an implicit, upwind Euler solver to evaluate their effectiveness. The implicit system is solved using either ADI or ILU and the solution acceleration techniques evaluated are quasi-Newton iteration, Jacobian freezing, multigrid and GMRES. ILU is a better preconditioner than ADI because it can use larger time steps. Adding GMRES does not always improve the convergence. However, GMRES preconditioned with ILU and multigrid can take advantage of Jacobian freezing to produce an efficient scheme that is relatively independent of grid size and grid quality.     

跳跃扩散下双障碍期权定价的数值解

提出了一种求解带有跳跃的双障碍期权定价模型的数值方法.算法采用了Crank-Nicolson 有限差分格式和复化梯形公式对模型进行离散,对离散后的线性系统采用GMRES迭代法求解,并且构造了一个新的预处理算子以加速迭代法的收敛.数值实验验证了该方法能快速求解模型并达到二阶收敛精度.