Software package and libraries for sequential and parallel graph partitioning, static mapping and clustering, sequential mesh and hypergraph partitioning, and sequential and parallel sparse matrix block ordering

[FRANÇAIS]French version
Version française


Updates of SCOTCH

3 September 2020

Version 6.1 of SCOTCH is out !

Like the previous ones, it is available as free/libre software under the CeCILL-C license.

2 December 2012

Exactly 20 years after, to the day, the first line of SCOTCH was written, version 6.0 of SCOTCH, aka « the 20 y.o. SCOTCH » edition, is released. This version offers many new features:

2 September 2010

Revision 5.1.10 of SCOTCH breaks the « 32-bit barrier » in parallel.

Revision 5.1.10 is the first to be able to handle in parallel graphs of more than two billion vertices (limit of representation for 32-bit wide signed integers). PT-SCOTCH has been able to bipartition, in 76 seconds, a 3D graph of more than 2.4 billion vertices and 7.3 billion edges, distributed across 2048 processors of machine platine at CCRT.

The sequential SCOTCH library is also fully capable of handling 64-bit values, since revision 5.1.8 for all of its routines.

8 September 2008
Version 5.1 of SCOTCH is available as free/libre software under the CeCILL-C license.

Version 5.1 is the first one to provide parallel graph partitioning features in PT-SCOTCH.

8 August 2007

Version 5.0 of SCOTCH is available as free/libre software under the CeCILL-C license.

Version 5.0 is the first one to include PT-SCOTCH, the parallel version of SCOTCH. Its new features comprise:

1st February 2006

Version 4.0 of SCOTCH is available as LGPL'ed free/libre software.

Version 4.0 is the first free/libre release of SCOTCH. It is a major rewriting of version 3.4, which comprises many new features:


What SCOTCH is

SCOTCH is a project carried out within the Satanas team of the Laboratoire Bordelais de Recherche en Informatique (LaBRI). It is part of the works of the team TADaaM of INRIA Bordeaux - Sud-Ouest.

Its purpose is to apply graph theory, with a divide and conquer approach, to scientific computing problems such as graph and mesh partitioning, static mapping, and sparse matrix ordering, in application domains ranging from structural mechanics to operating systems or bio-chemistry.

The SCOTCH distribution is a set of programs and libraries which implement the static mapping and sparse matrix reordering algorithms developed within the SCOTCH project.

SCOTCH has many interesting features:


Obtaining SCOTCH

Version 6 of SCOTCH is distributed as free/libre software, under the terms of the CeCILL-C license. Please refer to the Resources section below to see how to download the newest revisions of the sources of SCOTCH and of its documentation.

SCOTCH can also be distributed under other types of licenses and conditions to parties willing to embed it into closed, proprietary software. Please contact us if you are considering this option.



To ease the development, diffusion, and circulation of information regarding the SCOTCH project, most of its resources are now hosted on the Inria GitLab platform. This forge provides many services to people interested in the project.

The old Gforge instance (see below) will be maintained concurrently, up to the decommission of this platform.

Obsolete resources

Formerly, the resources regarding the SCOTCH project were hosted on the InriaGforge platform.
Home page of the SCOTCH project repository.
File download section of the SCOTCH project repository, where source tarballs can be downloaded from.
Source code repository of the SCOTCH project.
Documentation regarding the SCOTCH project.
Archive of the scotch-announces mailing list, to which one can subscribe here.
SCOTCH users are welcome to register to this list, to be informed of new releases, publications, and informations regarding SCOTCH, and to tell the other members of the community about new partitioning or ordering methods they have developed.
Fora regarding the SCOTCH project. Users and prospective users are welcome to contribute to them by submitting questions and reports of experiments with SCOTCH.
Bug, technical support and feature request tracking system.


Some mapping results obtained with SCOTCH


Documents regarding SCOTCH

Working documents regarding SCOTCH are now available from the InriaGforge documentation repository. Below are listed other documents or bibliographic data of documents which cannot be made available because of copyright issues.

Contributions au partitionnement de graphes parallèle multi-niveaux / Contributions to parallel multilevel graph partitioning.
Habilitation à diriger des recherches, LaBRI, Université Bordeaux 1, December 2009.
F. Pellegrini.
(Slides of the habilitation defense)

