Multiphase mesh partitioning

We consider the load-balancing problems which arise from parallel scientific codes containing multiple computational phases, or loops over subsets of the data, which are separated by global synchronisation points. We motivate, derive and describe the implementation of an approach which we refer to as the multiphase mesh partitioning strategy to address such issues. The technique is tested on several examples of meshes, both real and artificial, containing multiple computational phases and it is demonstrated that our method can achieve high quality partitions where a standard mesh partitioning approach fails.

A knowledge-based system to represent spatial reasoning for fire modelling

This paper describes the architecture of the knowledge based system (KBS) component of Smartfire, a fire field modelling tool for use by members of the fire safety engineering community who are not expert in modelling techniques. The KBS captures the qualitative reasoning of an experienced modeller in the assessment of room geometries, so as to set up the important initial parameters of the problem. Fire modelling expertise is an example of geometric and spatial reasoning, which raises representational problems. The approach taken in this project is a qualitative representation of geometric room information based on Forbus’ concept of a metric diagram. This takes the form of a coarse grid, partitioning the domain in each of the three spatial dimensions. Inference over the representation is performed using a case-based reasoning (CBR) component. The CBR component stores example partitions with key set-up parameters; this paper concentrates on the key parameter of grid cell distribution.

A generational scheme for partitioning graphs

Graph partitioning divides a graph into several pieces by cutting edges. Very effective heuristic partitioning algorithms have been developed which run in real-time, but it is unknown how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. Distinctive features are the transmission and modification of whole subdomains (the partitioned units) that act as genes, and the use of a multilevel heuristic algorithm to effect the crossover and mutations. Its effectiveness is demonstrated by improvements on previously established benchmarks.

Multiphase mesh partitioning for parallel computational mechanics codes

We consider the load-balancing problems which arise from parallel scientific codes containing multiple computational phases, or loops over subsets of the data, which are separated by global synchronisation points. We motivate, derive and describe the implementation of an approach which we refer to as the multiphase mesh partitioning strategy to address such issues. The technique is tested on example meshes containing multiple computational phases and it is demonstrated that our method can achieve high quality partitions where a standard mesh partitioning approach fails.

Computing regular equivalence: practical and theoretical issues

Social network analysts have tried to capture the idea of social role explicitly by proposing a framework that precisely gives conditions under which group actors are playing equivalent roles. They term these methods positional analysis techniques. The most general definition is regular equivalence which captures the idea that equivalent actors are related in a similar way to equivalent alters. Regular equivalence gives rise to a whole class of partitions on a network. Given a network we have two different computational problems. The first is how to find a particular regular equivalence. An algorithm exists to find the largest regular partition but there are not efficient algorithms to test whether there is a regular k-partition. That is a partition in k groups that is regular. In addition, when dealing with real data, it is unlikely that any regular partitions exist. To overcome this problem relaxations of regular equivalence have been proposed along with optimisation techniques to find nearly regular partitions. In this paper we review the algorithms that have developed to find particular regular equivalences and look at some of the recent theoretical results which give an insight into the complexity of finding regular partitions.

Parallel mesh partitioning on distributed memory systems

The problem of deriving parallel mesh partitioning algorithms for mapping unstructured meshes to parallel computers is discussed in this chapter. In itself this raises a paradox - we seek to find a high quality partition of the mesh, but to compute it in parallel we require a partition of the mesh. In fact, we overcome this difficulty by deriving an optimisation strategy which can find a high quality partition even if the quality of the initial partition is very poor and then use a crude distribution scheme for the initial partition. The basis of this strategy is to use a multilevel approach combined with local refinement algorithms. Three such refinement algorithms are outlined and some example results presented which show that they can produce very high global quality partitions, very rapidly. The results are also compared with a similar multilevel serial partitioner and shown to be almost identical in quality. Finally we consider the impact of the initial partition on the results and demonstrate that the final partition quality is, modulo a certain amount of noise, independent of the initial partition.

A combined evolutionary search and multilevel optimisation approach to graph-partitioning

The graph-partitioning problem is to divide a graph into several pieces so that the number of vertices in each piece is the same within some defined tolerance and the number of cut edges is minimised. Important applications of the problem arise, for example, in parallel processing where data sets need to be distributed across the memory of a parallel machine. Very effective heuristic algorithms have been developed for this problem which run in real-time, but it is not known how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. A distinctive feature is the use of a multilevel heuristic algorithm to provide an effective crossover. The technique is tested on several example graphs and it is demonstrated that our method can achieve extremely high quality partitions significantly better than those found by the state-of-the-art graph-partitioning packages.

