Research Reports for 2006

CSR 1-2006
The Numerical Prediction of Planar Viscoelastic Contraction Flows using the Pom-Pom Model and Higher-Order Finite Volume Schemes - Part II
J. P. Aguayo, P. M. Phillips, T. N. Phillips, H. R. Tamaddon-Jahromi, B. A. Snigerev and M. F. Webster
abstract    PDF
CSR 2-2006
Decomposing clause-sets: Integrating DLL algorithms, tree decompositions and hypergraph cuts for variable- and clause-based graph representations of CNF's
Marijn Heule and Oliver Kullmann
abstract    PDF
CSR 3-2006
Categorisation of clauses in conjunctive normal forms: Minimally unsatisfiable sub-clause-sets and the lean kernel
Oliver Kullmann, Inês Lynce and João Marques-Silva
abstract    PDF
CSR 4-2006
Excess pressure-drop estimation in contraction and expansion flows for constant viscosity, strain-hardening fluids
J. P. Aguayo, H. R. Tamaddon-Jahromi and M. F. Webster
abstract    PDF
CSR 5-2006
A study on Bautista-Manero models for worm-like micellar systems
J. P. Aguayo and M. F. Webster
abstract    PDF
CSR 6-2006
Evolutionary Morphing of Facial Images for Aging Simulation
Daniel Hubball, Min Chen and Phil W. Grant
abstract    PDF
CSR 7-2006
Logical Approaches to Computational Barriers
Arnold Beckmann, Ulrich Berger, Benedikt Löwe and John V. Tucker (editors)
abstract    PDF
CSR 8-2006
Alternative subcell discretisations for viscoelastic flow: Part I
F. Belblidia, H. Matallah, B. Puangkird and M. F. Webster
abstract    PDF
CSR 9-2006
Experimental computation of real numbers by Newtonian machines
E.J. Beggs and J.V. Tucker
abstract    PDF
CSR 10-2006
A General Approach for True Transient Computation of Viscoelastic Flows
I. J. Keshtiban, H. Tammadon-Jahromi and M. F. Webster
abstract    PDF
CSR 11-2006
Multi-mode simulation of filament stretching flows
H. Matallah, K.S. Sujatha, M.J. Banaai and M.F. Webster
abstract    PDF
CSR 12-2006
Modeling step-strain filament-stretching (CaBER-type) using ALE techniques
K.S.Sujatha, H.Matallah, M.J.Banaai and M.F.Webster
abstract    PDF
CSR 13-2006
Constraint satisfaction problems in clausal form: Autarkies, minimal unsatisfiability, and applications to hypergraph inequalities
Oliver Kullmann
abstract    PDF
CSR 14-2006
Division Safe Calculation in Totalised Fields
J A Bergstra and J V Tucker
abstract    PDF
CSR 15-2006
Reducibility of Domain Representations and Cantor-Weihrauch Domain Representations
J. Blanck
abstract    PDF
CSR 16-2006
Information Realisation: Textual, Graphical and Audial Representations of the Semantic Web
Owen Gilson, Nuno Silva, Phil W. Grant, Min Chen, João Rocha
abstract    PDF

CSR 1-2006 The Numerical Prediction of Planar Viscoelastic Contraction Flows using the Pom-Pom Model and Higher-Order Finite Volume Schemes - Part II

J. P. Aguayo, P. M. Phillips, T. N. Phillips, H. R. Tamaddon-Jahromi, B. A. Snigerev and M. F. Webster

This study investigates the numerical solution of viscoelastic flows using two contrasting high-order finite volume schemes. We extend our earlier work for Poiseuille flow in a planar channel and the single equation form of the extended pom-pom (SXPP) model, to determine steady-state solutions for planar 4:1 sharp contraction flows. The numerical techniques employed are time-stepping algorithms: one of hybrid finite element/volume type, the other of pure finite volume form. The pure finite volume scheme is a staggered-grid cell-centred scheme based on area-weighting and a semi-Lagrangian formulation. This may be implemented on structured or unstructured rectangular grids, utilising backtracking along the solution characteristics in time. For the hybrid scheme, we solve the momentum-continuity equations by a fractional-staged Taylor-Galerkin pressure-correction procedure and invoke a cell-vertex finite volume scheme for the constitutive law. A comparison of the two finite volume approaches is presented, concentrating upon the new features posed by the pom-pom class of models in this context of non-smooth flows. Here, the dominant feature of larger shear and extension in the entry zone influences both stress and stretch, so that larger stretch develops around the re-entrant corner zone as Weissenberg number increases, whilst correspondingly stress levels decline.
Report Titles


