On Backtracking Failure in Newton–GMRES Methods with a Demonstration for the Navier–Stokes Equations

In an earlier study of inexact Newton methods, we pointed out that certain counterintuitive behavior may occur when applying residual backtracking to the Navier–Stokes equations with heat and mass transport. Specifically, it was observed that a Newton–GMRES method globalized by backtracking (linesearch, damping) may be less robust when high accuracy is required of each linear solve in the Newton sequence than when less accuracy is required. In this brief discussion, we offer a possible explanation for this phenomenon, together with an illustrative numerical experiment involving the Navier–Stokes equations.     

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 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.     

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.     

Preconditioned implicit solution of linear hyperbolic equations with adaptivity

This paper describes a method for solving hyperbolic partial differential equations using an adaptive grid: the spatial derivatives are discretised with a finite volume method on a grid which is structured and partitioned into blocks which may be refined and derefined as the solution evolves. The solution is advanced in time via a backward differentiation formula. The discretisation used is second-order accurate and stable on Cartesian grids. The resulting system of linear equations is solved by GMRES at every time-step with the convergence of the iteration being accelerated by a semi-Toeplitz preconditioner. The efficiency of this preconditioning technique is analysed and numerical experiments are presented which illustrate the behaviour of the method on a parallel computer.     

Application of Preconditioned GMRES Algorithm for Analysis of Millimeter Wave Ferrite Sphere Circulators

The generalized minimal residual (GMRES) iterative method is applied to solve such sparse large non-symmetric system of linear equations resulting from the use of edge-based finite element method. In order to speed up the convergence of GMRES, the symmetric successive overrelaxation (SSOR) preconditioning scheme is applied for the analysis of millimeter wave ferrite circulator. Consequently, this preconditioned GMRES (PGMRES) approach can reach convergence 19 times faster than GMRES. The isolation and insertion losses of millimeter wave waveguide circulator are compared with those obtained from literature.     

Higher order finite element methods and multigrid solvers in a benchmark problem for the 3D Navier–Stokes equations

This paper presents a numerical study of the 3D flow around a cylinder which was defined as a benchmark problem for the steady state Navier–Stokes equations within the DFG high‐priority research program flow simulation with high‐performance computers by Schafer and Turek (Vol. 52, Vieweg: Braunschweig, 1996). The first part of the study is a comparison of several finite element discretizations with respect to the accuracy of the computed benchmark parameters. It turns out that boundary fitted higher order finite element methods are in general most accurate. Our numerical study improves the hitherto existing reference values for the benchmark parameters considerably. The second part of the study deals with efficient and robust solvers for the discrete saddle point problems. All considered solvers are based on coupled multigrid methods. The flexible GMRES method with a multiple discretization multigrid method proves to be the best solver. Copyright © 2002 John Wiley & Sons, Ltd.     

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.     

Convergence conditions for a restarted GMRES method augmented with eigenspaces

We consider the GMRES(m,k) method for the solution of linear systems Ax=b, i.e. the restarted GMRES with restart m where to the standard Krylov subspace of dimension m the other subspace of dimension k is added, resulting in an augmented Krylov subspace. This additional subspace approximates usually an A‐invariant subspace. The eigenspaces associated with the eigenvalues closest to zero are commonly used, as those are thought to hinder convergence the most. The behaviour of residual bounds is described for various situations which can arise during the GMRES(m,k) process. The obtained estimates for the norm of the residual vector suggest sufficient conditions for convergence of GMRES(m,k) and illustrate that these augmentation techniques can remove stagnation of GMRES(m) in many cases. All estimates are independent of the choice of an initial approximation. Conclusions and remarks assessing numerically the quality of proposed bounds conclude the paper. Copyright © 2004 John Wiley & Sons, Ltd.     

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

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