Algebraic factorizations for 3D non-hydrostatic free surface flows

The high amount of computer resources required to simulate complex free surface flows has prompted for developing fractional step schemes capable of reducing the computational effort. These schemes are borrowed from a wider family of methods originally devised for the incompressible Navier-Stokes equations. An alternative approach is to perform an algebraic splitting on the coefficient matrix of the linear system resulting from the discretized problem, ending up with the successive solution of sub-problems of smaller size. The resulting schemes are shown in different cases to be the algebraic counterpart of the standard fractional step formulations. This algebraic procedure was again originally devised in the context of incompressible Navier-Stokes system, but we believe it is far more general: in this paper it is indeed extended to the more involved 3D free surface flow model. The inexact block factorization technique is applied to the coefficient matrix arising from the problem at hand and two significant choices for the approximation are discussed and numerically tested.     

A robust preconditioner for fluid–structure interaction problems

Two preconditioners are presented for equation systems of strongly coupled fluid–structure interaction computations where the structure is modeled by shell elements. These preconditioners fall into the general category of incomplete LU factorization. The two differ mainly in whether the coefficient matrix is factorized node by node or variable-by-variable. In the variable-wise preconditioner, a modified Schur complement system for pressure is solved approximately with a few iterations using a special preconditioner. The efficiencies of the two preconditioners are compared for different finite element formulations of the fluid mechanics part, including formulations with SUPG and PSPG stabilizations.     

On the progressive iteration approximation property and alternative iterations

This note revisits the progressive iteration approximation property and some recent modifications from the point of view of iterative methods for solving linear systems. In particular we show the connection with the classical Richardson iteration and modified Richardson iteration. We propose to use GMRES as an alternative iterative method. Numerical experiments achieve much better approximations with only few iterations, which can be explained by an interpretation of the GMRES method.     

Preconditioners for Schwarz relaxation methods applied to differential algebraic equations

In this paper, the authors investigate the ability of Schwarz relaxation (SR) methods to deal with large systems of differential algebraic equations (DAEs) and assess their respective efficiency. Since the number of iterations required to achieve convergence of the classical SR method is strongly related to the number of subdomains and the time step size, two new preconditioning techniques are here developed. A preconditioner based on a correction using the algebraic equations is first introduced and leads to a number of iterations independent on the number of subdomains. A second preconditioner based on a correction using the Schur complement matrix makes the convergence independent on both the number of subdomains and the integration step size. Application on European electricity network is presented to outline the performance, efficiency, and robustness of the proposed preconditioning techniques for the solution of DAEs.     

自顶向下聚集型代数多重网格预条件的健壮性与参数敏感性研究

本文针对自顶向下聚集型代数多重网格预条件,进行了健壮性与参数敏感性研究。对从各向同性与各向异性偏微分方程边值问题离散所得的多种稀疏线性方程组,首先对问题规模敏感性进行了研究,并与基于强连接的经典聚集型算法进行了系统比较,发现虽然对沿不同坐标轴具有强各向异性的问题,基于坐标分割的自顶向下聚集型算法不如基于强连接的经典聚集算法,但对其它所有情形,自顶向下聚集型算法都具有明显优势,特别是在采用Jacobi光滑时,优势更加显著。之后,对最粗网格层的分割数与每次每个子图进行分割时的分割数这两个参数进行了敏感性分析,发现在采用Jacobi光滑求解五点差分离散所得的稀疏线性方程组时,自顶向下聚集型算法对这两个参数存在敏感性,虽然大部分情形下,迭代次数比较稳定,但在少量几种情形下,迭代次数明显增加。而对从九点差分离散得到的稀疏线性方程组,以及在采用Gauss-Seidel光滑的情况下,算法对这两个参数的选取不再具有敏感性,迭代次数都比较稳定。综合分析表明,自顶向下聚集型代数多重网格预条件具有较好的健壮性,特别是在采用Gauss-Seidel光滑,或采用九点差分离散时,健壮性表现更加充分。     