CSR 2-2006 Decomposing clause-sets: Integrating DLL algorithms, tree decompositions and hypergraph cuts for variable- and clause-based graph representations of CNF's

Marijn Heule and Oliver Kullmann

Applications of graph and hypergraph decomposition techniques to SAT solving have been studied under various conditions. Theoretical research focused on the direction given by tree decompositions, while practical approaches either integrated tree decomposition guidance into existing SAT solver, or studied splitting techniques using hypergraph cuts. In this article we present a uniform and general framework based on the splitting approach. We allow (and study) different graph representations, different graph and hypergraph splitting methods (involving vertices or (hyper)edges), different degrees of integration with the (full) problem structure, and various heuristics for selecting "good" decompositions. Basic is the notion of a decomposable graph representation. We show that resolution graphs (with only non-tautological resolvents(!)) yield a decomposable graph representation. Tree decomposition and variations have theoretical strength, but for practical purposes the (hyper)graph cut approach seems to be more suited, which is of a local nature, yielding one split at a time, while tree decomposition delivers one global scheme, from which all future splittings are derived. For (hyper)graph cuts even the weaker variation of resolution graphs, the conflict graphs (where also tautological resolvents are allowed), yield strictly better splitting possibilities than variable interaction graphs (at the expense of using bigger graphs). Very preliminary experimental results are given (yet mostly of negative nature).
Report Titles


CSR 3-2006 Categorisation of clauses in conjunctive normal forms: Minimally unsatisfiable sub-clause-sets and the lean kernel

Oliver Kullmann, Inês Lynce and João Marques-Silva

Finding out that a SAT problem instance F is unsatisfiable is not enough for applications, where good reasons are needed for explaining the inconsistency (so that for example the inconsistency may be repaired). Previous attempts of finding such good reasons focused on finding some minimally unsatisfiable sub-clause-set F' of F, which in general suffers from the non-uniqueness of F' (and thus it will only find some reason, albeit there might be others).

In our work, we develop a fuller approach, enabling a more fine-grained analysis of necessity and redundancy of clauses, supported by meaningful semantical and proof-theoretical characterisations. We combine known techniques for searching and enumerating minimally unsatisfiable subclause- sets with (full) autarky search. To illustrate our techniques, we give a detailed analysis of well-known industrial problem instances.
Report Titles


CSR 4-2006 Excess pressure-drop estimation in contraction and expansion flows for constant viscosity, strain-hardening fluids

J. P. Aguayo, H. R. Tamaddon-Jahromi and M. F. Webster

This article addresses the issue of reproducing quantitative pressure-drop predictions for constant shear-viscosity fluids in contraction and contraction/expansion flow geometries. Experimental observations on pressure-drop for severe strain-hardening Boger fluids reveal significant enhancement above Newtonian fluids in axisymmetric but not planar con gurations. This discrepancy has eluded predictive capability to date in contraction flows when utilising Oldroyd models. Here, we identify why this is so. The 4:1:4 contraction/expansion flow and adjustment of material parameters provides the key to resolving this dilemma in comparative form to the 4:1 counterpart problem. During the investigation, Oldroyd-B fluid compositions of various solvent:polymeric viscosity ratio splits are employed, alongside alternative strain-hardening model representations of Phan-Thien/Tanner and pom-pom type. A hybrid finite element/volume algorithm of incremental pressure-correction timestepping structure is utilised to elaborate solutions, reflecting some novel features with respect to the discrete treatment of pressure.
Report Titles


CSR 5-2006 A study on Bautista-Manero models for worm-like micellar systems

J. P. Aguayo and M. F. Webster

This study is concerned with the modelling of the Modified Bautista-Manero model (MBM) in planar channel and 4:1 contraction flow. The MBM model was proposed to represent the behaviour of worm-like micellar systems which has importance in industrial applications. An sensitivity analysis of the rheology is presented for this model. Here analytical solution for steady state planar channel flow shows an excellent agreement with a solution extracted via a Finite Difference implementation. Q vs. DP/L curves are included for a set of parameters. Schematic representation of shear-rate and velocity profiles at different flow rates indicate further detail in the interpretation of pressure-drop response. Transient solutions from start-up to steady state are also presented.
Report Titles