Grassland-herbivore interactions: How do grazers coexist?

We develop a new approach to modeling grazing systems that links foraging characteristics (intake and digestive constraints) with resource dynamics via the probability of encounter with different grass heights. Three complementary models are presented: the generation of a grass height structure through selective grazing; investigating the conditions for consumer coexistence; and, using a simplified resource structure, the consequences for consumer abundance. The main finding is that coexistence between grazers differing in body size is possible if a single-resource type becomes differentiated in its height structure. Large grazers can facilitate food availability for smaller species but with the latter being competitively dominant. The relative preference given to different resource partitions is important in determining the nature of population interactions. Large-body and small-body grazer populations can interact through competitive, parasitic, commensalist, or amensalist relationships, depending on the way they partition the resource as well as their relative populations and the dynamics of resource renewal. The models provide new concepts of multispecies carrying capacity (stock equilibrium) in grazed systems with implications for conservation and management. We conclude that consumer species are not substitutable; therefore, the use of rangeland management concepts such as "livestock units" may be inappropriate.

Learning soft computing control strategies in a modular neural network architecture

Modelling and control of nonlinear dynamical systems is a challenging problem since the dynamics of such systems change over their parameter space. Conventional methodologies for designing nonlinear control laws, such as gain scheduling, are effective because the designer partitions the overall complex control into a number of simpler sub-tasks. This paper describes a new genetic algorithm based method for the design of a modular neural network (MNN) control architecture that learns such partitions of an overall complex control task. Here a chromosome represents both the structure and parameters of an individual neural network in the MNN controller and a hierarchical fuzzy approach is used to select the chromosomes required to accomplish a given control task. This new strategy is applied to the end-point tracking of a single-link flexible manipulator modelled from experimental data. Results show that the MNN controller is simple to design and produces superior performance compared to a single neural network (SNN) controller which is theoretically capable of achieving the desired trajectory. (C) 2003 Elsevier Ltd. All rights reserved.

A New Gradient Descent Approach for Local Learning of Fuzzy Neural Models

The majority of reported learning methods for Takagi-Sugeno-Kang fuzzy neural models to date mainly focus on the improvement of their accuracy. However, one of the key design requirements in building an interpretable fuzzy model is that each obtained rule consequent must match well with the system local behaviour when all the rules are aggregated to produce the overall system output. This is one of the distinctive characteristics from black-box models such as neural networks. Therefore, how to find a desirable set of fuzzy partitions and, hence, to identify the corresponding consequent models which can be directly explained in terms of system behaviour presents a critical step in fuzzy neural modelling. In this paper, a new learning approach considering both nonlinear parameters in the rule premises and linear parameters in the rule consequents is proposed. Unlike the conventional two-stage optimization procedure widely practised in the field where the two sets of parameters are optimized separately, the consequent parameters are transformed into a dependent set on the premise parameters, thereby enabling the introduction of a new integrated gradient descent learning approach. A new Jacobian matrix is thus proposed and efficiently computed to achieve a more accurate approximation of the cost function by using the second-order Levenberg-Marquardt optimization method. Several other interpretability issues about the fuzzy neural model are also discussed and integrated into this new learning approach. Numerical examples are presented to illustrate the resultant structure of the fuzzy neural models and the effectiveness of the proposed new algorithm, and compared with the results from some well-known methods.

AVEC 2011–The First International Audio/Visual Emotion Challenge

The Audio/Visual Emotion Challenge and Workshop (AVEC 2011) is the first competition event aimed at comparison of multimedia processing and machine learning methods for automatic audio, visual and audiovisual emotion analysis, with all participants competing under strictly the same conditions. This paper first describes the challenge participation conditions. Next follows the data used – the SEMAINE corpus – and its partitioning into train, development, and test partitions for the challenge with labelling in four dimensions, namely activity, expectation, power, and valence. Further, audio and video baseline features are introduced as well as baseline results that use these features for the three sub-challenges of audio, video, and audiovisual emotion recognition.

Distillable entanglement and area laws in spin and harmonic-oscillator systems

