求解离散不适定问题的正则化GMERR方法

迭代极小残差方法是求解大型线性方程组的常用方法, 通常用残差范数控制迭代过程.但对于不适定问题, 即使残差范数下降, 误差范数未必下降. 对大型离散不适定问题,组合广义最小误差(GMERR)方法和截断奇异值分解(TSVD)正则化方法, 并利用广义交叉校验准则(GCV)确定正则化参数,提出了求解大型不适定问题的正则化GMERR方法.数值结果表明, 正则化GMERR方法优于正则化GMRES方法.     

A note on the mesh independence of convergence bounds for additive Schwarz preconditioned GMRES

Additive Schwarz preconditioners, when including a coarse grid correction, are said to be optimal for certain discretized partial differential equations, in the sense that bounds on the convergence of iterative methods are independent of the mesh size h. Cai and Zou (Numer. Linear Algebra Appl. 2002; 9 :379–397) showed with a one‐dimensional example that in the absence of a coarse grid correction the usual GMRES bound has a factor of the order of . In this paper we consider the same example and show that for that example the behavior of the method is not well represented by the above‐mentioned bound: We use an a posteriori bound for GMRES from (SIAM Rev. 2005; 47 :247–272) and show that for that example a relevant factor is bounded by a constant. Furthermore, for a sequence of meshes, the convergence curves for that one‐dimensional example, and for several two‐dimensional model problems, are very close to each other; thus, the number of preconditioned GMRES iterations needed for convergence for a prescribed tolerance remains almost constant. Copyright © 2008 John Wiley & Sons, Ltd.     

Pseudoeigenvector bases and deflated GMRES for highly nonnormal matrices

Pseudoeigenvalues have been extensively studied for highly nonnormal matrices. This paper focuses on the corresponding pseudoeigenvectors. The properties and uses of pseudoeigenvector bases are investigated. It is shown that pseudoeigenvector bases can be much better conditioned than eigenvector bases. We look at the stability and the varying quality of pseudoeigenvector bases. Then applications are considered including the exponential of a matrix. Several aspects of GMRES convergence are looked at, including why using approximate eigenvectors to deflate eigenvalues can be effective even when there is not a basis of eigenvectors.     

Dynamic block GMRES: an iterative method for block linear systems

We present variants of the block-GMRES() algorithms due to Vital and the block-LGMRES(,) by Baker, Dennis and Jessup, obtained with replacing the standard QR factorization by a rank-revealing QR factorization in the Arnoldi process. The resulting algorithm allows for dynamic block deflation whenever there is a linear dependency between the Krylov vectors or the convergence of a right-hand-side occurs. implementations of the algorithms were tested on a number of test matrices and the results show that in some cases a substantial reduction of the execution time is obtained. Also a parallel implementation of our variant of the block-GMRES() algorithm, using and was tested on parallel computer, showing good parallel efficiency. This work was carried out while the author was at IM/UFRGS.     

Krylov subspace methods, biorthogonal polynomials and Padé-type approximants

It is shown that Krylov subspace methods for solving systems of linear equations can be based on formal biorthogonal polynomials and on Padé-type and Padé approximants. New algorithms for their implementation are derived. This revised version was published online in June 2006 with corrections to the Cover Date.     

Some results about GMRES in the singular case

In this paper, we study the Generalized Minimal Residual (GMRES) method for solving singular linear systems, particularly when the necessary and sufficient condition to obtain a Krylov solution is not satisfied. Thanks to some new results which may be applied in exact arithmetic or in finite precision, we analyze the convergence of GMRES and restarted GMRES. These formulas can also be used in the case when the systems are nonsingular. In particular, it allows us to understand what is often referred to as stagnation of the residual norm of GMRES. This revised version was published online in June 2006 with corrections to the Cover Date.     

Schwarz domain decomposition for the incompressible Navier–Stokes equations in general co‐ordinates

