Mesh partitioning: a multilevel balancing and refinement algorithm

Multilevel algorithms are a successful class of optimization techniques which addresses the mesh partitioning problem. They usually combine a graph contraction algorithm together with a local optimization method which refines the partition at each graph level. In this paper we present an enhancement of the technique which uses imbalance to achieve higher quality partitions. We also present a formulation of the Kernighan-Lin partition optimization algorithm which incorporates load-balancing. The resulting algorithm is tested against a different but related state-of-the-art partitioner and shown to provide improved results.

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.

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.

[Conference report] Magic and mathematics: The life and work of John Dee. National Maritime Museum, Greenwich, 13-14 June 2003

Tony Mann provides a report of a two-day meeting "Magic and mathematics: The life and work of John Dee" held from 13-14 June 2003 at the National Maritime Museum, Greenwich.

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.

[Book review] Mathematics and Culture II

Review of Mathematics and Culture II. Visual Perfection: Mathematics and Creativity, Michele Emmer (Ed.), Springer, 2005 ISBN: 978-3-540-21368-0

BSHM meetings: BMS History of Mathematics Splinter Group

Introduction to abstracts from papers given at BMS History of Mathematics Splinter Group, held 17 April 2007, in Swansea.

BSHM meetings: British Mathematics Colloquium

Report on the British Mathematics Colloquium, which took place in York, 25-28 March 2008. Also includes abstracts of the individual talks.

[BSHM meetings] Topics in the history of financial mathematics: early commerce to chaos in modern stock markets

This account provides an overview of the study day, entitled 'Topics in the History of Financial Mathematics: Early commerce to chaos in modern stock markets,' held by the British Society for the History of Mathematics jointly with Gresham College, at Gresham College, London on 25th April 2008. The series of talks explored the development of mathematics and mathematical techniques in a commercial and financial context.

Reviews: making mathematics with needlework

Review of Making Mathematics with Needlework, edited by Sarah-Marie Belcastro and Carolyn Yackel, published by AK Peters Ltd, 2007 (ISBN 978-1-56881-331-8).

[Book review] Collaborative learning in mathematics

Review of: Collaborative Learning in Mathematics: A challenge to our beliefs and practices by Malcolm Swan, National Institute of Adult Continuing Education, paperback £24.95, ISBN 981-1-86201-311-7; hardback £44.95, ISBN 978-1-86201-316-2.

Some issues on assessment methods and learning in mathematics and statistics

This paper looks at the application of some of the assessment methods in practice with the view to enhance students’ learning in mathematics and statistics. It explores the effective application of assessment methods and highlights the issues or problems, and ways of avoiding them, related to some of the common methods of assessing mathematical and statistical learning. Some observations made by the author on good assessment practice and useful approaches employed at his institution in designing and applying assessment methods are discussed. Successful strategies in implementing assessment methods at different levels are described.