Code verification for governing equations with arbitrary functions using adjusted method of manufactured solutions

A new, adjusted approach to code verification using the method of manufactured solutions is presented. It is applicable for the physical problems, represented by mathematical models that include partial differential governing equations, which contain one or more functions that can vary from case to case. For the verification of such codes it has to be presumed that the varying functions are arbitrary and that is why this adjusted method is called the MMS-A. The aim of the new approach is further simplification of the existing methods that can become complex, time consuming and less convenient in general, when used for problems with arbitrary functions. With some additional programming the MMS-A can also be used for verifying codes, in which it is difficult to access the right-hand side of the governing equations (black box codes). In the present article the new method is described in detail and it is compared to the original method of manufactured solutions. It is demonstrated that using the MMS-A, the additional source term can be omitted. The use of the MMS-A is shown through examples that display the effectiveness of the new method.     

Distributed optimization with arbitrary local solvers

With the growth of data and necessity for distributed optimization methods, solvers that work well on a single machine must be re-designed to leverage distributed computation. Recent work in this area has been limited by focusing heavily on developing highly specific methods for the distributed environment. These special-purpose methods are often unable to fully leverage the competitive performance of their well-tuned and customized single machine counterparts. Further, they are unable to easily integrate improvements that continue to be made to single machine methods. To this end, we present a framework for distributed optimization that both allows the flexibility of arbitrary solvers to be used on each (single) machine locally and yet maintains competitive performance against other state-of-the-art special-purpose distributed methods. We give strong primal–dual convergence rate guarantees for our framework that hold for arbitrary local solvers. We demonstrate the impact of local solver selection both theoretically and in an extensive experimental comparison. Finally, we provide thorough implementation details for our framework, highlighting areas for practical performance gains.     

Iterative Toeplitz solvers with local quadratic convergence

We study an iterative, locally quadratically convergent algorithm for solving Toeplitz systems of equations from [R. P. Brent, F. G. Gustavson and D. Y. Y. Yun. “Fast solution of Toeplitz systems of equations and computation of Padé approximations”,J. Algorithms, 1:259–295, 1980]. We introduce a new iterative algorithm that is locally quadratically convergent when used to solve symmetric positive definite Toeplitz systems. We present a set of numerical experiments on randomly generated symmetric positive definite Toeplitz matrices. In these experiments, our algorithm performed significantly better than the previously proposed algorithm.     

Monte Carlo linear solvers with non-diagonal splitting

Monte Carlo (MC) linear solvers can be considered stochastic realizations of deterministic stationary iterative processes. That is, they estimate the result of a stationary iterative technique for solving linear systems. There are typically two sources of errors: (i) those from the underlying deterministic iterative process and (ii) those from the MC process that performs the estimation. Much progress has been made in reducing the stochastic errors of the MC process. However, MC linear solvers suffer from the drawback that, due to efficiency considerations, they are usually stochastic realizations of the Jacobi method (a diagonal splitting), which has poor convergence properties. This has limited the application of MC linear solvers. The main goal of this paper is to show that efficient MC implementations of non-diagonal splittings too are feasible, by constructing efficient implementations for one such splitting. As a secondary objective, we also derive conditions under which this scheme can perform better than MC Jacobi, and demonstrate this experimentally. The significance of this work lies in proposing an approach that can lead to efficient MC implementations of a wider variety of deterministic iterative processes.     

MASA : a library for verification using manufactured and analytical solutions

In this paper we introduce the Manufactured Analytical Solution Abstraction ( MASA ) library for applying the method of manufactured solutions to the verification of software used for solving a large class of problems stemming from numerical methods in mathematical physics including nonlinear equations, systems of algebraic equations, and ordinary and partial differential equations. We discuss the process of scientific software verification, manufactured solution generation using symbolic manipulation with computer algebra systems such as Maple? or SymPy, and automatic differentiation for forcing function evaluation. We discuss a hierarchic methodology that can be used to alleviate the combinatorial complexity in generating symbolic manufactured solutions for systems of equations based on complex physics. Finally, we detail the essential features and examples of the Application Programming Interface behind MASA , an open source library designed to act as a central repository for manufactured and analytical solutions over a diverse range of problems.     

Evaluation of numerical error estimation based on grid refinement studies with the method of the manufactured solutions

This article presents a study on the estimation of the numerical uncertainty based on grid refinement studies with the method of manufactured solutions. The availability of an exact solution and the convergence of the numerical solution to machine accuracy allow the determination of the exact error and of the distinct contributions of the iterative and discretization errors. The study focuses on three different problems of error/uncertainty evaluation (the uncertainty is in this case the error multiplied by a safety factor): the estimation of the iterative error/uncertainty; the influence of the iterative error on the estimation of the discretization error/uncertainty, and the overall numerical error/uncertainty as a combination of the iterative and discretization errors. The results obtained in this study show that it is possible to obtain a reliable iterative error estimator based on a geometric-progression extrapolation of the L_∞ norm of the differences between iterations. In order to obtain a negligible influence of the iterative error on the estimation of the discretization error, the iterative error must be two to three orders of magnitude smaller than the discretization error. If the iterative error is non-negligible it should be added, simply arithmetically, to the discretization error to obtain a reliable estimate of the numerical error; combining by RMS is not conservative.     

