GPU Acceleration of Partial Differential Equation Solvers

Differential equations are often directly solvable by analytical means only in their one dimensional version. Partial differential equations are generally not solvable by analytical means in two and three dimensions, with the exception of few special cases. In all other cases, numerical approximation methods need to be utilized. One of the most popular methods is the finite element method. The main areas of focus, here, are the Poisson heat equation and the plate bending equation. The purpose of this paper is to provide a quick walkthrough of the various approaches that the authors followed in pursuit of creating optimal solvers, accelerated with the use of graphical processing units, and comparing them in terms of accuracy and time efficiency with existing or self-made non-accelerated solvers.

Performance and Fault Tolerance of Preconditioned Iterative Solvers on Low-Power ARM Architectures

As the complexity of computing systems grows, reliability and energy are two crucial challenges asking for holistic solutions. In this paper, we investigate the interplay among concurrency, power dissipation, energy consumption and voltage-frequency scaling for a key numerical kernel for the solution of sparse linear systems. Concretely, we leverage a task-parallel implementation of the Conjugate Gradient method, equipped with an state-of-the-art pre-conditioner embedded in the ILUPACK software, and target a low-power multi core processor from ARM.In addition, we perform a theoretical analysis on the impact of a technique like Near Threshold Voltage Computing (NTVC) from the points of view of increased hardware concurrency and error rate.

Orbits of operators commuting with the Volterra operator

Asymptotic estimates of the norms of orbits of certain operators that commute with the classical Volterra operator V acting on L-P[0,1], with 1 0, but also to operators of the form phi (V), where phi is a holomorphic function at zero. The method to obtain the estimates is based on the fact that the Riemann-Liouville operator as well as the Volterra operator can be related to the Levin-Pfluger theory of holomorphic functions of completely regular growth. Different methods, such as the Denjoy-Carleman theorem, are needed to analyze the behavior of the orbits of I - cV, where c > 0. The results are applied to the study of cyclic properties of phi (V), where phi is a holomorphic function at 0.

Integral completeness of locally convex spaces

A locally convex space X is said to be integrally complete if each continuous mapping f: [0, 1] --> X is Riemann integrable. A criterion for integral completeness is established. Readily verifiable sufficient conditions of integral completeness are proved.

tts: A SAT-Solver for Small, Difficult Instances

The Ternary Tree Solver (tts) is a complete solver for propositional satisfiability which was designed to have good performance on the most difficult small instances. It uses a static ternary tree data structure to represent the simplified proposition under all permissible partial assignments and maintains a database of derived propositions known to be unsatisfiable. In the SAT2007 competition version 4.0 won the silver medal for the category handmade, speciality UNSAT solvers and was the top qualifier for the second stage for handmade benchmarks, solving 11 benchmarks which were not solved by any other entrant. We describe the methods used by the solver and analyse the competition Phase 1 results on small benchmarks. We propose a first version of a comprehensive suite of small difficult satisfiability benchmarks (sdsb) and compare the worst-case performance of the competition medallists on these benchmarks.

sgen1: A generator of small but difficult satisfiability benchmarks

The satisfiability problem is known to be NP-Complete; therefore, there should be relatively small problem instances that take a very long time to solve. However, most of the smaller benchmarks that were once thought challenging, especially the satisfiable ones, can be processed quickly by modern SAT-solvers. We describe and make available a generator that produces both unsatisfiable and, more significantly, satisfiable formulae that take longer to solve than any others known. At the two most recent international SAT Competitions, the smallest unsolved benchmarks were created by this generator. We analyze the results of all solvers in the most recent competition when applied to these benchmarks and also present our own more focused experiments.

Infinite Dimensional Banach spaces of functions with nonlinear properties

The aim of this paper is to show that there exist infinite dimensional Banach spaces of functions that, except for 0, satisfy properties that apparently should be destroyed by the linear combination of two of them. Three of these spaces are: a Banach space of differentiable functions on Rn failing the Denjoy-Clarkson property; a Banach space of non Riemann integrable bounded functions, but with antiderivative at each point of an interval; a Banach space of infinitely differentiable functions that vanish at infinity and are not the Fourier transform of any Lebesgue integrable function.

