Multigrid preconditioned Krylov subspace methods for three-dimensional numerical solutions of the incompressible Navier–Stokes equations

We consider numerical methods for the incompressible Reynolds averaged Navier–Stokes equations discretized by finite difference techniques on non-staggered grids in body-fitted coordinates. A segregated approach is used to solve the pressure–velocity coupling problem. Several iterative pressure linear solvers including Krylov subspace and multigrid methods and their combination have been developed to compare the efficiency of each method and to design a robust solver. Three-dimensional numerical experiments carried out on scalar and vector machines and performed on different fluid flow problems show that a combination of multigrid and Krylov subspace methods is a robust and efficient pressure solver. This revised version was published online in June 2006 with corrections to the Cover Date.     

Adaptive solution of infinite linear systems by Krylov subspace methods

In this paper we consider the problem of approximating the solution of infinite linear systems, finitely expressed by a sparse coefficient matrix. We analyse an algorithm based on Krylov subspace methods embedded in an adaptive enlargement scheme. The management of the algorithm is not trivial, due to the irregular convergence behaviour frequently displayed by Krylov subspace methods for nonsymmetric systems. Numerical experiments, carried out on several test problems, indicate that the more robust methods, such as GMRES and QMR, embedded in the adaptive enlargement scheme, exhibit good performances.     

Numerical solution of unsteady incompressible Navier-Stokes equations using high-order method of lines

A high-order method of lines is devised for solving the unsteady incompressible Navier-Stokes equations in the vorticity-stream function formulation. The vorticity transport equation is solved by the eight- or tenth-order method of lines and the Poisson equation for the stream function is solved by a high-order multigrid method. The numerical results of the two-dimensional (2D) homogeneous isotropic turbulence and the turbulent mixing layer are presented. In the homogeneous isotropic turbulence with tenth order of spatial accuracy, the power law of the inertial energy spectrum at the climax stage coincides with the predictions by Batchelor, Leith and Kraichnan. In the turbulent mixing layer with eight order of spatial accuracy, the vortex pairing are reproduced and the coherent structure of the Reynolds stress at the pairing is noticed.     

Alternating Krylov subspace image restoration methods

Alternating methods for image deblurring and denoising have recently received considerable attention. The simplest of these methods are two-way methods that restore contaminated images by alternating between deblurring and denoising. This paper describes Krylov subspace-based two-way alternating iterative methods that allow the application of regularization operators different from the identity in both the deblurring and the denoising steps. Numerical examples show that this can improve the quality of the computed restorations. The methods are particularly attractive when matrix-vector products with a discrete blurring operator and its transpose can be evaluated rapidly, but the structure of these operators does not allow inexpensive diagonalization.     

Stochastic nonhomogeneous incompressible Navier-Stokes equations

We construct solutions for 2- and 3-D stochastic nonhomogeneous incompressible Navier-Stokes equations with general multiplicative noise. These equations model the velocity of a mixture of incompressible fluids of varying density, influenced by random external forces that involve feedback; that is, multiplicative noise. Weak solutions for the corresponding deterministic equations were first found by Kazhikhov [A.V. Kazhikhov, Solvability of the initial and boundary-value problem for the equations of motion of an inhomogeneous viscous incompressible fluid, Soviet Phys. Dokl. 19 (6) (1974) 331-332; English translation of the paper in: Dokl. Akad. Nauk SSSR 216 (6) (1974) 1240-1243]. A stochastic version with additive noise was solved by Yashima [H.F. Yashima, Equations de Navier-Stokes stochastiques non homogènes et applications, Thesis, Scuola Normale Superiore, Pisa, 1992].The methods here extend the Loeb space techniques used to obtain the first general solutions of the stochastic Navier-Stokes equations with multiplicative noise in the homogeneous case [M. Capiński, N.J. Cutland, Stochastic Navier-Stokes equations, Applicandae Math. 25 (1991) 59-85]. The solutions display more regularity in the 2D case. The methods also give a simpler proof of the basic existence result of Kazhikhov.     

Galerkin and subspace decomposition methods in space and time for the Navier-Stokes equations

