Chris Walshaw
 – NetWorks
 – partition archive
 – publications
 Enterprise & KE

JOSTLE — graph partitioning software

partitioned 3 element airfoil

JOSTLE is a software package designed to partition unstructed meshes (for example, finite element or finite volume meshes) for use on distributed memory parallel computers. It can also be used to repartition and load-balance existing partitions (such as those deriving from adaptive refined meshes). It achieves this by modelling the mesh as an undirected graph and then using state-of-the-art graph partitioning techniques.

The code is extremely fast and provides high quality multilevel partitioning and diffusive load-balancing in both serial & parallel.

Since its release in 1995, JOSTLE gained a worldwide user community of around 150 licensed sites, by groups based at Los Alamos, Argonne & Sandia National Labs (all in the USA), NASA, and in Universities across the world (specifically the USA, Canada, Brazil, Austria, Belgium, Czech Republic, Finland, France, Germany, Greece, Holland, Italy, Poland, Russia, Spain, Sweden, Switzerland, Turkey, Israel, Oman, India, Japan, Singapore & Taiwan).

After 20 years as a free software package, in 2015 JOSTLE was withdrawn from service. However it has been commercialised and extended and most of the functionality is available under the name of NetWorks.


You can find out more about the underlying algorithms from several papers; probably the best to start with are:

overview paper
C. Walshaw and M. Cross. JOSTLE: Parallel Multilevel Graph-Partitioning Software - An Overview. In F. Magoules, editor, Mesh Partitioning Techniques and Domain Decomposition Techniques, pages 27-58. Civil-Comp Ltd., 2007. (Invited chapter).
[citation.bib] [abstract.html]
dynamic partitioning & load balancing:
C. Walshaw, M. Cross, and M. Everett. Parallel Dynamic Graph Partitioning for Adaptive Unstructured Meshes. J. Par. Dist. Comput., 47(2):102-108, 1997.
[citation.bib] [abstract.html]
parallel partitioning:
C. Walshaw and M. Cross. Parallel Optimisation Algorithms for Multilevel Mesh Partitioning. Parallel Comput., 26(12):1635-1660, 2000.
[citation.bib] [abstract.html]
multiphase partitioning:
C. Walshaw, M. Cross, and K. McManus. Multiphase Mesh Partitioning. Appl. Math. Modelling, 25(2):123-140, 2000.
[citation.bib] [abstract.html]
multilevel balancing:
C. Walshaw and M. Cross. Mesh Partitioning: a Multilevel Balancing and Refinement Algorithm. SIAM J. Sci. Comput., 22(1):63-80, 2000.
[citation.bib] [abstract.html]
partitioning for optimising domain shape:
C. Walshaw, M. Cross, R. Diekmann, and F. Schlimbach. Multilevel Mesh Partitioning for Optimising Domain Shape. Intl. J. High Performance Comput. Appl., 13(4):334-353, 1999.
[citation.bib] [abstract.html]
mapping to heterogeneous communication networks:
C. Walshaw and M. Cross. Multilevel Mesh Partitioning for Heterogeneous Communication Networks. Future Generation Comput. Syst., 17(5):601-623, 2001.
[citation.bib] [abstract.html]
combined with evolutionary search to create extremely high quality partitions:
A. J. Soper, C. Walshaw, and M. Cross. A Combined Evolutionary Search and Multilevel Optimisation Approach to Graph Partitioning. J. Global Optimization, 29(2):225-241, 2004.
[citation.bib] [abstract.html]

A full list of papers can be found on the publications page.

Back to top


User guides are available for:

Back to top