CSR 6-2006 Evolutionary Morphing of Facial Images for Aging Simulation

Daniel Hubball, Min Chen and Phil W. Grant

Aging has considerable effects on the appearance of the human face and is dif cult to simulate using a universally-applicable global model. In this paper, we present a data-driven framework for facial age progression (and regression) automatically in conjunction with a database of facial images. We build parameterized local models for face modeling, age-transformation and image warping based on a subset of imagery data selected according to an input image and associated metadata. In order to obtain a person-speci c mapping in the model space from an encoded face description to an encoded age-transformation, we employed genetic programming to automatically evolve a solution by learning from example transformations in the selected subset. In order to capture various factors that determine the in uence of feature points, we developed a new image warping algorithm based on non-uniform radial basis functions (NURBFs). A genetic algorithm was used to handle the large parameter space associated with NURBFs. With evolutionary computing, our approach is able to infer from the input and the database the most appropriate models to be used for transforming the input face. We compared our data-driven approach with the traditional global model approach. The noticeable improvement in terms of the resemblance between the output images and the actual target images (which are unknown to the process) demonstrated the effectiveness and usability of this new approach.
Report Titles


CSR 7-2006 Logical Approaches to Computational Barriers

Arnold Beckmann, Ulrich Berger, Benedikt Löwe and John V. Tucker (editors)

Computability in Europe (CiE) is an informal network of European scientists working on computability theory, including its foundations, technical development, and applications. Among the aims of the network is to advance our theoretical understanding of what can and cannot be computed, by any means of computation. Its scientific vision is broad: computations may be performed with discrete or continuous data by all kinds of algorithms, programs, and machines. Computations may be made by experimenting with any sort of physical system obeying the laws of a physical theory such as Newtonian mechanics, quantum theory or relativity. Computations may be very general, depending upon the foundations of set theory; or very specific, using the combinatorics of finite structures.CiE also works on subjects intimately related to computation, especially theories of data and information, and methods for formal reasoning about computations. The sources of new ideas and methods include practical developments in areas such as neural networks, quantum computation, natural computation, molecular computation, and computational learning. Applications are everywhere, especially, in algebra, analysis and geometry, or data types and programming.

This proceedings contains some of the talks given at the second CiE conference that was held at the Department of Computer Science, Swansea University, 30 June - 5 July, 2006.
Report Titles


CSR 8-2006 Alternative subcell discretisations for viscoelastic flow: Part I

F. Belblidia, H. Matallah, B. Puangkird and M. F. Webster

This study is concerned with the investigation of the associated properties of subcell discretisations for viscoelastic flows, where aspects of compatibility of solution function spaces are paramount. We introduce one new scheme, through a subcell finite element approximation fe(sc), and compare and contrast this against two precursor schemes – one with finite element discretisation in common, but at the parent element level quad-fe; the other, at the subcell level appealing to hybrid finite element/finite volume discretisation fe/fv(sc). To conduct our comparative study, we consider Oldroyd modelling and two classical steady benchmark flow problems to assess issues of numerical accuracy and stability - cavity flow and contraction flow. We are able to point to specific advantages of the finite element subcell discretisation and appreciate the characteristic properties of each discretisation, by analysing stress and flow field structure up to critical states of Weissenberg number. Findings reveal that the subcell linear approximation for stress within the constitutive equation (either feor fv) yields a more stable scheme, than that for its quadratic counterpart (quad-fe), whilst still maintaining third order accuracy. The more compatible form of stress interpolation within the momentum equation is found to be via the subcell elements under fe(sc); yet, this makes no difference under fe/fv(sc). Furthermore, improvements in solution representation are gathered through enhanced upwinding forms, which may be coupled to stability gains with strain-rate stabilisation.
Report Titles


CSR 9-2006 Experimental computation of real numbers by Newtonian machines

E.J. Beggs and J.V. Tucker

We prove that there is a 3-dimensional Newtonian machine which given any real number x &isin [0, 1] can generate an infinite sequence [pn, qn], for n=1,2, &hellip, of rational number interval approximations that converges to x as n &rarr &infin. The machine is a system for scattering and collecting particles. The theorem implies that every real number x &isin [0, 1] is computable by a simple Newtonian kinematic system that is bounded in space and mass and for which the calculation of the nth approximation of x takes place in O(n) time with O(n) energy.
Secondly, following a methodology we have proposed for analysing the nature of experimental computation, we describe a set of variants of the scatter machine and their kinematic subtheories; these refinements explain why our machine is non-deterministic.
Report Titles