Bounded model checking of software using SMT solvers instead of SAT solvers

C bounded model checking (cbmc) has proved to be a successful approach to automatic software analysis. The key idea is to (i) build a propositional formula whose models correspond to program traces (of bounded length) that violate some given property and (ii) use state-of-the-art SAT solvers to check the resulting formulae for satisfiability. In this paper, we propose a generalisation of the cbmc approach on the basis of an encoding into richer (but still decidable) theories than propositional logic. We show that our approach may lead to considerably more compact formulae than those obtained with cbmc. We have built a prototype implementation of our technique that uses a satisfiability modulo theories (SMT) solver to solve the resulting formulae. Computer experiments indicate that our approach compares favourably with—and on some significant problems outperforms—cbmc.     

MOL solvers for hyperbolic PDEs with source terms

A method-of-lines solution algorithm for reacting flow problems modelled by hyperbolic partial differential equations (PDEs) with stiff source terms is presented. Monotonicity preserving advection schemes are combined with space/time error balancing and a Gauss–Seidel iteration to provide an efficient solver. Numerical experiments on two challenging examples are presented to illustrate the performance of the method.     

Verification and validation of RANS maneuvering simulation of Esso Osaka: effects of drift and rudder angle on forces and moments

The present work covers rigorous verification and validation of a Reynolds averaged Navier–Stokes (RANS) code applied to a maneuvering problem covering the “static rudder” and “pure drift” conditions. The objectives are: (1) to apply the RANS technology together with the Chimera grid technique to compute the hydrodynamic forces acting on the bare hull and the appended hull of the tanker Esso Osaka during simple maneuvers; (2) to provide detailed information about the levels of verification and validation for the integral quantities; (3) to develop a procedure for generation of the systematically refined Chimera grids, which are used for the verification; and (4) to provide information about the trends in the forces and moments when the rudder and drift angles are varied. The flow problem is solved by the general-purpose RANS code CFDSHIP-IOWA, which is run in steady mode. The effect of the free surface is neglected and the two-equation k–ω model, models the turbulence. The verification and validation are performed by means of one of the latest approaches. It takes both the numerical and experimental uncertainties and errors into account, when the method is validated. The verification and validation of the forces and moments show that fair levels of verification and validation are established for most of the considered cases. A brief summary of the levels validation says that the bare hull results are validated at levels from 4.2% to 9.3%. For the appended hull the levels of validation for the rudder forces and the overall forces and moments range from 3.4% to 28.0% and from 6.3% to 37.2% for the “static rudder” and “pure drift” conditions, respectively. Further, it appears that even though validation is not achieved for all the cases, the method is generally capable of capturing the overall behavior of the integral quantities when the rudder and drift angles are varied.     

Adjoint RANS with filtered shape derivatives for hydrodynamic optimisation

The adjoint RANS method has been implemented in the framework of an unstructured general-purpose finite volume code following the derive-then-discretise strategy (continuous adjoint approach). An explicit filtering technique is applied to the shape derivatives in order to extract noise from the mesh-based representation of high-resolution. In a CAD-free optimisation strategy the method is applied to a semi-circular profile in incompressible, external flow. It was observed that the filtering is particularly relevant at high Reynolds-numbers. In the complex scenario of ship hull design, the filtered shape derivative can directly be applied to the base-line configuration in order to support both manual and automatic shape optimisation.     

Comparison of Eulerian Vlasov solvers

Vlasov methods, which instead of following the particle trajectories, solve directly the Vlasov equation on a grid of phase space have proven to be an efficient alternative to the Particle-In-Cell method for some specific problems. Such methods are useful, in particular, to obtain high precision in regions where the distribution function is small.Gridded Vlasov methods have the advantage of being completely free of numerical noise, however the discrete formulations contain some other numerical artifacts, like diffusion or dissipation. We shall compare in this paper different types of methods for solving the Vlasov equation on a grid in phase space: the semi-Lagrangian method, the finite volume method, the spectral method, and a method based on a finite difference scheme, conserving exactly several invariants of the system. Moreover, for each of those classes of methods, we shall first compare different interpolation or reconstruction procedures. Then we shall investigate the cost in memory as well as in CPU time which is a very important issue because of the size of the problem defined on the phase space.     

Application of the method of manufactured solutions to the verification of a pressure-based finite-volume numerical scheme

