One-step 5-stage Hermite-Birkhoff-Taylor ODE solver of order 12

A one-step 5-stage Hermite-Birkhoff-Taylor method, HBT(12)5, of order 12 is constructed for solving nonstiff systems of differential equations y^′=f(t,y), y(t₀)=y₀, where y∈Rⁿ. The method uses derivatives y^′ to y⁽⁹⁾ as in Taylor methods combined with a 5-stage Runge-Kutta method. Forcing an expansion of the numerical solution to agree with a Taylor expansion of the true solution to order 12 leads to Taylor- and Runge-Kutta-type order conditions which are reorganized into Vandermonde-type linear systems whose solutions are the coefficients of the method. HBT(12)5 has a larger interval of absolute stability than Dormand-Prince DP(8, 7)13M and Taylor method T12 of order 12. The new method has also a smaller norm of principal error term than T12. It is superior to DP(8, 7)13M and T12 on the basis the number of steps, CPU time and maximum global error on common test problems. The formulae of HBT(12)5 are listed in an appendix.     

A one-step 7-stage Hermite-Birkhoff-Taylor ODE solver of order 11

A one-step 7-stage Hermite-Birkhoff-Taylor method of order 11, denoted by HBT(11)7, is constructed for solving nonstiff first-order initial value problems y^′=f(t,y), y(t₀)=y₀. The method adds the derivatives y^′ to y⁽⁶⁾, used in Taylor methods, to a 7-stage Runge-Kutta method of order 6. Forcing an expansion of the numerical solution to agree with a Taylor expansion of the true solution to order 11 leads to Taylor- and Runge-Kutta-type order conditions. These conditions are reorganized into Vandermonde-type linear systems whose solutions are the coefficients of the method. The new method has a larger scaled interval of absolute stability than the Dormand-Prince DP87 and a larger unscaled interval of absolute stability than the Taylor method, T11, of order 11. HBT(11)7 is superior to DP87 and T11 in solving several problems often used to test higher-order ODE solvers on the basis of the number of steps, CPU time, and maximum global error. Numerical results show the benefit of adding high-order derivatives to Runge-Kutta methods.     

A domain-decomposing parallel sparse linear system solver

The solution of large sparse linear systems is often the most time-consuming part of many science and engineering applications. Computational fluid dynamics, circuit simulation, power network analysis, and material science are just a few examples of the application areas in which large sparse linear systems need to be solved effectively. In this paper, we introduce a new parallel hybrid sparse linear system solver for distributed memory architectures that contains both direct and iterative components. We show that by using our solver one can alleviate the drawbacks of direct and iterative solvers, achieving better scalability than with direct solvers and more robustness than with classical preconditioned iterative solvers. Comparisons to well-known direct and iterative solvers on a parallel architecture are provided.     

A parallel stiff ODE solver based on MIRKs

A parallel, "across the method" implementation of a stiff ODE solver is presented. The construction of the methods is outlined and the main implementational issues are discussed. Performance results, using MPI on the IBM SP-2, are presented and they indicate that a speed-up between 3 and 5 typically can be obtained compared to state-of-the-art sequential codes.     

Existence for a semilinear sixth-order ODE

In this paper we study the existence and multiplicity of nontrivial solutions for a boundary value problem associated with a semilinear sixth-order ordinary differential equation arising in the study of spatial patterns. Our treatment is based on variational tools, including two Brezis-Nirenberg's linking theorems.     

A stable, direct solver for the gradient equation

A new finite element discretization of the equation is introduced. This discretization gives rise to an invertible system that can be solved directly, requiring a number of operations proportional to the number of unknowns. We prove an optimal error estimate, and furthermore show that the method is stable with respect to perturbations of the right-hand side . We discuss a number of applications related to the Stokes equations.

     

A stochastic approach to global error estimation in ODE multistep numerical integration

In order to assess the quality of approximate solutions obtained in the numerical integration of ordinary differential equations related to initial-value problems, there are available procedures which lead to deterministic estimates of global errors. The aim of this paper is to propose a stochastic approach to estimate the global errors, especially in the situations of integration which are often met in flight mechanics and control problems. Treating the global errors in terms of their orders of magnitude, the proposed procedure models the errors through the distribution of zero-mean random variables belonging to stochastic sequences, which take into account the influence of both local truncation and round-off errors. The dispersions of these random variables, in terms of their variances, are assumed to give an estimation of the errors. The error estimation procedure is developed for Adams-Bashforth-Moulton type of multistep methods. The computational effort in integrating the variational equations to propagate the error covariance matrix associated with error magnitudes and correlations is minimized by employing a low-order (first or second) Euler method. The diagonal variances of the covariance matrix, derived using the stochastic approach developed in this paper, are found to furnish reasonably precise measures of the orders of magnitude of accumulated global errors in short-term as well as long-term orbit propagations.     

