Parallel solution of a traffic flow simulation problem

Computational Fluid Dynamics (CFD) methods for solving traffic flow continuum models have been studied and efficiently implemented in traffic simulation codes in the past. This is the first time that such methods are studied from the point of view of parallel computing. We studied and implemented an implicit numerical method for solving the high-order flow conservation traffic model on parallel computers. Implicit methods allow much larger time-step than explicit methods, for the same accuracy. However, at each time-step a nonlinear system must be solved. We used the Newton method coupled with a linear iterative method (Orthomin). We accelerated the convergence of Orthomin with parallel incomplete LU factorization preconditionings. We ran simulation tests with real traffic data from an 12-mile freeway section (in Minnesota) on the nCUBE2 parallel computer. These tests gave the same accuracy as past tests, which were performed on one-processor computers, and the overall execution time was significantly reduced.     

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.     

A new iterative algorithm for solving H∞ control problem of continuous‐time Markovian jumping linear systems based on online implementation

A new online iterative algorithm for solving the H_∞ control problem of continuous‐time Markovian jumping linear systems is developed. For comparison, an available offline iterative algorithm for converging to the solution of the H_∞ control problem is firstly proposed. Based on the offline iterative algorithm and a new online decoupling technique named subsystems transformation method, a set of linear subsystems, which implementation in parallel, are obtained. By means of the adaptive dynamic programming technique, the two‐player zero‐sum game with the coupled game algebraic Riccati equation is solved online thereafter. The convergence of the novel policy iteration algorithm is also established. At last, simulation results have illustrated the effectiveness and applicability of these two methods. Copyright © 2016 John Wiley & Sons, Ltd.     

Further results on the preconditioned sor method

Several methods have been developed on the preconditioned iterative methodsi. e iterative methods applied to preconditioned linear systems. Usui, Kohno and Niki [4] have proposed the adaptive Gauss-Seidel (GS) method, and the same authors [5] have presented the pre-conditioned SOR method. They have shown, with the aid of numerical examples, that the two methods have a better rate of convergence in comparison with the classical SOR method. In this paper we will prove theoretically the improvement in the rate of convergence.     

Modified alternating direction-implicit iteration method for linear systems from the incompressible Navier–Stokes equations

In order to solve the large sparse systems of linear equations arising from numerical solutions of two-dimensional steady incompressible viscous flow problems in primitive variable formulation, Ran and Yuan [On modified block SSOR iteration methods for linear systems from steady incompressible viscous flow problems, Appl. Math. Comput. 217 (2010), pp. 3050–3068] presented the block symmetric successive over-relaxation (BSSOR) and the modified BSSOR iteration methods based on the special structures of the coefficient matrices. In this study, we present the modified alternating direction-implicit (MADI) iteration method for solving the linear systems. Under suitable conditions, we establish convergence theorems for the MADI iteration method. In addition, the optimal parameter involved in the MADI iteration method is estimated in detail. Numerical experiments show that the MADI iteration method is a feasible and effective iterative solver.     

Quotient convergence and multi-splitting methods for solving singular linear equations

Abstract   In this paper, we use the group inverse to characterize the quotient convergence of an iterative method for solving consistent singular linear systems, when the matrix index equals one. Next, we show that for stationary splitting iterative methods, the convergence and the quotient convergence are equivalent, which was first proved in [7]. Lastly, we propose a (multi-)splitting iterative method A=F–G, where the splitting matrix F may be singular, endowed with group inverse, by using F ^# as a solution tool for any iteration. In this direction, sufficient conditions for the quotient convergence of these methods are given. Then, by using the equivalence between convergence and quotient convergence, the classical convergence of these methods is proved. These latter results generalize Cao’s result, which was given for nonsingular splitting matrices F. Keywords: Group inverse, singular linear equations, iterative method, P-regular splitting, Hermitian positive definite matrix, multi-splitting, quotient convergence AMS Classification: 15A09, 65F35     

New gauss–seidel like block iterative methods to solve discrete boundary value problems

The concept of new Gauss–Seidel like iterative methods, which was introduced in [3], will be extended so as to obtain a class of convergent Gauss–Seidel like block iterative methods to solve linear matrix equations Ax=b with an M-Matrix A. New block iterative methods will be applied to finite difference approximations of the Laplace's equation on a square (“model problem” [8]) which surpass even the block successive overrelaxation iterative method with optimum relaxation factor in this example.     

Probabilistic robust design with linear quadratic regulators

