/*! \file BisectionTree.hpp \brief ordeing by graph decomposer, SCOTCH or METIS \author Xavier Juvigny, ONERA \date Jul. 2nd 2012 \date Nov. 30th 2016 */ // This file is part of Dissection // // Dissection is free software: you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // // Linking Dissection statically or dynamically with other modules is making // a combined work based on Disssection. Thus, the terms and conditions of // the GNU General Public License cover the whole combination. // // As a special exception, the copyright holders of Dissection give you // permission to combine Dissection program with free software programs or // libraries that are released under the GNU LGPL and with independent modules // that communicate with Dissection solely through the Dissection-fortran // interface. You may copy and distribute such a system following the terms of // the GNU GPL for Dissection and the licenses of the other code concerned, // provided that you include the source code of that other code when and as // the GNU GPL requires distribution of source code and provided that you do // not modify the Dissection-fortran interface. // // Note that people who make modified versions of Dissection are not obligated // to grant this special exception for their modified versions; it is their // choice whether to do so. The GNU General Public License gives permission to // release a modified version without this exception; this exception also makes // it possible to release a modified version which carries forward this // exception. If you modify the Dissection-fortran interface, this exception // does not apply to your modified version of Dissection, and you must remove // this exception when you distribute your modified version. // // This exception is an additional permission under section 7 of the GNU // General Public License, version 3 ("GPLv3") // // Dissection is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with Dissection. If not, see . // // ============================================================== // == Bisection tree : stored by components in 1D arrays == // ============================================================== #ifndef _DISSECTION_SPLITTERS_BISECTIONTREE_HPP_ #define _DISSECTION_SPLITTERS_BISECTIONTREE_HPP_ #include #include "Splitters/BitManipulations.hpp" #include "Splitters/BisectionInterConnection.hpp" #include "Splitters/Splitter.hpp" #include "Algebra/CSR_matrix.hpp" namespace Dissection { /** @brief Nested Bisection tree The nested bisection tree is the core of the symbolic factorization. Nodes are numbered from root,starting at 1, to leaves by layer order. By example : (layer level) ----------- 1 0 / \ 2 3 1 /\ /\ 4 5 6 7 2 Data are stored components by components, ordered as above : [D1,D2,D3,D4,D5,D6,D7] Each layer l data begin at 2^l (0 <= l < number of layers) A node n is in layer highest_one_idx(n) The brother of a node n (node sharing same father) is n^1 (^ means xor operation as C convention). Ancestors are n>>p where 0 < p < number of layers - level of domain */ class Tree { public: /**@name Constructors and destructor */ //@{ /** @brief Build bisection tree From the sparse matrix CSR structure, build the bisection tree for symbolic factorization computing some block permutations to speed-up data transfert between blocks. @param dim Dimension of the sparse matrix @param ptRows Indices pointing on the beginning of each row of the sparse matrix. The last value ptRows[dim] provides the number of non zero coefficients of the sparse matrix. @param indCols Column indice of each non zero coefficients of the sparse matrix. Values must be stored and sorted (increasing) by row @param nbMaxLevel Maximal number of iteration for the bisection method. @param minSize Minimal number of nodes per subdomains in the leaves of the tree. @param spltFct The nested bisection library function to use By default, Scotch is used to do nested bisection @param checkData If true, verify some consistencies in the given sparse matrix structure. If false, assume than provided sparse matrix structure is consistency. */ Tree(FILE *fp, bool &berr, unsigned dim, const CSR_indirect *csr, const bool isSym, //const bool isLower, const int *remap_eqn, //const int *remap_indcols, unsigned nbMaxLevel=8, unsigned minSize = 120, splitter spltFct = NULL, bool checkData = false, bool verbose = true); /** @brief Destructor */ ~Tree(); //@} /** @name Getters and setters */ //@{ /// Return index of the brother (i.e having same father) node /// of a node nd. static int selfIndex(unsigned nd) { return (int)(nd - 1); } static int Index2Node(unsigned nd) { return (int)(nd + 1); } static unsigned brotherIndex(unsigned nd) { return (nd ^ 1); } /// Return index of the father node index of a node nd static unsigned fatherIndex(unsigned nd) { return (nd / 2); } /// Return index of nth forerunner of domain nd : static unsigned nthfatherIndex(unsigned nd, unsigned nth) { return (nd >> nth); } /// Return index of the first child index for node nd : static unsigned childIndex(unsigned nd) { return (nd * 2); } /// Return layer number where lies the domain nd : static unsigned nodeLayer(unsigned nd) { return highest_one_idx(nd); } /// Return unsigned NumberOfLevels() { return _nbLevels; } unsigned NumberOfSubdomains() { return _nbDoms; } // unsigned NumberOfSubdomains(unsigned level) { // (_sbLevels - 1) == (void) if (level < _nbLevels) { return ((1 << (level + 1)) - 1); // including own level } else { return 0U; } } /// Return number of internal nodes of a domain nd (>=1) unsigned sizeOfDomain(unsigned nd) const { return _sizeOfDomains[selfIndex(nd)]; } unsigned sizeOfFathersStrips(unsigned nd) const { return _sizeOfFathersStrips[selfIndex(nd)]; } /// Return connection between a domain nd (nd >= 1) and his ancestors const FathersStrips& getFathersStrips(unsigned nd) { return _interco[selfIndex(nd)]; } const CSR_indirect& getDiagCSR(unsigned nd) { return _csr_diag[selfIndex(nd)]; } const CSR_indirect& getOffdiagCSR(unsigned nd) { return _csr_offdiag[selfIndex(nd)]; } int *getDiagLoc2Glob(unsigned nd) { return _loc2glob_diag[selfIndex(nd)]; } int *getOffdiagLoc2Glob(unsigned nd) { return _loc2glob_offdiag[selfIndex(nd)]; } bool save(FILE* stream) const; /** @brief Load bisection tree contents */ bool load(FILE* stream) ; /** @brief Print information on bisection tree A verbose level can be provided. Depending of his value, informations printed are : >=1 : Some statistics data (number of domains, mean number of nodes per domains per layer, variance of number of nodes per domains,...) >=2 : Global indices of nodes contained per domains >=3 : Block permutation from a domain and his forerunnings @param verboseLevel Choose the level of verbose to print some information for dissection tree. */ void printInfo(FILE* stream, unsigned verboseLevel = 1) const; //@} private: bool _verbose; /* Allocate and fill an array with indices of domain containing each local index. The caller of this method must free the returned array. */ unsigned* compLoc2Dom(unsigned dim) const; /* Remove self references from the skeleton graph of the sparse matrix provided to the splitter */ void removeLoops(int dim, const int* ptRows, const int* indCols, int*& ptRows2, int*& indCols2); /* Do symbolic factorization */ FathersStrips* symbolicFactorization(SetOfStrips** connections); /* Renumbering interfaces to optimize number of strips */ void renumberingInterface(unsigned nperm, unsigned* perm, const SetOfStrips& paral, const SetOfStrips& parar, const SetOfStrips& seq, unsigned layer, unsigned iDom) const; void draw_csr(char *filename, int dim, const int *ptRows, const int *indCols, const int *ptRow_diag, const int *indVals, const unsigned *l2d); /// Number of levels done in nested bisection algorithm unsigned _nbDoms; unsigned _nbLevels; /// Number of nodes (internal only for each leaf) int *_sizeOfDomains; int *_sizeOfFathersStrips; /// Indice (starting at 0) of the beginning of each domain /// in local 2 global correspondance. int *_ptOnDomains; /// Local 2 global array for each subdomain (partition) int *_local2global; /// global 2 local array (partition) int *_global2local; /// FathersStrips* _interco; /// For global indices, store the domain containing it : int* _glob2dom; int **_loc2glob_diag; int **_loc2glob_offdiag; bool _isSym; CSR_indirect *_csr_diag; CSR_indirect *_csr_offdiag; }; } #endif