Transonic aeroelastic simulation for instability searches and uncertainty analysis

In this paper the use of eigenvalue stability analysis of very large dimension aeroelastic numerical models arising from the exploitation of computational fluid dynamics is reviewed. A formulation based on a block reduction of the system Jacobian proves powerful to allow various numerical algorithms to be exploited, including frequency domain solvers, reconstruction of a term describing the fluid–structure interaction from the sparse data which incurs the main computational cost, and sampling to place the expensive samples where they are most needed. The stability formulation also allows non-deterministic analysis to be carried out very efficiently through the use of an approximate Newton solver. Finally, the system eigenvectors are exploited to produce nonlinear and parameterised reduced order models for computing limit cycle responses. The performance of the methods is illustrated with results from a number of academic and large dimension aircraft test cases.

Modelling road traffic accidents using macroscopic second-order models of traffic flow

In this paper, we introduce a macroscopic model for road traffic accidents along highway sections. We discuss the motivation and the derivation of such a model, and we present its mathematical properties. The results are presented by means of examples where a section of a crowded one-way highway contains in the middle a cluster of drivers whose dynamics are prone to road traffic accidents. We discuss the coupling conditions and present some existence results of weak solutions to the associated Riemann Problems. Furthermore, we illustrate some features of the proposed model through some numerical simulations. © The authors 2012.

Zero-One Designs Produce Small Hard SAT Instances

Some basics of combinatorial block design are combined with certain constraint satisfaction problems of interest to the satisfiability community. The paper shows how such combinations lead to satisfiability problems, and shows empirically that these are some of the smallest very hard satisfiability problems ever constructed. Partially balanced (0,1) designs (PB01Ds) are introduced as an extension of balanced incomplete block designs (BIBDs) and (0,1) designs. Also, (0,1) difference sets are introduced as an extension of certain cyclical difference sets. Constructions based on (0,1) difference sets enable generation of PB01Ds over a much wider range of parameters than is possible for BIBDs. Building upon previous work of Spence, it is shown how PB01Ds lead to small, very hard, unsatisfiable formulas. A new three-dimensional form of combinatorial block design is introduced, and leads to small, very hard, satisfiable formulas. The methods are validated on solvers that performed well in the SAT 2009 and earlier competitions.

On the use of OpenFOAM to model Oscillating wave surge converters

The Computational Fluid Dynamic (CFD) toolbox OpenFOAM is used to assess the applicability of Reynolds-Averaged Navier-Stokes (RANS) solvers to the simulation of Oscillating Wave Surge Converters (OWSC) in significant waves. Simulation of these flap type devices requires the solution of the equations of motion and the representation of the OWSC’s motion in a moving mesh. A new way to simulate the sea floor inside a section of the moving mesh with a moving dissipation zone is presented. To assess the accuracy of the new solver, experiments are conducted in regular and irregular wave traces for a full three dimensional model. Results of acceleration and flow features are presented for numerical and experimental data. It is found that the new numerical model reproduces experimental results within the bounds of experimental accuracy.

Weakening Cardinality Constraints Creates Harder Satisfiability Benchmarks

For some time, the satisfiability formulae that have been the most difficult to solve for their size have been crafted to be unsatisfiable by the use of cardinality constraints. Recent solvers have introduced explicit checking of such constraints, rendering previously difficult formulae trivial to solve. A family of unsatisfiable formulae is described that is derived from the sgen4 family but cannot be solved using cardinality constraints detection and reasoning alone. These formulae were found to be the most difficult during the SAT2014 competition by a significant margin and include the shortest unsolved benchmark in the competition, sgen6-1200-5-1.cnf.

Improving the robustness of the iterative solver in state-space modelling of guitar distortion circuitry

Iterative solvers are required for the discrete-time simulation of nonlinear behaviour in analogue distortion circuits. Unfortunately,these methods are often computationally too expensive for realtime simulation. Two methods are presented which attempt to reduce the expense of iterative solvers. This is achieved by applying information that is derived from the specific form of the non linearity.The approach is first explained through the modelling of an asymmetrical diode clipper, and further exemplified by application to the Dallas Rangemaster Treble Booster guitar pedal, which provides an initial perspective of the performance on systems with multiple nonlinearities.