In this paper, we study robust design of uncertain systems in a probabilistic setting by means of linear quadratic regulators (LQR). We consider systems affected by random bounded nonlinear uncertainty so that classical optimization methods based on linear matrix inequalities cannot be used without conservatism. The approach followed here is a blend of randomization techniques for the uncertainty together with convex optimization for the controller parameters. In particular, we propose an iterative algorithm for designing a controller which is based upon subgradient iterations. At each step of the sequence, we first generate a random sample and then we perform a subgradient step for a convex constraint defined by the LQR problem. The main result of the paper is to prove that this iterative algorithm provides a controller which quadratically stabilizes the uncertain system with probability one in a finite number of steps. In addition, at a fixed step, we compute a lower bound of the probability that a quadratically stabilizing controller is found.     

Numerical solution of fuzzy linear system

The aim of this paper is to present a numerical method for solving a general n×n fuzzy system of linear equations of the form Ax=b, where A is a crisp matrix and b an arbitrary fuzzy vector. We obtain the solution of n×n fuzzy linear systems by using Jacobi and Gauss-Seidel iterative methods and also show that the order of system will not be increased and the computing time will be shorter than other numerical methods. Finally, we illustrate this method by offering some numerical examples.     

The numerical solution of the time-dependent matrix equation A(t)V(t) + WA(t) = G(t)

A rapidly convergent iterative method for the solution of matrix equations of the form

A(t)V(t) + WA (t) = G(t)

is outlined. Such matrix equations arise in the study of parabolic systems and in the application of Lyapunov methods in the stability analysis of linear time-invariant systems. The desired solution at each time step is obtained by solving a comparatively small ordered matrix equation of the form

AV + WA=G rather than resorting to the conventional systems of linear algebraic equations with a composite coefficient matrix of order mn × mn.     

On model reduction of K-power bilinear systems

As a special type of bilinear systems, K-power bilinear systems have a special coupled structure that should be preserved in the process of model reduction. We investigate moment matching methods for K-power systems and extract structure-preserved reduced models from the perspective of bilinear systems and coupled systems. The optimal H₂ reduction is also considered for K-power systems. We prove that there exist reduced models satisfying the optimality conditions and meanwhile preserving the coupled structure of the original models. Furthermore, such reduced models can be produced by an iterative algorithm, or alternatively by a subsystem-iteration algorithm with less computational effort and faster convergence rate. Simulation results show that the proposed iterative algorithms possess superior performance in contrast to moment matching methods.     

Extension of fractional step techniques for incompressible flows: The preconditioned Orthomin(1) for the pressure Schur complement

The objective of this paper is to present different fractional step schemes in the algebraic context to solve the incompressible Navier–Stokes equations, test them and pick the best one in terms of efficiency and robustness. The equivalence between fractional step schemes and iterative methods for the pressure Schur complement system has been well established in the literature. For example, the classical incremental projection scheme can be associated with a Richardson iteration for the pressure Schur complement plus a correction to enforce the mass conservation. We introduce in this paper an Orthomin(1) iteration which minimizes the Schur complement residual at each solver iteration by using, in the updating step, a factor dynamically computed. Two versions are considered, namely the momentum preserving and continuity preserving versions. The method is compared to the classical Richardson method, including the continuity and momentum preserving versions. In addition, two Schur complement preconditioners are considered and compared, based on the approximation of the weak Uzawa operator. From the implementation point of view, the benefit of the method is two fold. On the one hand, it can be easily implemented starting from the global matrix of the monolithic scheme, without changing the assembly. On the other hand, it enables the use of simple algebraic solvers without the need for complex preconditioners; this is a requirement for massively parallel computers. The four methods are finally tested and compared through the solution of numerical examples. The main conclusion is that with very few additional computation, the Orthomin(1) iteration largely improves the global convergence properties of the fractional schemes here presented.     

On Accelerated Iterative Methods for the Solution of Systems of Linear Equations

In literature, it has been reported that the convergence of some preconditioned stationary iterative methods using certain type upper triangular matrices as preconditioners are faster than the basic iterative methods. In this paper, a new preconditioned iterative method for the numerical solution of linear systems has been introduced, and the convergence analysis of the proposed method and an existing one have been done. Some numerical examples have also been given, which show the effectiveness of both of the methods.     

基于策略迭代算法的连续时间线性Markov跳变系统非零和微分反馈Nash控制

