Isorropia: Partitioning, Load Balancing and more
ispatest_lbeval_utils.hpp
Go to the documentation of this file.
1//@HEADER
2//************************************************************************
3//
4// Isorropia: Partitioning and Load Balancing Package
5// Copyright (2006) Sandia Corporation
6//
7//Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
8//license for use of this work by or on behalf of the U.S. Government.
9//
10// Redistribution and use in source and binary forms, with or without
11// modification, are permitted provided that the following conditions are
12// met:
13//
14// 1. Redistributions of source code must retain the above copyright
15// notice, this list of conditions and the following disclaimer.
16//
17// 2. Redistributions in binary form must reproduce the above copyright
18// notice, this list of conditions and the following disclaimer in the
19// documentation and/or other materials provided with the distribution.
20//
21// 3. Neither the name of the Corporation nor the names of the
22// contributors may be used to endorse or promote products derived from
23// this software without specific prior written permission.
24//
25// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36//
37//************************************************************************
38//@HEADER
39
40#ifndef _ispatest_lbeval_utils_hpp_
41#define _ispatest_lbeval_utils_hpp_
42
44#include <vector>
45
46#ifdef HAVE_EPETRA
47
48#include <Epetra_CrsGraph.h>
49#include <Epetra_CrsMatrix.h>
50#include <Epetra_Vector.h>
51#include <Epetra_LinearProblem.h>
53
54/* Load balance evaluation (As calculated in Zoltan_LB_Eval)
55
56 Given an Epetra graph and possible vertex and hyperedge weights,
57 calculate the hypergraph balance, cutn and cutl. We think of
58 the rows of the graph as the objects (vertices) to be partitioned
59 and the columns of the graph as the hyperedges.
60
61 ====================================
62
63 Definition of hypergraph balance:
64
65 Suppose Size_p is target size of partition p. (Sum of all Size_p is 1.0)
66 (For now Size_p is always 1/p in isorropia - we don't have an interface
67 to set different desired partition sizes.)
68
69 Let W_p be the total row weight on process p and WT be the sum of the
70 row weights on all processes. Then
71
72 imbalance on process p = |W_p - Size_p*WT| / Size_p*WT
73
74 balance = (1 + maximum imbalance over all processes p)
75
76 ====================================
77
78 Definition of hypergraph cutn and cutl:
79
80 Suppose Cut_k is the number of cuts in column k. (So column k is in
81 Cut_k + 1 different partitions.) Suppose W_k is the weight of column k.
82
83 cutn = Sum over all k of W_K * ((Cut_k > 0) ? 1 : 0)
84
85 cutl = Sum over all k of Cut_k * W_k
86
87 ====================================
88
89 TODO explain metrics computed in compute_graph_metrics
90*/
91namespace ispatest {
92
98int compute_balance(const Epetra_Vector &wgts, double myGoalWeight,
99 double &min, double &max, double &avg);
100
106int compute_hypergraph_metrics(const Epetra_CrsGraph &graph,
108 double &myGoalWeight,
109 double &balance, double &cutn, double &cutl);
110
116int compute_hypergraph_metrics(const Epetra_RowMatrix &matrix,
118 double &myGoalWeight,
119 double &balance, double &cutn, double &cutl);
120
136int compute_graph_metrics(const Epetra_RowMatrix &matrix,
138 double &myGoalWeight,
139 double &balance, int &numCuts, double &cutWgt, double &cutn, double &cutl);
140
156int compute_graph_metrics(const Epetra_CrsGraph &graph,
158 double &myGoalWeight,
159 double &balance, int &numCuts, double &cutWgt, double &cutn, double &cutl);
160
165void show_matrix(const char *txt, const Epetra_RowMatrix &matrix, const Epetra_Comm &comm);
166
171void show_matrix(const char *txt, const Epetra_CrsGraph &graph, const Epetra_Comm &comm);
172
177void show_matrix(const char *txt, const Epetra_LinearProblem &problem, const Epetra_Comm &comm);
178
179
180
181}//namespace ispatest
182
183#endif //HAVE_EPTERA
184
185#endif
186
Definition: Isorropia_EpetraCostDescriber.hpp:128
ispatest is the namespace that contains isorropia's test-utilities.
Definition: ispatest_epetra_utils.hpp:59
int compute_hypergraph_metrics(const Epetra_CrsGraph &graph, Isorropia::Epetra::CostDescriber &costs, double &myGoalWeight, double &balance, double &cutn, double &cutl)
Compute Zoltan-style hypergraph metrics given a partitioned CrsGraph and a CostDescriber (weight) obj...
int compute_graph_metrics(const Epetra_RowMatrix &matrix, Isorropia::Epetra::CostDescriber &costs, double &myGoalWeight, double &balance, int &numCuts, double &cutWgt, double &cutn, double &cutl)
Compute graph metrics given an Epetra_RowMatrix.
void show_matrix(const char *txt, const Epetra_RowMatrix &matrix, const Epetra_Comm &comm)
Print out a distributed RowMatrix.
int compute_balance(const Epetra_Vector &wgts, double myGoalWeight, double &min, double &max, double &avg)
Given an Epetra_Vector of weights, compute the weight imbalance on each process.