1.3
Contents of this document
This document describes the capabilities and operations of
Scotch
, a software
package devoted to static mapping, graph and mesh partitioning, and sparse matrix
block ordering.
Scotch
allows the user to map efficiently any kind of weighted
process graph onto any kind of weighted architecture graph, and provides high-
quality block orderings of sparse matrices. The rest of this manual is organized
as follows. Section 2 presents the goals of the
Scotch
project, and section 3
outlines the most important aspects of the mapping and ordering algorithms that it
implements. Section 4 summarizes the most important changes between version
5.0
and previous versions. Section 5 defines the formats of the files used in
Scotch
,
section 6 describes the programs of the
Scotch
distribution, and section 7 defines
the interface and operations of the
libScotch
library. Section 8 explains how
to obtain and install the
Scotch
distribution. Finally, some practical examples
are given in section 9, and instructions on how to implement new methods in the
libScotch
library are provided in section 10.
2
The
Scotch
project
2.1
Description
Scotch
is a project carried out at the
Laboratoire Bordelais de Recherche en In-
formatique
(LaBRI) of the Universit´e Bordeaux I, and now within the ScAlApplix
project of INRIA Bordeaux Sud-Ouest. Its goal is to study the applications of graph
theory to scientific computing, using a “divide and conquer” approach.
It focused first on static mapping, and has resulted in the development of the
Dual Recursive Bipartitioning (or DRB) mapping algorithm and in the study of
several graph bipartitioning heuristics [41], all of which have been implemented in
the
Scotch
software package [45]. Then, it focused on the computation of high-
quality vertex separators for the ordering of sparse matrices by nested dissection,
by extending the work that has been done on graph partitioning in the context
of static mapping [46, 47]. More recently, the ordering capabilities of
Scotch
have been extended to native mesh structures, thanks to hypergraph partitioning
algorithms. New graph partitioning methods have also been recently added [8, 42].
Version
5.0
of
Scotch
is the first one to comprise parallel graph ordering rou-
tines. The parallel features of
Scotch
are referred to as
PT-Scotch
(“
Parallel
Threaded
Scotch
”). While both packages share a significant amount of code, bea-
cuse
PT-Scotch
transfers control to the sequential routines of the
libScotch
library when the subgraphs on which it operates are located on a single processor,
the two sets of routines have a distinct user’s manual. Readers interested in the
parallel features of
Scotch
should refer to the
PT-Scotch 5.1
User’s Guide
[43].
2.2
Availability
Starting from version
4.0
, which has been developed at INRIA within the ScAlAp-
plix project,
Scotch
is available under a dual licensing basis. On the one hand, it
is downloadable from the
Scotch
web page as free/libre software, to all interested
parties willing to use it as a library or to contribute to it as a testbed for new
partitioning and ordering methods. On the other hand, it can also be distributed,
under other types of licenses and conditions, to parties willing to embed it tightly
into closed, proprietary software.
7
