Scotch Brand 5.1.10 - Manual (Page 7)

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