CSR 10-2006 A General Approach for True Transient Computation of Viscoelastic Flows

I. J. Keshtiban, H. Tammadon-Jahromi and M. F. Webster

This article considers the problem of solving true-transient flows in planar contractions for Oldroyd-B and Pom-pom fluids. This is conducted through both controlled force and controlled flow-rate configurations, with comparison therein, considering consistency issues. To accomplish this task we employ a novel timedependent hybrid finite element/finite volume (fe/fv) algorithm. Such an approach combines an incremental pressure-correction fe-treatment for mass and momentum equations, with a cell-vertex fv-discretisation of the hyperbolic stress constitutive equation. In particular, we highlight differences in dynamic flow structure evolution within the field and its impact upon stress generation, as a consequence of the choice of driving flow conditions. The advantages of smooth flow transitions are highlighted under controlled-force configurations, in contrast to non-smooth states for controlled flow-rate scenarios.
Report Titles


CSR 11-2006 Multi-mode simulation of filament stretching flows

H. Matallah, K.S. Sujatha, M.J. Banaai and M.F. Webster

This study considers the continuous filament-stretching problem through a hybrid finite element/volume scheme. A range of strain-hardening fluid models are employed of Oldroyd- B, Giesekus, and linear Phan-Thien/Tanner form (LPTT). Both exponential and linear plateretraction rates are investigated, indicating their different dynamics. In addition, we compare and contrast single versus multi-mode modelling, pointing to the importance of each mode. The influence of multi-mode representation is made apparent through the stress components generated and consequences thereof. Results at large levels of Hencky-strain are presented, displaying symmetrical behaviour in axial stress. There is no sign of bead-like structure formation with either Giesekus or LPTT (ξ=0) solutions, in contrast to that apparent with the LPTT (ξ=0.13) counterpart.
Report Titles


CSR 12-2006 Modeling step-strain filament-stretching (CaBER-type) using ALE techniques

K.S.Sujatha, H.Matallah, M.J.Banaai and M.F.Webster

This paper discusses the numerical modeling of capillary breakup extensional rheometer procedures (CaBER) using Arbitrary Lagrangian/Eulerian (ALE) methods. Different models, fluid viscosities and aspect-ratios are studied, employing a hybrid finite element/finite volume spatial approach. Finite element discretisation is employed for the momentum and continuity equation, whilst a pure-upwinding cell-vertex finite volume representation is utilised for the hyperbolic stress equation. The results are validated against equivalent experimental results from the literature. By employing various constitutive models, we study viscoelastic response for some strain-hardening fluids in CaBER-type step-strain flows. In this instance, bead-like structures appear for filaments with high initial aspect-ratios. On the contrary, no bulges/beads are apparent for low polymeric viscosity Boger-type fluids (Oldroyd-B). This study elucidates the influence of surface tension and elastic forces upon these particular filament stretching flows.
Report Titles


CSR 13-2006 Constraint satisfaction problems in clausal form: Autarkies, minimal unsatisfiability, and applications to hypergraph inequalities

Oliver Kullmann

We investigate in depth a natural generalisation of boolean formulas in conjunctive normal forms (or 'clause-sets') allowing non-boolean variables; this generalisation is closely related to 'sets of no-goods' in the AI literature, and we will argue that it is the right generalisation of boolean clause-sets maintaining essential combinatorial properties. First we build up a solid foundation for (generalised) clause-sets, including the notion of autarky systems, the interplay between autarkies and resolution, and basic notions of (DP-)reductions. We obtain fixed parameter tractability (FPT) of satisfiability decision for generalised clause-sets, using as parameter a suitably generalised notion of maximal deficiency, where in the boolean case the deficiency is the difference between the number of clauses and the number of variables. Another central result in the boolean case regarding the deficiency is the classification of minimally unsatisfiable clause-sets with low deficiency (MU(1), MU(2), ...). We generalise the well-known characterisations of boolean MU(1). The proofs for FPT and MU(1) are not straight-forward, but are obtained by an interplay between suitable generalisations of techniques and notions from the boolean case, and exploiting combinatorial properties of the natural translation of (generalised) clause-sets into boolean clause-sets. Of fundamental importance here is autarky theory (autarkies are generalisations of satisfying assignments), and we concentrate especially on matching autarkies (based on matching theory) and special cases of linear autarkies (based on linear programming and linear algebra). Minimally unsatisfiable (generalised) clause-sets are 'lean', i.e., they do not admit non-trivial autarkies. Besides minimally unsatisfiable clause-sets we consider also 'irredundant' clause-sets, which allow for satisfiable clause-sets, with a special emphasise on 'hitting clause-sets' (which are irredundant in a very strong sense) and the generalisation to 'multihitting' clause-sets.