The present study reports a numerical procedure based on a series of tests that make use of the method of manufactured solutions (MMS) and allow to evaluate the effective numerical performance with respect to the theoretical order of accuracy. The method is applied to a pressure-based finite volume numerical scheme suited to variable density flows representative of those encountered in combustion applications. The algorithm is based on a predictor-corrector time integration scheme that employs a projection method for the momentum equations. A physically consistent constraint is retained to ensure that the velocity field is solved correctly. The MMS application shows that the combination of this velocity constraint and the variable-coefficient Poisson solver is of fundamental importance to ensure both the numerical stability and the expected order of accuracy. Especially, the resort to an inner iteration procedure gives rise to undeniable improvements in terms of both the order of accuracy and error magnitude. The MMS applications confirm the interest of the method to conduct a preliminary check of the performance of any numerical algorithm applied to both fully incompressible and variable density flows. Finally, the analysis is ended by the application of the retained pressure-based finite-volume scheme to the numerical simulation of mixing layers featuring increasing values of the density contrast. The corresponding results shed some light onto the stability and robustness of the numerical scheme, important issues that are not addressed through MMS analyses.     

A survey of point-based POMDP solvers

The past decade has seen a significant breakthrough in research on solving partially observable Markov decision processes (POMDPs). Where past solvers could not scale beyond perhaps a dozen states, modern solvers can handle complex domains with many thousands of states. This breakthrough was mainly due to the idea of restricting value function computations to a finite subset of the belief space, permitting only local value updates for this subset. This approach, known as point-based value iteration, avoids the exponential growth of the value function, and is thus applicable for domains with longer horizons, even with relatively large state spaces. Many extensions were suggested to this basic idea, focusing on various aspects of the algorithm—mainly the selection of the belief space subset, and the order of value function updates. In this survey, we walk the reader through the fundamentals of point-based value iteration, explaining the main concepts and ideas. Then, we survey the major extensions to the basic algorithm, discussing their merits. Finally, we include an extensive empirical analysis using well known benchmarks, in order to shed light on the strengths and limitations of the various approaches.     

Asymptotic solvers for second-order differential equation systems with multiple frequencies

In this paper, an asymptotic expansion is constructed to solve second-order differential equation systems with highly oscillatory forcing terms involving multiple frequencies. An asymptotic expansion is derived in inverse of powers of the oscillatory parameter and its truncation results in a very effective method of dicretizing the differential equation system in question. Numerical experiments illustrate the effectiveness of the asymptotic method in contrast to the standard Runge–Kutta method.     

Scientific applications of iterative Toeplitz solvers

Recent research on using the preconditioned conjugate gradient method as an iterative method for solving Toeplitz systems has brought much attention. One of the main important results of this methodology is that the complexity of solving a large class of Toeplitz systems can be reduced toO (n logn) operations as compared to theO(n log² n) operations required by fast direct Toeplitz solvers, provided that a suitable preconditioner is chosen under certain conditions on the Toeplitz operator. In this paper, we survery some applications of iterative Toeplitz solvers to Toeplitz-related problems arising from scientific applications. These applications include partial differential equations, queueing networks, signal and image processing, integral equations, and time series analysis. Research supported by the Cooperative Research Centre for Advanced Computational Systems. Research supported in part by HKRGC grants no. CUHK 316/94E.     

Coupling solvers with model transformations to generate explorable model sets

Software and Systems Modeling - Model transformation is an effective technique to produce target models from source models. Most transformation approaches focus on generating a single target model...     

Some fourth-order nonlinear solvers with closed formulae for multiple roots

In this paper, we present six new fourth-order methods with closed formulae for finding multiple roots of nonlinear equations. The first four of them require one-function and three-derivative evaluation per iteration. The last two require one-function and two-derivative evaluation per iteration. Several numerical examples are given to show the performance of the presented methods compared with some known methods.     

On the error control in ODE solvers with local extrapolation

Jackson, Enright, and Hull have analytically assessed the effectiveness of RK-algorithms for linear ODEs with constant coefficients. Their results may carry over to more general problems if a certain relation between the local error estimate and the true local error of the algorithm continues to hold. Numerical investigation of this relation for a code which performs local extrapolation gives some insight in the performance of the error control mechanism of such codes.     

On the verification of polynomial system solvers

We discuss the verification of mathematical software solving polynomial systems symbolically by way of triangular decomposition. Standard verification techniques are highly resource consuming and apply only to polynomial systems which are easy to solve. We exhibit a new approach which manipulates constructible sets represented by regular systems. We provide comparative benchmarks of different verification procedures applied to four solvers on a large set of well-known polynomial systems. Our experimental results illustrate the high efficiency of our new approach. In particular, we are able to verify triangular decompositions of polynomial systems which are not easy to solve.