Isorropia: Partitioning, Coloring, and Ordering
Isorropia is a package for combinatorial scientific computing, with focus on partitioning (load balancing), but also supports coloring and ordering. Its main purpose is to assist with redistributing objects such as matrices and matrix-graphs in a parallel execution setting, to allow for more efficient computations. Isorropia produces good maps for Epetra matrices/graphs. Isorropia should be called after the matrix/graph is filled, so the sparsity pattern is known.
In addition to matrix/graph partitioning, Isorropia has the capability to partition 1, 2 or 3-dimensional real coordinates into balanced spatial regions. The coordinates are represented as an Epetra_MultiVector.
Isorropia's coloring capability can also be employed for the purpose of probing structurally symmetric matrices.
Isorropia is primarily an interface to the Zoltan toolkit. Zoltan became a Trilinos package in 9.0 and is now a required dependency. If you wish to use third-party libraries (such as ParMetis or PT-Scotch) with Isorropia (via Zoltan), see the configure options for Zoltan.
Isorropia currently contains algorithms for three separate problems. In the case of sparse matrices, these problems can each be viewed as a combinatorial problem based on graphs:
Partitioning (load-balancing) and subsequent data redistribution.
Fill-reducing ordering (for sparse direct solvers).
Isorropia contains separate classes to solve each of these problems, all of which derive from Isorropia::Operator and Isorropia::Epetra::Operator. Note that an operator in Isorropia is different from an operator in Epetra!
Isorropia has a fairly small number of parameters, listed below. (Default values in all caps.) Note that Isorropia parameters are case insensitive. For more specific control of low-level features, you may set a Zoltan parameter. Isorropia will pass any parameter in the Zoltan sublist to Zoltan.
STRUCTURALLY SYMMETRIC [NO/yes] (is symmetrization required?)
PARTITIONING METHOD [block/cyclic/random/rcb/hsfc/graph/HYPERGRAPH]
NUM PARTS [int n] (global number of parts)
IMBALANCE TOL [float tol] (1.0 is perfect balance)
BALANCE OBJECTIVE [ROWS/nonzeros]
DISTANCE [1/2] (for coloring only; two is default)
We focus on the partitioning (load balancing), which is the most heavily used feature. Isorropia's load balancing user interface consists primarily of the Isorropia::Partitioner, Isorropia::Redistributor and Isorropia::CostDescriber classes, as well as the Isorropia::Epetra::createBalancedCopy functions.
The Isorropia::Epetra::createBalancedCopy functions are free-standing functions (not class members) which simply take an input object (Epetra_CrsGraph, Epetra_CrsMatrix, etc.) and return a copy which is balanced across processes (parts).
In many use cases, such as performing one partitioning and then using it to redistribute multiple objects, it is more efficient to use the Isorropia::Partitioner and Isorropia::Redistributor classes. The general usage model is to:
Create a Isorropia::Partitioner instance, providing the objects to be partitioned, and optionally weights for those objects. Weights can be defined with an Isorropia::CostDescriber for graphs and hypergraphs, or with an Epetra_MultiVector for geometric coordinates.
Create a Isorropia::Redistributor object (providing as input a Isorropia::Partitioner instance)
Use the Isorropia::Redistributor to redistribute one or more objects to the new partitioning.
Isorropia was designed such that these steps can usually be done in three lines of code. For example, the Partitioner will by default compute the partitioning at construction time.
Isorropia currently supports partitioning/redistributing of several Epetra objects, including Epetra_CrsGraph, Epetra_RowMatrix (which includes Epetra_CrsMatrix and Epetra_VbrMatrix) and Epetra_MultiVector. (The Epetra_MultiVector is interpreted as 1, 2 or 3 dimensional coordinates and is partitioned into balanced spatial regions using Zoltan's geometric partitioning methods.)
Several Isorropia classes and methods accept Teuchos::ParameterList objects, allowing the user to control certain behavior. Isorropia parameters can be either lower or upper case.
Choice of partitioner
Currently, all partitioning methods are provided by Zoltan. The default option (for sparse matrices) is to minimize communication with the hypergraph model. However, a wide range of partitioners is supported (BLOCK, CYCLIC, RANDOM, GRAPH). The partitioning method is set by using a Isorropia parameter :
params.set("partitioning method", "graph"); // Corresponds to LB_METHOD in Zoltan
Passing parameters through to Zoltan
Isorropia can relay Zoltan parameters directly to Zoltan. Before passing a Teuchos::ParameterList to Isorropia, create a sublist in it named "Zoltan". Then, any parameters that should be passed to Zoltan itself, can be stored in the sublist exactly as they appear in the Zoltan users guide. Example:
Teuchos::ParameterList& sublist = params.sublist("Zoltan");
Refer to the Zoltan User's guide (available at the Zoltan web site) for available Zoltan parameters. In many cases, no parameters are necessary. Note that Isorropia will override a few default Zoltan settings: For graphs and matrices, the default method (LB_METHOD) is HYPERGRAPH. The default approach (LB_APPROACH) is PARTITION. For coordinates the default LB_METHOD is RCB (recursive coordinate bisection).
A number of example programs which demonstrate using Isorropia are provided in the 'packages/isorropia/example' subdirectory.
matrix_1.cpp demonstrates creating a balanced copy of Epetra_CrsGraph and Epetra_CrsMatrix objects using Isorropia::Epetra::createBalancedCopy functions.
part_redist.cpp demonstrates repartitioning and redistributing the contents of an Epetra_LinearProblem object, using the Isorropia::Partitioner and Isorropia::Redistributor classes. This program does not use user-specified weights/costs.
Other programs in the example subdirectory demonstrate the use of weights/costs data to influence the partitioner. See vert_weights.cpp, graphedge_weights.cpp and hgedge_weights.cpp.
example_rcb.cpp demonstrates the use of Isorropia to partition spatial coordinates using Zoltan's Recursive Coordinate Bisection algorithm.
Isorropia supports vertex coloring of a graph via Zoltan. Both distance-1 and distance-2 coloring is supported. See the Zoltan User's guide (available at the Zoltan web site) for details. Currently, coloring is limited to structurally symmetric matrices but we expect to support nonsymmetric matrices (e.g. Jacobians) in the future.
Isorropia currently supports a subset of the graph (sparse matrix) ordering features in Zoltan. The intended main use is to produce a permutation that can be used as fill-reducing ordering for direct solvers. Currently Zoltan relies on third-party libraries (ParMetis and PT-Scotch) for this.
Isorropia's distance-2 graph vertex capability enables matrix probing, the re-construction (or approximation) of a matrix from matrix-vector products with specially chosen vectors. These vectors are combinations of columns of the identity which are carefully chosen such that the columns probed by such a vector are structurally orthogonal. The most common use case of probing is when the matrix is not explicitly stored, but the matrix entries are necessary for some other procedure (e.g. preconditioning). In certain applications, an exact reconstruction of the matrix is needed. In others, an approximation based on a priori knowledge of the ``significant'' matrix entries suffices. Isorropia's probing functionality works in both cases. See Probing for an example of how probing is used.
Currently, Isorropia's probing functionality is limited to structurally symmetric matrices but we expect to support nonsymmetric matrices (e.g. Jacobians) in the future.