Performance comparison of the NWF and DC methods for implementing High-Resolution schemes in a fully coupled incompressible flow solver

This paper reports on the use of the Normalized Weighting Factor (NWF) method and the Deferred Correction (DC) approach for the implementation of High Resolution (HR) convective schemes in an implicit, fully coupled, pressure-based flow solver. Four HR schemes are realized within the framework of the NWF and DC methods and employed to solve the following three laminar flow problems: (i) lid-driven flow in a square cavity, (ii) sudden expansion in a square cavity, and (iii) flow in a planar T-junction, over three grid systems with sizes of 10⁴, 5 × 10⁴, and 3 × 10⁵ control volumes. The merit of both approaches is demonstrated by comparing the computational costs required to solve these problems using the various HR schemes on the different grid systems. Whereas previous attempts to use the NWF method in a segregated flow solver failed to produce converged solutions, current results clearly demonstrate that both methods are suitable for utilization in a coupled flow solver. In terms of CPU efficiency, there is no global and consistent superiority of any method over another even though the DC method outperformed the NWF method in two of the three test problems solved.     

Roe solver with entropy corrector for uncertain hyperbolic systems

This paper deals with intrusive Galerkin projection methods with a Roe-type solver for treating uncertain hyperbolic systems using a finite volume discretization in physical space and a piecewise continuous representation at the stochastic level. The aim of this paper is to design a cost-effective adaptation of the deterministic Dubois and Mehlman corrector to avoid entropy-violating shocks in the presence of sonic points. The adaptation relies on an estimate of the eigenvalues and eigenvectors of the Galerkin Jacobian matrix of the deterministic system of the stochastic modes of the solution and on a correspondence between these approximate eigenvalues and eigenvectors for the intermediate states considered at the interface. We derive some indicators that can be used to decide where a correction is needed, thereby reducing the computational costs considerably. The effectiveness of the proposed corrector is assessed on the Burgers and Euler equations including sonic points.     

A unified solution framework for multi-attribute vehicle routing problems

Vehicle routing attributes are extra characteristics and decisions that complement the academic problem formulations and aim to properly account for real-life application needs. Hundreds of methods have been introduced in recent years for specific attributes, but the development of a single, general-purpose algorithm, which is both efficient and applicable to a wide family of variants remains a considerable challenge. Yet, such a development is critical for understanding the proper impact of attributes on resolution approaches, and to answer the needs of actual applications. This paper contributes towards addressing these challenges with a component-based design for heuristics, targeting multi-attribute vehicle routing problems, and an efficient general-purpose solver. The proposed Unified Hybrid Genetic Search metaheuristic relies on problem-independent unified local search, genetic operators, and advanced diversity management methods. Problem specifics are confined to a limited part of the method and are addressed by means of assignment, sequencing, and route-evaluation components, which are automatically selected and adapted and provide the fundamental operators to manage attribute specificities. Extensive computational experiments on 29 prominent vehicle routing variants, 42 benchmark instance sets and overall 1099 instances, demonstrate the remarkable performance of the method which matches or outperforms the current state-of-the-art problem-tailored algorithms. Thus, generality does not necessarily go against efficiency for these problem classes.     

A comparison of some ODE solvers which require Jacobian evaluations

A variety of third-order ODE solvers which have a minimum configuration (i.e. minimum work per step) have been numerically tested and the results compared. They include implicit and explicit processes, and share the property that a Jacobian matrix must be evaluated at least once during the integration. Some of these processes have not been previously described in the literature.     

Torsion-free path geometries and integrable second order ODE systems

A search for invariants of second order ODE systems under the class of point transformations, which mix the parameter and the dependent variables, uncovers a torsion tensor generalizing part of the curvature tensor of an affine connection. We study the geometry of ODE systems for which this torsion vanishes. These are the ODE systems for which deformations of solutions fixing a point constitute a field of Segré varieties in the tangent bundle of the locally defined space of solutions. Conversely, a field of Segré varieties for which certain differential invariants vanish induces a torsion-free ODE system on the space of solutions to a natural PDE system. The geometry on the solution space is used to produce first integrals for torsion-free ODE systems, given as algebraic invariants of a curvature tensor involving up to fourth derivatives of the equations. In the generic case, there are enough first integrals to solve the equations explicitly in spite of the absence of symmetry. In the case of torsion-free ODE pairs, the field of Segré varieties is equivalent to a half-flat split signature conformal structure, and we characterize in terms of curvature those systems having an abundance of totally geodesic surfaces.     

