Debian Codegraph @

3rdparty/dissection/src/Splitters/BisectionTree.hpp

raw
1 /*! \file BisectionTree.hpp
2 \brief ordeing by graph decomposer, SCOTCH or METIS
3 \author Xavier Juvigny, ONERA
4 \date Jul. 2nd 2012
5 \date Nov. 30th 2016
6 */
7
8 // This file is part of Dissection
9 //
10 // Dissection is free software: you can redistribute it and/or modify
11 // it under the terms of the GNU General Public License as published by
12 // the Free Software Foundation, either version 3 of the License, or
13 // (at your option) any later version.
14 //
15 // Linking Dissection statically or dynamically with other modules is making
16 // a combined work based on Disssection. Thus, the terms and conditions of
17 // the GNU General Public License cover the whole combination.
18 //
19 // As a special exception, the copyright holders of Dissection give you
20 // permission to combine Dissection program with free software programs or
21 // libraries that are released under the GNU LGPL and with independent modules
22 // that communicate with Dissection solely through the Dissection-fortran
23 // interface. You may copy and distribute such a system following the terms of
24 // the GNU GPL for Dissection and the licenses of the other code concerned,
25 // provided that you include the source code of that other code when and as
26 // the GNU GPL requires distribution of source code and provided that you do
27 // not modify the Dissection-fortran interface.
28 //
29 // Note that people who make modified versions of Dissection are not obligated
30 // to grant this special exception for their modified versions; it is their
31 // choice whether to do so. The GNU General Public License gives permission to
32 // release a modified version without this exception; this exception also makes
33 // it possible to release a modified version which carries forward this
34 // exception. If you modify the Dissection-fortran interface, this exception
35 // does not apply to your modified version of Dissection, and you must remove
36 // this exception when you distribute your modified version.
37 //
38 // This exception is an additional permission under section 7 of the GNU
39 // General Public License, version 3 ("GPLv3")
40 //
41 // Dissection is distributed in the hope that it will be useful,
42 // but WITHOUT ANY WARRANTY; without even the implied warranty of
43 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
44 // GNU General Public License for more details.
45 //
46 // You should have received a copy of the GNU General Public License
47 // along with Dissection. If not, see <http://www.gnu.org/licenses/>.
48 //
49
50 // ==============================================================
51 // == Bisection tree : stored by components in 1D arrays ==
52 // ==============================================================
53 #ifndef _DISSECTION_SPLITTERS_BISECTIONTREE_HPP_
54 #define _DISSECTION_SPLITTERS_BISECTIONTREE_HPP_
55 #include <cstdio>
56 #include "Splitters/BitManipulations.hpp"
57 #include "Splitters/BisectionInterConnection.hpp"
58 #include "Splitters/Splitter.hpp"
59 #include "Algebra/CSR_matrix.hpp"
60
61 namespace Dissection
62 {
63 /** @brief Nested Bisection tree
64
65 The nested bisection tree is the core of the
66 symbolic factorization.
67 Nodes are numbered from root,starting at 1,
68 to leaves by layer order.
69
70 By example : (layer level)
71 ----------- 1 0
72 / \
73 2 3 1
74 /\ /\
75 4 5 6 7 2
76
77 Data are stored components by components, ordered as above :
78 [D1,D2,D3,D4,D5,D6,D7]
79
80 Each layer l data begin at 2^l (0 <= l < number of layers)
81
82 A node n is in layer highest_one_idx(n)
83
84 The brother of a node n (node sharing same father) is n^1
85 (^ means xor operation as C convention).
86
87 Ancestors are n>>p where
88 0 < p < number of layers - level of domain
89 */
90 class Tree
91 {
92 public:
93 /**@name Constructors and destructor */
94 //@{
95 /** @brief Build bisection tree
96
97 From the sparse matrix CSR structure,
98 build the bisection tree for symbolic factorization
99 computing some block permutations to speed-up data
100 transfert between blocks.
101
102 @param dim Dimension of the sparse matrix
103 @param ptRows Indices pointing on the beginning of
104 each row of the sparse matrix.
105 The last value ptRows[dim] provides the
106 number of non zero coefficients of the
107 sparse matrix.
108 @param indCols Column indice of each non zero coefficients
109 of the sparse matrix. Values must be stored
110 and sorted (increasing) by row
111 @param nbMaxLevel Maximal number of iteration for the
112 bisection method.
113 @param minSize Minimal number of nodes per subdomains
114 in the leaves of the tree.
115 @param spltFct The nested bisection library function to use
116 By default, Scotch is used to do nested
117 bisection
118 @param checkData If true, verify some consistencies in the given sparse
119 matrix structure. If false, assume than
120 provided sparse matrix structure is
121 consistency.
122 */
123 Tree(FILE *fp, bool &berr, unsigned dim,
124 const CSR_indirect *csr,
125 const bool isSym, //const bool isLower,
126 const int *remap_eqn, //const int *remap_indcols,
127 unsigned nbMaxLevel=8, unsigned minSize = 120,
128 splitter spltFct = NULL,
129 bool checkData = false, bool verbose = true);
130
131 /** @brief Destructor
132 */
133 ~Tree();
134 //@}
135
136 /** @name Getters and setters */
137 //@{
138 /// Return index of the brother (i.e having same father) node
139 /// of a node nd.
140 static int selfIndex(unsigned nd) {
141 return (int)(nd - 1);
142 }
143 static int Index2Node(unsigned nd) {
144 return (int)(nd + 1);
145 }
146 static unsigned brotherIndex(unsigned nd) {
147 return (nd ^ 1);
148 }
149 /// Return index of the father node index of a node nd
150 static unsigned fatherIndex(unsigned nd) {
151 return (nd / 2);
152 }
153 /// Return index of nth forerunner of domain nd :
154 static unsigned nthfatherIndex(unsigned nd, unsigned nth) {
155 return (nd >> nth);
156 }
157 /// Return index of the first child index for node nd :
158 static unsigned childIndex(unsigned nd) {
159 return (nd * 2);
160 }
161 /// Return layer number where lies the domain nd :
162 static unsigned nodeLayer(unsigned nd) {
163 return highest_one_idx(nd);
164 }
165 /// Return
166 unsigned NumberOfLevels() {
167 return _nbLevels;
168 }
169 unsigned NumberOfSubdomains() {
170 return _nbDoms;
171 }
172 //
173 unsigned NumberOfSubdomains(unsigned level) {
174 // (_sbLevels - 1) == (void)
175 if (level < _nbLevels) {
176 return ((1 << (level + 1)) - 1); // including own level
177 }
178 else {
179 return 0U;
180 }
181 }
182
183 /// Return number of internal nodes of a domain nd (>=1)
184 unsigned sizeOfDomain(unsigned nd) const {
185 return _sizeOfDomains[selfIndex(nd)];
186 }
187
188 unsigned sizeOfFathersStrips(unsigned nd) const {
189 return _sizeOfFathersStrips[selfIndex(nd)];
190 }
191
192 /// Return connection between a domain nd (nd >= 1) and his ancestors
193 const FathersStrips& getFathersStrips(unsigned nd) {
194 return _interco[selfIndex(nd)];
195 }
196 const CSR_indirect& getDiagCSR(unsigned nd) {
197 return _csr_diag[selfIndex(nd)];
198 }
199 const CSR_indirect& getOffdiagCSR(unsigned nd) {
200 return _csr_offdiag[selfIndex(nd)];
201 }
202 int *getDiagLoc2Glob(unsigned nd) {
203 return _loc2glob_diag[selfIndex(nd)];
204 }
205 int *getOffdiagLoc2Glob(unsigned nd) {
206 return _loc2glob_offdiag[selfIndex(nd)];
207 }
208
209 bool save(FILE* stream) const;
210 /** @brief Load bisection tree contents */
211 bool load(FILE* stream) ;
212 /** @brief Print information on bisection tree
213
214 A verbose level can be provided. Depending of
215 his value, informations printed are :
216
217 >=1 : Some statistics data (number of domains,
218 mean number of nodes per domains per layer,
219 variance of number of nodes per domains,...)
220 >=2 : Global indices of nodes contained per domains
221
222 >=3 : Block permutation from a domain and his forerunnings
223
224 @param verboseLevel Choose the level of verbose
225 to print some information for
226 dissection tree.
227 */
228 void printInfo(FILE* stream,
229 unsigned verboseLevel = 1) const;
230
231 //@}
232 private:
233 bool _verbose;
234 /* Allocate and fill an array with indices of domain
235 containing each local index.
236 The caller of this method must free the returned array.
237 */
238 unsigned* compLoc2Dom(unsigned dim) const;
239 /* Remove self references from the skeleton graph of the sparse matrix
240 provided to the splitter
241 */
242 void removeLoops(int dim,
243 const int* ptRows, const int* indCols,
244 int*& ptRows2, int*& indCols2);
245 /* Do symbolic factorization */
246 FathersStrips* symbolicFactorization(SetOfStrips** connections);
247 /* Renumbering interfaces to optimize number of strips */
248 void renumberingInterface(unsigned nperm, unsigned* perm,
249 const SetOfStrips& paral,
250 const SetOfStrips& parar,
251 const SetOfStrips& seq,
252 unsigned layer, unsigned iDom) const;
253 void draw_csr(char *filename,
254 int dim,
255 const int *ptRows,
256 const int *indCols,
257 const int *ptRow_diag,
258 const int *indVals,
259 const unsigned *l2d);
260
261 /// Number of levels done in nested bisection algorithm
262
263 unsigned _nbDoms;
264 unsigned _nbLevels;
265 /// Number of nodes (internal only for each leaf)
266 int *_sizeOfDomains;
267 int *_sizeOfFathersStrips;
268 /// Indice (starting at 0) of the beginning of each domain
269 /// in local 2 global correspondance.
270 int *_ptOnDomains;
271 /// Local 2 global array for each subdomain (partition)
272 int *_local2global;
273 /// global 2 local array (partition)
274 int *_global2local;
275 ///
276 FathersStrips* _interco;
277 /// For global indices, store the domain containing it :
278 int* _glob2dom;
279 int **_loc2glob_diag;
280 int **_loc2glob_offdiag;
281 bool _isSym;
282 CSR_indirect *_csr_diag;
283 CSR_indirect *_csr_offdiag;
284 };
285 }
286
287 #endif