We address the presence of nondistillable (bound) entanglement in natural many-body systems. In particular, we consider standard harmonic and spin-1/2 chains, at thermal equilibrium and characterized by few interaction parameters. The existence of bound entanglement is addressed by calculating explicitly the negativity of entanglement for different partitions. This allows us to individuate a range of temperatures for which no entanglement can be distilled by means of local operations, despite the system being globally entangled. We discuss how the appearance of bound entanglement can be linked to entanglement-area laws, typical of these systems. Various types of interactions are explored, showing that the presence of bound entanglement is an intrinsic feature of these systems. In the harmonic case, we analytically prove that thermal bound entanglement persists for systems composed by an arbitrary number of particles. Our results strongly suggest the existence of bound entangled states in the macroscopic limit also for spin-1/2 systems.

Thermal bound entanglement in macroscopic systems and area law

Does bound entanglement naturally appear in quantum many-body systems? We address this question by showing the existence of bound-entangled thermal states for harmonic oscillator systems consisting of an arbitrary number of particles. By explicit calculations of the negativity for different partitions, we find a range of temperatures for which no entanglement can be distilled by means of local operations, despite the system being globally entangled. We offer an interpretation of this result in terms of entanglement-area laws, typical of these systems. Finally, we discuss generalizations of this result to other systems, including spin chains.

Partitioning Heritability of Regulatory and Cell-Type-Specific Variants across 11 Common Diseases

Regulatory and coding variants are known to be enriched with associations identified by genome-wide association studies (GWASs) of complex disease, but their contributions to trait heritability are currently unknown. We applied variance-component methods to imputed genotype data for 11 common diseases to partition the heritability explained by genotyped SNPs () across functional categories (while accounting for shared variance due to linkage disequilibrium). Extensive simulations showed that in contrast to current estimates from GWAS summary statistics, the variance-component approach partitions heritability accurately under a wide range of complex-disease architectures. Across the 11 diseases DNaseI hypersensitivity sites (DHSs) from 217 cell types spanned 16% of imputed SNPs (and 24% of genotyped SNPs) but explained an average of 79% (SE = 8%) of  from imputed SNPs (5.1× enrichment; p = 3.7 × 10⁻¹⁷) and 38% (SE = 4%) of  from genotyped SNPs (1.6× enrichment, p = 1.0 × 10⁻⁴). Further enrichment was observed at enhancer DHSs and cell-type-specific DHSs. In contrast, coding variants, which span 1% of the genome, explained <10% of  despite having the highest enrichment. We replicated these findings but found no significant contribution from rare coding variants in independent schizophrenia cohorts genotyped on GWAS and exome chips. Our results highlight the value of analyzing components of heritability to unravel the functional architecture of common disease.

Consensus and Confusion in Molluscan Trees: Evaluating Morphological and Molecular Phylogenies

Mollusks are the most morphologically disparate living animal phylum, they have diversified into all habitats, and have a deep fossil record. Monophyly and identity of their eight living classes is undisputed, but relationships between these groups and patterns of their early radiation have remained elusive. Arguments about traditional morphological phylogeny focus on a small number of topological concepts but often without regard to proximity of the individual classes. In contrast, molecular studies have proposed a number of radically different, inherently contradictory, and controversial sister relationships. Here, we assembled a dataset of 42 unique published trees describing molluscan interrelationships. We used these data to ask several questions about the state of resolution of molluscan phylogeny compared to a null model of the variation possible in random trees constructed from a monophyletic assemblage of eight terminals. Although 27 different unique trees have been proposed from morphological inference, the majority of these are not statistically different from each other. Within the available molecular topologies, only four studies to date have included the deep-sea class Monoplacophora; but 36.4% of all trees are not significantly different. We also present supertrees derived from 2 data partitions and 3 methods, including all available molecular molluscan phylogenies, which will form the basis for future hypothesis testing. The supertrees presented here were not constructed to provide yet another hypothesis of molluscan relationships, but rather to algorithmically evaluate the relationships present in the disparate published topologies. Based on the totality of available evidence, certain patterns of relatedness among constituent taxa become clear. The internodal distance is consistently short between a few taxon pairs, particularly supporting the relatedness of Monoplacophora and the chitons, Polyplacophora. Other taxon pairs are rarely or never found in close proximity, such as the vermiform Caudofoveata and Bivalvia. Our results have specific utility for guiding constructive research planning in order to better test relationships in Mollusca as well as other problematic groups. Taxa with consistently proximate relationships should be the focus of a combined approach in a concerted assessment of potential genetic and anatomical homology, while unequivocally distant taxa will make the most constructive choices for exemplar selection in higher-level phylogenomic analyses.