The Galerkin method and the subspace decomposition method in space and time for the two-dimensional incompressible Navier-Stokes equations with the H²-initial data are considered. The subspace decomposition method consists of splitting the approximate solution as the sum of a low frequency component discretized by the small time step Δt and a high frequency one discretized by the large time step pΔt with p>1. The H²-stability and L²-error analysis for the subspace decomposition method are obtained. Finally, some numerical tests to confirm the theoretical results are provided.     

On the uniqueness of strong solution to the incompressible Navier-Stokes equations with damping

In this paper, we show that the Cauchy problem of the incompressible Navier-Stokes equations with damping α|u|^β−1u(α>0) has global strong solution for any β>3 and the strong solution is unique when 3<β?5. This improves earlier results.     

Three-dimensional eddy-current computation using Krylov subspace methods

This paper considers the numerical solution of a transmissionboundary-value problem for the time-harmonic Maxwell equationswith the help of a special finite-volume discretization. Applyingthis technique to several three-dimensional test problems, weobtain large, sparse, complex linear systems, which are solvedby four types of algorithm, using biconjugate gradients, squaredconjugate gradients, stabilized conjugate gradients, and generalizedminimal residuals, respectively. Wecombine these methods withsuitably chosen preconditioning matrices and compare the speedof convergence.     

Krylov type subspace methods for matrix polynomials

We consider solving eigenvalue problems or model reduction problems for a quadratic matrix polynomial Iλ² − Aλ − B with large and sparse A and B. We propose new Arnoldi and Lanczos type processes which operate on the same space as A and B live and construct projections of A and B to produce a quadratic matrix polynomial with the coefficient matrices of much smaller size, which is used to approximate the original problem. We shall apply the new processes to solve eigenvalue problems and model reductions of a second order linear input-output system and discuss convergence properties. Our new processes are also extendable to cover a general matrix polynomial of any degree.     

Upwind compact finite difference scheme for time-accurate solution of the incompressible Navier-Stokes equations

This article presents a time-accurate numerical method using high-order accurate compact finite difference scheme for the incompressible Navier-Stokes equations. The method relies on the artificial compressibility formulation, which endows the governing equations a hyperbolic-parabolic nature. The convective terms are discretized with a third-order upwind compact scheme based on flux-difference splitting, and the viscous terms are approximated with a fourth-order central compact scheme. Dual-time stepping is implemented for time-accurate calculation in conjunction with Beam-Warming approximate factorization scheme. The present compact scheme is compared with an established non-compact scheme via analysis in a model equation and numerical tests in four benchmark flow problems. Comparisons demonstrate that the present third-order upwind compact scheme is more accurate than the non-compact scheme while having the same computational cost as the latter.     

Structure-preserving model reduction of second-order systems by Krylov subspace methods

In this paper, structure-preserving model reduction methods for second-order systems are investigated. By introducing an appropriate parameter, the second-order system is represented by a strictly dissipative realization and the \(H_{2}\) norm of the strictly dissipative system is discussed. Then, based on the Krylov subspace techniques, two model reduction methods are proposed to reduce the order of the strictly dissipative system. Further, the reduced second-order systems are obtained. Moreover, according to the factorization of the error system, the \(H_{2}\) error bounds are represented by the Kronecker product and the vectorization operator. Finally, two numerical examples illustrate the efficiency of our methods.     

Projection and projection-difference methods for the solution of the Navier-Stokes equations

The projection and projection-difference methods for the approximate solution of the nonlinear unsteady Navier-Stokes equations in a bounded two-dimensional region are studied. Asymptotic estimates for the convergence rate of the approximate solutions and the time and space derivatives in the uniform topology are obtained.     

Convergence analysis of the one-step iterative Krylov subspace methods

The paper suggests a new way of definition of the iteration parameter for the one-step Krylov subspace method, which is based on some geometrical extremal problem. An equivalent renorming of the underlying space speeds up the convergence rate.     

Comparison of Krylov subspace methods on the PageRank problem