Stability of Some Generalized Godunov Schemes With Linear High-Order Reconstructions

Classical Semi-Lagrangian schemes have the advantage of allowing large time steps, but fail in general to be conservative. Trying to keep the advantages of both large time steps and conservative structure, Flux-Form Semi-Lagrangian schemes have been proposed for various problems, in a form which represent (at least in a single space dimension) a high-order, large time-step generalization of the Godunov scheme. At the theoretical level, a recent result has shown the equivalence of the two versions of Semi-Lagrangian schemes for constant coefficient advection equations, while, on the other hand, classical Semi-Lagrangian schemes have been proved to be strictly related to area-weighted Lagrange–Galerkin schemes for both constant and variable coefficient equations. We address in this paper a further issue in this theoretical framework, i.e., the relationship between stability of classical and of Flux-Form Semi-Lagrangian schemes. We show that the stability of the former class implies the stability of the latter, at least in the case of the one-dimensional linear continuity equation.     

Determination of a good value of the time step and preconditioned Krylov subspace methods for the Navier-Stokes equations

The main purpose of this paper is to develop stable versions of some Krylov subspace methods for solving the linear systems of equations Ax = b which arise in the difference solution of 2-D nonstationary Navier-Stokes equations using implicit scheme and to determine a good value of the time step. Our algorithms are based on the conjugate-gradient method with a suitable preconditioner for solving the symmetric positive definite system and preconditioned GMRES, Orthomin(K), QMR methods for solving the nonsymmetric and (in)definite system. The performance of these methods is compared. In addition, we show that by using the condition number of the first nonsymmetric coefficient matrix, it is possible to determine a good value of the time step.     

三维对流扩散方程的稀疏存储及预条件迭代

基于四阶紧致格式对三维对流扩散方程进行离散,并给出所得到的离散线性方程组的块三角稀疏矩阵形式。以带双阈值的不完全因子化LU分解[(ILUT(τ,s))]作为预条件子,分别用FGMRES、BICGSTAB和TFQMR作为迭代加速器,对离散线性方程组进行求解验证了格式精度并比较了不同迭代法的CPU时间和迭代步。此外,通过比较传统迭代法和预条件迭代法的计算效率,表明预条件迭代法不仅能够保证格式的四阶精度,还能极大地提高收敛效率。     

Performance analysis of parallel Schwarz preconditioners in the LES of turbulent channel flows

We present a comparative study of parallel Schwarz preconditioners in the solution of linear systems arising in a Large Eddy Simulation (LES) procedure for turbulent plane channel flows. This procedure applies a time-splitting technique to suitably filtered Navier–Stokes equations, in order to decouple the continuity and momentum equations, and uses a semi-implicit scheme for time integration and finite volumes for space discretisation. This approach requires the solution of four sparse linear systems at each time step, accounting for a large part of the overall simulation; hence the linear system solvers are a crucial component in the whole procedure. Several preconditioners are applied in the simulation of a reference test case for the LES community, using discretisation grids of different sizes, with the aim of analysing the effects of different algorithmic choices defining the preconditioners, and identifying the most effective ones for the selected problem. The preconditioners, coupled with the GMRES method, are run within SParC-LES, a recently developed LES code based on the PSBLAS and MLD2P4 libraries for parallel sparse matrix computations and preconditioning.     

A Schur method for solving algebraic Riccati equations

In this paper a new algorithm for solving algebraic Riccati equations (both continuous-time and discrete-time versions) is presented. The method studied is a variant of the classical eigenvector approach and uses instead an appropriate set of Schur vectors, thereby gaining substantial numerical advantages. Considerable discussion is devoted to a number of numerical issues. The method is apparently quite numerically stable and performs reliably on systems with dense matrices up to order 100 or so, storage being the main limiting factor.     

Numerical and computational aspects of some block-preconditioners for saddle point systems