A robust kernel-based solver for variable-order time fractional PDEs under 2D/3D irregular domains

This study presents a robust kernel-based collocation method (KBCM) for solving multi-term variable-order time fractional partial differential equations (VOTFPDEs). In the proposed method, Radial basis functions (RBFs) and Muntz polynomials basis (MPB) are implemented to discretize the spatial and temporal derivative terms in the VOTFPDEs, respectively. Due to the properties of the RBFs, the spatial discretization in the proposed method is mathematically simple and truly meshless, which avoids troublesome mesh generation for high-dimensional problems involving irregular geometries. Due to the properties of the MPB, only few temporal discretization is required to achieve the satisfactory accuracy. Numerical efficiency of the proposed method is investigated under several typical examples.     

A fourth‐order Hermitian box‐scheme with fast solver for the Poisson problem in a cube

We present a fourth‐order Hermitian box‐scheme (HB‐scheme) for the Poisson problem in a cube. A single‐nonstaggered regular grid is used supporting the discrete unknowns u and . The scheme is fourth‐order accurate for u and in norm. The fast numerical resolution uses a matrix capacitance method, resulting in a computational complexity of . Numerical results are reported on several examples including nonseparable problems. The present scheme is the extension to the three‐dimensional case of the HB‐scheme presented in Abbas and Croisille [J Sci Comp 49 (2011), 239–267]. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 609–629, 2015     

A Gauss-Seidel type solver for special convex programs,with application to frictional contact mechanics

An iterative method is described that solves the constrained minimization of a convex function, when the constraintsg _j(x ₁,...,x _n)0 are functions of only a few variables and can be partitioned in some way. A proof of convergence is given which is based on the fact that the function values that are generated decrease. The relation to the nonlinear equation solver TanGS is shown (Ref. 1), together with some new results for TanGS. Finally, the solver is applied to the solution of tangential traction in contact mechanics.     

A Rigorous ODE Solver and Smale's 14th Problem

We present an algorithm for computing rigorous solutions to a large class of ordinary differential equations. The main algorithm is based on a partitioning process and the use of interval arithmetic with directed rounding. As an application, we prove that the Lorenz equations support a strange attractor, as conjectured by Edward Lorenz in 1963. This conjecture was recently listed by Steven Smale as one of several challenging problems for the twenty-first century. We also prove that the attractor is robust, i.e., it persists under small perturbations of the coefficients in the underlying differential equations. Furthermore, the flow of the equations admits a unique SRB measure, whose support coincides with the attractor. The proof is based on a combination of normal form theory and rigorous computations. July 27, 2000. Final version received: June 30, 2001.     

A set of procedures making real arithmetic of unlimited accuracy possible within ALGOL 60

The facilities to perform floating point arithmetic of unlimited accuracy and to continuously control the round-off error are often found desirable. The paper describes how the authors have implemented this feature using the ALGOL 60 procedure concept.     

求一类常系数线性常微分方程特解的有限递推法

对于非齐次项为多项式,指数函数,正(余)弦函数,或它们的乘积形式的常系数线性常微分方程,提出了求其特解的有限递推法.它方法统一,计算简洁,便于编程,能解决高阶问题,能在有限步内得出方程的解析特解,因而优于目前广泛采用的待定系数法.     

A GENERATOR AND A SIMPLEX SOLVER FOR NETWORK PIECEWISE LINEAR PROGRAMS

ＡＧＥＮＥＲＡＴＯＲＡＮＤＡＳＩＭＰＬＥＸＳＯＬＶＥＲＦＯＲＮＥＴＷＯＲＫＰＩＥＣＥＷＩＳＥＬＩＮＥＡＲＰＲＯＧＲＡＭＳＳＵＮＪＩＥ（孙捷）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉ...     

A preconditioned MinRes solver for time‐periodic parabolic optimal control problems

This work is devoted to the multiharmonic analysis of parabolic optimal control problems in a time‐periodic setting. In contrast to previous approaches, we include the cases of different control and observation domains, the observation in certain energy spaces, and the presence of control constraints. In all these cases, we propose a new preconditioned MinRes solver for the frequency domain equations and show that this solver is robust with respect to the space and time discretization parameters as well as the involved ‘bad’ model parameters of the state equation. Copyright © 2012 John Wiley & Sons, Ltd.