PageRank algorithm plays a very important role in search engine technology and consists in the computation of the eigenvector corresponding to the eigenvalue one of a matrix whose size is now in the billions. The problem incorporates a parameter that determines the difficulty of the problem. In this paper, the effectiveness of stationary and nonstationary methods are compared on some portion of real web matrices for different choices of . We see that stationary methods are very reliable and more competitive when the problem is well conditioned, that is for small values of . However, for large values of the parameter the problem becomes more difficult and methods such as preconditioned BiCGStab or restarted preconditioned GMRES become competitive with stationary methods in terms of Mflops count as well as in number of iterations necessary to reach convergence.     

Two-Level preconditioned Krylov subspace methods for the solution of three-dimensional heterogeneous Helmholtz problems in seismics

In this paper we address the solution of three-dimensional heterogeneous Helmholtz problems discretized with compact fourth-order finite difference methods with application to acoustic waveform inversion in geophysics. In this setting, the numerical simulation of wave propagation phenomena requires the approximate solution of possibly very large linear systems of equations. We propose an iterative two-grid method where the coarse grid problem is solved inexactly. A single cycle of this method is used as a variable preconditioner for a flexible Krylov subspace method. Numerical results demonstrate the usefulness of the algorithm on a realistic three-dimensional application. The proposed numerical method allows us to solve wave propagation problems with single or multiple sources even at high frequencies on a reasonable number of cores of a distributed memory cluster.     

Fast generalized cross validation using Krylov subspace methods

The task of fitting smoothing spline surfaces to meteorological data such as temperature or rainfall observations is computationally intensive. The generalized cross validation (GCV) smoothing algorithm, if implemented using direct matrix techniques, is O(n ³) computationally, and memory requirements are O(n ²). Thus, for data sets larger than a few hundred observations, the algorithm is prohibitively slow. The core of the algorithm consists of solving series of shifted linear systems, and iterative techniques have been used to lower the computational complexity and facilitate implementation on a variety of supercomputer architectures. For large data sets though, the execution time is still quite high. In this paper we describe a Lanczos based approach that avoids explicitly solving the linear systems and dramatically reduces the amount of time required to fit surfaces to sets of data.      

Convergence of compressible Navier-Stokes-Maxwell equations to incompressible Navier-Stokes equations

The combined quasi-neutral and non-relativistic limit of compressible Navier-Stokes-Maxwell equations for plasmas is studied. For well-prepared initial data, it is shown that the smooth solution of compressible Navier-Stokes-Maxwell equations converges to the smooth solution of incompressible Navier-Stokes equations by introducing new modulated energy functional.     

Preserving geometric properties of the exponential matrix by block Krylov subspace methods

Given a large square real matrix A and a rectangular tall matrix Q, many application problems require the approximation of the operation . Under certain hypotheses on A, the matrix preserves the orthogonality characteristics of Q; this property is particularly attractive when the associated application problem requires some geometric constraints to be satisfied. For small size problems numerical methods have been devised to approximate while maintaining the structure properties. On the other hand, no algorithm for large A has been derived with similar preservation properties. In this paper we show that an appropriate use of the block Lanczos method allows one to obtain a structure preserving approximation to when A is skew-symmetric or skew-symmetric and Hamiltonian. Moreover, for A Hamiltonian we derive a new variant of the block Lanczos method that again preserves the geometric properties of the exact scheme. Numerical results are reported to support our theoretical findings, with particular attention to the numerical solution of linear dynamical systems by means of structure preserving integrators. AMS subject classification (2000) 65F10, 65F30, 65D30     

Hermite collocation solution of partial differential equations via preconditioned Krylov methods

We are concerned with the numerical solution of partial differential equations (PDEs) in two spatial dimensions discretized via Hermite collocation. To efficiently solve the resulting systems of linear algebraic equations, we choose a Krylov subspace method. We implement two such methods: Bi‐CGSTAB [1] and GMRES [2]. In addition, we utilize two different preconditioners: one based on the Gauss–Seidel method with a block red‐black ordering (RBGS); the other based upon a block incomplete LU factorization (ILU). Our results suggest that, at least in the context of Hermite collocation, the RBGS preconditioner is superior to the ILU preconditioner and that the Bi‐CGSTAB method is superior to GMRES. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17:120–136, 2001