This paper describes a domain decomposition method for the incompressible Navier–Stokes equations in general co‐ordinates. Domain decomposition techniques are needed for solving flow problems in complicated geometries while retaining structured grids on each of the subdomains. This is the so‐called block‐structured approach. It enables the use of fast vectorized iterative methods on the subdomains. The Navier–Stokes equations are discretized on a staggered grid using finite volumes. The pressure‐correction technique is used to solve the momentum equations together with incompressibility conditions. Schwarz domain decomposition is used to solve the momentum and pressure equations on the composite domain. Convergence of domain decomposition is accelerated by a GMRES Krylov subspace method. Computations are presented for a variety of flows. Copyright © 2000 John Wiley & Sons, Ltd.     

MODELLING OF WAVE PROPAGATION IN THE NEARSHORE REGION USING THE MILD SLOPE EQUATION WITH GMRES-BASED ITERATIVE SOLVERS

The mild slope equation in its linear and non-linear forms is used for the modelling of nearshore wave propagation. The finite difference method is used to descretize the governing elliptic equations and the resulting system of equations is solved using GMRES-based iterative method. The original GMRES solution technique of Saad and Schultz is not directly applicable to the present case owing to the complex coefficient matrix. The simpler GMRES algorithm of Walker and Zhou is used as the core solver, making the upper Hessenberg factorization unneccessary when solving the least squares problem. Several preconditioning-based acceleration strategies are tested and the results show that the GMRES-based iteration scheme performs very well and leads to monotonic convergence for all the test-cases considered.     

Preconditioning methods for discontinuous Galerkin solutions of the Navier–Stokes equations

A Newton–Krylov method is developed for the solution of the steady compressible Navier–Stokes equations using a discontinuous Galerkin (DG) discretization on unstructured meshes. Steady-state solutions are obtained using a Newton–Krylov approach where the linear system at each iteration is solved using a restarted GMRES algorithm. Several different preconditioners are examined to achieve fast convergence of the GMRES algorithm. An element Line-Jacobi preconditioner is presented which solves a block-tridiagonal system along lines of maximum coupling in the flow. An incomplete block-LU factorization (Block-ILU(0)) is also presented as a preconditioner, where the factorization is performed using a reordering of elements based upon the lines of maximum coupling. This reordering is shown to be superior to standard reordering techniques (Nested Dissection, One-way Dissection, Quotient Minimum Degree, Reverse Cuthill–Mckee) especially for viscous test cases. The Block-ILU(0) factorization is performed in-place and an algorithm is presented for the application of the linearization which reduces both the memory and CPU time over the traditional dual matrix storage format. Additionally, a linear p-multigrid preconditioner is also considered, where Block-Jacobi, Line-Jacobi and Block-ILU(0) are used as smoothers. The linear multigrid preconditioner is shown to significantly improve convergence in term of number of iterations and CPU time compared to a single-level Block-Jacobi or Line-Jacobi preconditioner. Similarly the linear multigrid preconditioner with Block-ILU smoothing is shown to reduce the number of linear iterations to achieve convergence over a single-level Block-ILU(0) preconditioner, though no appreciable improvement in CPU time is shown.     

A Fast,Matrix-free Implicit Method for Computing Low Mach Number Flows on Unstructured Grids

A fast, matrix-free implicit method has been developed to solve low Mach number flow problems on unstructured grids. The preconditioned compressible Euler and Navier-Stokes equations are integrated in time using a linearized implicit scheme. A newly developed fast, matrix-free implicit method, GMRES + LU?SGS, is then applied to solve the resultant system of linear equations. A variety of computations has been made for a wide range of flow conditions, for both in viscid and viscous flows, in both 2D and 3D to validate the developed method and to evaluate the effectiveness of the GMRES + LU?SGS method. The numerical results obtained indicate that the use of the GMRES + LU?SGS method leads to a significant increase in performance over the LU?SGS method, while maintaining memory requirements similar to its explicit counterpart. An overall speedup factor from one to more than two order of magnitude for all test cases in comparison with the explicit method is demonstrated.