(3M) Calculator User Manual

1.3 Contents of this document
This document describes the capabilities and o perations 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 weig hted
process graph onto any kind of weighted architecture graph, and provides high-
quality block orderings of sparse matrices . The rest o f this manual is organized
as follows. Section 2 presents the g oals of the Scotch project, and se ction 3
outlines the most impo rtant aspects of the mapping and ordering alg orithms that it
implements. Section 4 summarizes the most important changes betwee n version 5.0
and previous versions. Section 5 defines the formats of the files used in Scotch,
section 6 describes the prog rams 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 gra ph
theory to scientific computing, using a “divide and co nquer” approach.
It focused first on static mapping, and has resulted in the development of the
Dual Recursive B ipartitioning (or DRB) mapping algorithm and in the study of
several graph bipartitioning heuristics [41], all o f which have been implemented in
the Scotch software package [45]. Then, it focuse d 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 sta tic mapping [46, 47]. More r e cently, the ordering capabilities of Scotch
have been extended to native mesh structures, thanks to hypergraph partitioning
algorithms. New graph partitioning methods have als o been recently added [8, 42].
Version 5.0 of Scotch is the first one to comprise parallel g raph 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 process or,
the two sets of routines have a distinct use r’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 dow nloadable from the Scotch web page as free/libre software, to all interested
parties willing to use it as a library or to c ontribute to it a s 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