Linear systems with two-by-two block matrices are usually preconditioned by block lower- or upper-triangular systems that require an approximation of the related Schur complement. In this work, in the finite element framework, we consider one special such approximation, namely, the element-wise Schur complement. It is sparse and its construction is perfectly parallelizable, making it an appropriate ingredient when building preconditioners for iterative solvers executed on both distributed and shared memory computer architectures. For saddle point matrices with symmetric positive (semi-)definite blocks we show that the Schur complement is spectrally equivalent to the so-constructed approximation and derive spectral equivalence bounds. We also illustrate the quality of the approximation for nonsymmetric problems, where we observe the same good numerical efficiency.Furthermore, we demonstrate the computational and numerical performance of the corresponding preconditioned iterative solution method on a large scale model benchmark problem originating from the elastic glacial isostatic adjustment model discretized using the finite element method.     

Parallel Rosenbrock methods for chemical systems

Parallel Rosenbrock methods are developed for systems with stiff chemical reactions. Unlike classical Runge-Kutta methods, these linearly implicit schemes avoid the necessity to iterate at each time step. Parallelism across the method allows for the solution of the linear algebraic systems in essentially Backward Euler-like solves on concurrent processors. In addition to possessing excellent stability properties, these methods are computationally efficient while preserving positivity of the solutions. Numerical results confirm these characteristics when applied to problems involving stiff chemistry, and enzyme kinetics.     

The Uzawa-PPS iteration methods for nonsingular and singular non-Hermitian saddle point problems

In this paper, based on the positive-definite and positive-semidefinite splitting (PPS) iteration scheme, we establish a class of Uzawa-PPS iteration methods for solving nonsingular and singular non-Hermitian saddle point problems with the (1,1) part of the coefficient matrix being non-Hermitian positive definite. Theoretical analyses show that the convergence and semi-convergence properties of the proposed methods can be guaranteed under suitable conditions. Furthermore, we consider acceleration of the Uzawa-PPS methods by Krylov subspace (like GMRES) methods and discuss the spectral properties of the corresponding preconditioned matrix. Numerical experiments are given to confirm the theoretical results which show that the feasibility and effectiveness of the proposed methods and preconditioners.     

A block-asynchronous relaxation method for graphics processing units

In this paper, we analyze the potential of asynchronous relaxation methods on Graphics Processing Units (GPUs). We develop asynchronous iteration algorithms in CUDA and compare them with parallel implementations of synchronous relaxation methods on CPU- or GPU-based systems. For a set of test matrices from UFMC we investigate convergence behavior, performance and tolerance to hardware failure. We observe that even for our most basic asynchronous relaxation scheme, the method can efficiently leverage the GPUs computing power and is, despite its lower convergence rate compared to the Gauss–Seidel relaxation, still able to provide solution approximations of certain accuracy in considerably shorter time than Gauss–Seidel running on CPUs- or GPU-based Jacobi. Hence, it overcompensates for the slower convergence by exploiting the scalability and the good fit of the asynchronous schemes for the highly parallel GPU architectures. Further, enhancing the most basic asynchronous approach with hybrid schemes–using multiple iterations within the “subdomain” handled by a GPU thread block–we manage to not only recover the loss of global convergence but often accelerate convergence of up to two times, while keeping the execution time of a global iteration practically the same. The combination with the advantageous properties of asynchronous iteration methods with respect to hardware failure identifies the high potential of the asynchronous methods for Exascale computing.     

An energy preserving/decaying scheme for nonlinearly constrained multibody systems

Several numerical time integration methods for multibody system dynamics are described: an energy preserving scheme and three energy decaying ones, which introduce high-frequency numerical dissipation in order to annihilate the nondesired high-frequency oscillations. An exhaustive analysis of these four schemes is done, including their formulation, and energy preserving and decaying properties by taking into account the presence of nonlinear algebraic constraints and the incrementation of finite rotations. A new energy preserving/decaying scheme is developed, which is well suited for either stiff or nonstiff nonlinearly constrained multibody systems. Examples on a series of test cases show the performance of the algorithms.     