针对一类连续时间线性Markov跳变系统,本文提出了一种新的策略迭代算法用于求解系统的非零和微分反馈Nash控制问题.通过求解耦合的数值迭代解,以获得具有线性动力学特性和无限时域二次成本的双层非零和微分策略的Nash均衡解.在每一个策略层,采用策略迭代算法来计算与每一组给定的反馈控制策略相关联的最小无限时域值函数.然后,通过子系统分解将Markov跳变系统分解为N个并行的子系统,并将该算法应用于跳变系统.本文提出的策略迭代算法可以很容易求解非零和微分策略所对应的耦合代数Riccati方程,且对高维系统有效.最后通过仿真示例证明了本文设计方法的有效性和可行性.     

Convergence of P-regular splitting iterative methods for non-Hermitian positive semidefinite linear systems

In this paper, we study the convergence of P-regular splitting iterative methods for singular and non-singular non-Hermitian positive semidefinite linear systems, which generalize the known results. Some numerical experiments are performed to illustrate the convergence results.     

线性系统求解中迭代算法的GPU加速方法

在求解线性系统时,迭代法是一种基本的方法,特别是在系数矩阵为大规模稀疏矩阵的情况下,高效地使用迭代法求解变得十分重要。本文通过分析迭代法的一般特点,提出了使用具有强大计算能力和存储带宽的GPU加速迭代法的一般方法。利用这些方法,在两种主流GPU平台上实现了一个经典的迭代法PQMRCGSTAB,并且针对不同的GPU平台特点提出了具体的优化方法。与AMD Opteron 2.4GHz 4核处理器相比,双精度版本的PQMRCGSTAB算法经NVIDIA Tesla S1070加速后性能提高31倍,经AMD Radeon HD 4870 X2加速后性能提高9倍。     

A projection method for the numerical solution of linear systems in separable stiff differential equations

This paper deals with the efficient implementation of implicit methods for solving stiff ODEs, in the case of Jacobians with separable sets of eigenvalues. For solving the linear systems required we propose a method which is particularly suitable when the large eigenvalues of the Jacobian matrix are few and well separated from the small ones. It is based on a combination of an initial iterative procedure, which reduces the components of the vector error along to the nondominant directions of J and a projection Krylov method which reduces the components of the vector error along to the directions corresponding to the large eigenvalues. The technique solves accurately and cheaply the linear systems in the Newton's method, and computes the number of stiff eigenvalues of J when this information is not explicitly available. Numerical results are given as well as comparisons with the LSODE code.     

Efficient parallelization of the iterative solution of a coupled fluid–structure interaction problem

In this paper we consider the parallelization of the generation and iterative solution of coupled linear systems modelling the interaction of an acoustic field in a fluid medium with an elastic structure immersed in the fluid. The particular case studied is that of a hollow steel sphere in water. The aim of the work is to speed up the generation and solution of the systems. We describe the methods used, which involve special sparse storage arrangements and a novel application of a sparse approximate inverse preconditioning technique, and present results showing that the methods are very effective in terms of speeding up the generation and iterative solution of the systems. Copyright © 2007 John Wiley & Sons, Ltd.     

Numerical computation of sign-indefinite linear quadratic differential games for weakly coupled large-scale systems

In this paper, N-player linear quadratic differential games that are sign-indefinite for infinite horizon weakly coupled large-scale systems are discussed. After establishing the asymptotic structure and local uniqueness of the solution for cross-coupled sign-indefinite algebraic Riccati equations (CSARE), a new algorithm for solving CSARE is provided. It is shown that the proposed algorithm attains linear convergence. Moreover, in order to reduce the computational workspace, the recursive algorithm is combined. Finally, a high-order approximation strategy based on the proposed iterative solutions is described. As a result, it was recently proved that the numerical strategy achieves a high-order approximation of the equilibrium value. As another important feature, when the small parameters are unknown, a parameter-independent strategy is developed.     

A numerical technique for the stability analysis of linear switched systems

In this paper the ray-gridding approach, a new numerical technique for the stability analysis of linear switched systems is presented. It is based on uniform partitions of the state-space in terms of ray directions which allow refinable families of polytopes of adjustable complexity to be examined for invariance. In this framework the existence of a polyhedral Lyapunov function that is common to a family of asymptotically stable subsystems can be checked efficiently via simple iterative algorithms. The technique can be used to prove the stability of switched linear systems, classes of linear time-varying systems and linear differential lnclusions. We also present preliminary results on another related problem; namely, the construction of multiple polyhedral Lyapunov functions for the specification of stabilizing switching sequences for a switched system constructed from a family of stable linear subsystems.