Distillating knowledge about SCOTCH.
Combinatorial Scientific Computing, Dagstuhl Seminar Proceedings series, number 09061, July 2009.
F. Pellegrini.

PT-SCOTCH: a tool for efficient parallel graph ordering.
Parallel Computing, 34(6-8), pp 318-331, 2008.
C. Chevalier and F. Pellegrini.

SCOTCH 5.1 User's guide.
Technical report, LaBRI, September 2008.
F. Pellegrini.

PT-SCOTCH 5.1 User's guide.
Technical report, LaBRI, September 2008.
F. Pellegrini.

Conception et mise en oeuvre d'outils efficaces pour le partitionnement et la distribution parallèles de problèmes numériques de très grande taille.
Thèse de doctorat, LaBRI, Université Bordeaux 1, September 2007.
C. Chevalier.

A parallelisable multi-level banded diffusion scheme for computing balanced partitions with smooth boundaries.
EuroPar, August 2007, Rennes. © Springer-Verlag, published in the LNCS series, LNCS 4641, pp 191-200.
F. Pellegrini.

PT-SCOTCH: a tool for efficient parallel graph ordering.
Research report, LaBRI, December 2006. Submitted to Parallel Computing.
C. Chevalier and F. Pellegrini.

PT-SCOTCH : Un outil pour la renumérotation parallèle efficace de grands graphes dans un contexte multi-niveaux.
RenPar, October 2006, Canet-en-Roussillon.
C. Chevalier and F. Pellegrini.

PT-SCOTCH: A tool for efficient parallel graph ordering.
PMAA, September 2006, Rennes.
C. Chevalier and F. Pellegrini.

Improvement of the Efficiency of Genetic Algorithms for Scalable Parallel Graph Partitioning in a Multi-Level Framework.
EuroPar, August 2006, Dresden. © Springer-Verlag, published in the LNCS series, LNCS 4128, pp 243-252.
C. Chevalier and F. Pellegrini.

SCOTCH 4.0 User's guide.
Technical report, LaBRI, February 2006.
F. Pellegrini.

Native mesh ordering with SCOTCH.
Research report, LaBRI, May 2004.
F. Pellegrini.

Using the native mesh partitioning capabilities of SCOTCH 4.0 in a parallel industrial electromagnetics code.
Eleventh SIAM Conference on Parallel Processing for Scientific Computing, San Francisco, California, USA, February 2004.
F. Pellegrini and D. Goudin.

SCOTCH 3.4 User's guide.
Research report RR-1264-01, LaBRI, November 2001.
F. Pellegrini.

Hybridizing Nested Dissection and Halo Approximate Minimum Degree for Efficient Sparse Matrix Ordering.
Concurrency: Practice and Experience, 12:69-84, 2000.
F. Pellegrini, J. Roman, and P. Amestoy.
Preliminary version published in the proceedings of Irregular'99, San Juan, Puerto Rico, LNCS 1586, pages 986-995.

Sparse matrix ordering with SCOTCH.
Proceedings of HPCN'97, Vienna, Austria. LNCS 1225, pages 370-378. Springer, April 1997.
F. Pellegrini and J. Roman.

Experimental Analysis of the Dual Recursive Bipartitioning Algorithm for Static Mapping.
Research report RR-1138-96, LaBRI, September 1996.
F. Pellegrini and J. Roman.

SCOTCH: A Software Package for Static Mapping by Dual Recursive Bipartitioning of Process and Architecture Graphs.
Proceedings of HPCN'96, Brussels, Belgium. LNCS 1067, pages 493-498. Springer, April 1996. F. Pellegrini and J. Roman.

Application de méthodes de partition à la résolution de problèmes de graphes issus du parallélisme.
Thèse de doctorat, LaBRI, Université Bordeaux 1, January 1995.
F. Pellegrini.

Static mapping by dual recursive bipartitioning of process and architecture graphs.
Proceedings of SHPCC'94, Knoxville, Tennessee, pages 486-493. IEEE Press, May 1994.
F. Pellegrini.

François Pellegrini