A Jacobi-like method for solving algebraic Riccati equations onparallel computers

An algorithm to solve continuous-time algebraic Riccati equations through the Hamiltonian Schur form is developed. It is an adaption for Hamiltonian matrices of an asymmetric Jacobi method of Eberlein (1987). It uses unitary symplectic similarity transformations and preserves the Hamiltonian structure of the matrix. Each iteration step needs only local information about the current matrix, thus admitting efficient parallel implementations on certain parallel architectures. Convergence performance of the algorithm is compared with the Hamiltonian-Jacobi algorithm of Byers (1990). The numerical experiments suggest that the method presented here converges considerably faster for non-Hermitian Hamiltonian matrices than Byers' Hamiltonian-Jacobi algorithm. Besides that, numerical experiments suggest that for the method presented here, the number of iterations needed for convergence can be predicted by a simple function of the matrix size     

Algebraic Connectivity Estimation Based on Decentralized Inverse Power Iteration

In this work, we propose a new scheme to estimate the algebraic connectivity of the graph describing the network topology of a multi‐agent system. We consider network topologies modeled by undirected graphs. The main idea is to propose a new decentralized conjugate gradient algorithm and a decentralized compound inverse power iteration scheme. The matrix inversion computation in this scheme is replaced by solving the non‐homogeneous linear equations relying on the proposed decentralized conjugate gradient algorithm. With this scheme, we can achieve a fast convergence rate in estimating the algebraic connectivity by setting the parameter μ properly. Simulation results demonstrate the effectiveness of the proposed scheme.     

How to solve Lyapunov iterative equations

Original methods to solve an iterative sequence of Lyapunov equations are detailed. The first one is based on the eigenvalue–eigenvector approach. The second one considers the Schur reduction method. The third one takes into account the linearity of the equations. These methods are based on classical approaches, by optimizing the elapsed time by minimizing computation quantity. In fact, in classical approaches, there are some computations repeated in each iteration. The proposed approaches are based on the fact that these computations are executed just before the first iteration. In such case, a corresponding algorithm is developed, and is decomposed into two steps. The first step considers all common computations. In the second step, the solution is directly given at each iteration. Simulation results confirm the performance of the presented approaches, which decrease the computational quantity and increase the algorithm speed.     

A domain decomposition method for almost incompressible flow

A domain decomposition method for solving the Navier-Stokes equations for almost incompressible flow is examined. At the price of a nonuniform decomposition of the domain, we have fast solvers in all subdomains. Hence, each iteration on the Schur complement system can be performed very efficiently. We have shown theoretically that the method requires much fewer memory positions and arithmetic operations than a direct method. Numerical experiments show that the iteration on the Schur complement system converges very fast. We also show that the spatial grid ratio might be crucial for the performance of the method. Moreover, we show that for a given discretization of the problem, the rate of efficiency is larger than 100% for the problem studied here, due to the very nice parallelization properties of the algorithm.     

Solving linear systems in interior-point methods

There are two approaches to solve the linear systems in interior-point methods: the normal equation approach and the augmented system approach. We integrated the two methods by applying matrix partitioning to the augmented system approach. Specifically, we show the Schur complement method which is applied to problems with dense columns is a special case of the augmented system approach. We will use this property for the integrated approach. If we use the integrated approach, we can solve linear systems maintaining sparsity of matrices without respect of the existence of dense columns.Scope and purposeInterior-point methods require a step to solve the linear systems for computing a new direction at every iteration. Generally, we solve the linear systems by applying Cholesky factorization. When there is a dense column, we can not exploit the sparsity of matrices. The most popular way of treating such a dense column employs the Schur complement method or the augmented system approach. The Schur complement method is faster than the augmented system approach, but suffers from numerical unstability. We present a fast and numerically stable approach by integrating former approaches.