Autarky theory provides methods for deriving lower bounds on the deficiency δ(F) of generalised clause-sets F, where δ(F) relates the number of clauses and the number of variables of F, while the structural properties of minimally unsatisfiable (generalised) clause-sets enable classifications of minimally unsatisfiable clause-sets of low deficiency. Using the canonical translation of hypergraph colouring problems into (generalised) clause-sets, we are able to interprete classical basic results from hypergraph theory within this more general framework. We provide a general method for proving the existence of a matching in the bipartite graph of a hypergraph G covering all vertex nodes (if such a matching exists, then G must have at least as meany hyperedges as vertices). This methods allows to derive the (generalised) Fisher inequality, that a non-trivial pairwise balanced design must have as least as many blocks as points, as well as a the bound by Seymour, that a minimally non-2-colourable hypergraph must have at least as many hyperedges as vertices. Regarding Seymour’s inequality, without any additional work the result generalises to non-k-colourable hypergraphs for k≥2: Consider a hypergraph G and the canonical translation of the k-colouring problem for G into a (generalised) 'colouring' clause-set F[k](G). 'Minimally non k-colourability' of G is equivalent to F[k](G) being minimally unsatisfiable, a complicated and 'fragile' notion. But the lower bound on the deficiency on F[k](G) does actually not hinge on the minimal unsatisfiability, but only on the absence of a special class of linear autarkies (namely 'balanced linear autarkies'), and so we can use the 'smooth' generalisation of minimally unsatisfiable clause-sets by (balanced linearly) lean clause-sets. Finally we touch upon the characterisation of minimally unsatisfiable colouring clause-sets with minimal deficiency, recasting the characterisation of 'self-blocking square condensers' by Seymour.
Report Titles


CSR 14-2006 Division Safe Calculation in Totalised Fields

J A Bergstra and J V Tucker

A 0-totalised field is a field in which division is a total operation with 0-1=0. Equational reasoning in such fields is greatly simplified but in deriving a term one still wishes to know whether or not the calculation has invoked 0-1. If it has not then we call the derivation division-safe. We propose three methods of guaranteeing division-safe calculations in 0-totalised fields.
Report Titles


CSR 15-2006 Reducibility of Domain Representations and Cantor-Weihrauch Domain Representations

J. Blanck

A notion of (continuous) reducibility of representations of topological spaces is introduced and basic properties of this notion are studied for domain representations.

A representation reduces to another if its representingmap factors through the other representation. Reductions form a pre-order on representations. A spectrum is a class of representations divided by the equivalence relation induced by reductions. Representations belonging to the top element of a spectrum are said to be universal and these representations are the ones most closely capturing the structure of the represented space. Notion of admissibility considered both for domains and within Weihrauch's TTE are shown to be universality concepts in the appropriate spectra.

To illustrate the framework, some domain representations of real numbers are considered and it is shown that the usual interval domain representation, which is universal among dense representations, does not reduce to a binary expansion domain representation. However, a substructure of the interval domain more suitable for efficient computation of operations is on the other hand shown to be equivalent to the usual interval domain with respect to reducibility.
Report Titles


CSR 16-2006 Information Realisation: Textual, Graphical and Audial Representations of the Semantic Web

Owen Gilson, Nuno Silva, Phil W. Grant, Min Chen, João Rocha

Information Realisation is the process of presenting data as Textual, Graphical or Audial information to a human user. In this paper, we discuss the importance of this concept with respect to the accessibility of Semantic Web data to a diverse target audience. We provide an ontological point of view, defining the expressive characteristics and application domain of representation formats, thus presenting a system which produces representations customised to the user environment and the nature of the source data. Our approach considers the semantics of the data, not just the structure, and aims to present the information in the most semantically appropriate manner for the given target environment. We provide examples of a simple data set being realised as popular target representation formats: textual (XHTML, RSS); graphical (SVG, X3D); and audial (SoundML, VoiceXML).
Report Titles