/*! \file SparseRenumbering.cpp \brief tridiagonal factorization algorithm with Cuthill-McKee \author François-Xavier Roux, ONERA, Laboratoire Jacques-Louis Lions \author Atsushi Suzuki, Laboratoire Jacques-Louis Lions \date Jul. 12th 2015 \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 . // #include #include #include #include #include "Algebra/SparseRenumbering.hpp" #include "Driver/DissectionDefault.hpp" #include "Compiler/arithmetic.hpp" #include "Compiler/DissectionIO.hpp" using std::list; void CMK_number(const int dim, const int *ptrows, const int *indcols, vector &new2old, const bool verbose, FILE *fp) { vector list, indic, connect; vector mask; int i1_prev, i2_prev, i0, i1; double profile, min_profile; connect.resize(dim); list.resize(dim); indic.resize(dim); mask.resize(dim); // compute initial profile i1_prev = 0; i2_prev = indcols[ptrows[0]]; for (int k = (ptrows[0] + 1); k < ptrows[1]; k++) { i2_prev = indcols[k] > i2_prev ? indcols[k] : i2_prev; } min_profile = ((double)(i2_prev - i1_prev + 2) * (double)(i2_prev - i1_prev + 1)) * 0.5; while (i2_prev < (dim - 1)) { int i1 = i2_prev + 1; int i2 = indcols[ptrows[i1_prev]]; for (int k = (ptrows[i1_prev] + 1); k < ptrows[i2_prev + 1]; k++) { i2 = indcols[k] > i2 ? indcols[k] : i2; } min_profile += (double)(i2 - i1 + 2) * (double)(i2 - i1 + 1) * 0.5; i1_prev = i1; i2_prev = i2; } diss_printf(verbose, fp, "%s %d : Cuthill McKee renumbering : init block : %g :: ", __FILE__, __LINE__, min_profile); // initialize frontal renumbering from an excentric point for (int i = 0; i < dim; i++) { connect[i] = ptrows[i + 1] - ptrows[i]; mask[i] = false; } i0 = 0; // initialization : critical when connent[] == dim { int imin = dim; // find index that attains minimun of connect[] for (int i = 0; i < dim; i++) { if (imin > connect[i]) { imin = connect[i]; i0 = i; } } } mask[i0] = true; profile = frontal_numb(dim, ptrows, indcols, i0, list, indic, connect); i1 = list[dim - 1]; diss_printf(verbose, fp, "- > node %d : %g :: ", i0, profile); if (profile < min_profile) { min_profile = profile; } else { for (int i = 0; i < dim; i++) { list[i] = i; } } profile = min_profile; min_profile = min_profile + 1.0; // repeat frontal numbering as long as profile improves while (profile < min_profile) { min_profile = profile; for (int i = 0; i < dim; i++) { new2old[i] = list[i]; } for (int i = 0; i < dim; i++) { connect[i] = ptrows[i + 1] - ptrows[i]; } { i0 = 0; // initialization : critical when connent[] == dim int imin = dim; for (int k = ptrows[i1]; k < ptrows[i1 + 1]; k++) { const int ii = indcols[k]; if (imin > connect[ii]) { imin = connect[ii]; i0 = ii; } } if (mask[i0]) { for (int i = (dim - 1); i >=0; i--) { if (!mask[list[i]]) { i0 = list[i]; break; } } } } mask[i0] = true; profile = frontal_numb(dim, ptrows, indcols, i0, list, indic, connect); i1 = list[dim - 1]; diss_printf(verbose, fp, "- > node: %d : %g :: ", i0, profile); } // while diss_printf(verbose, fp, "-> optimazied : %g\n", min_profile); } double frontal_numb(const int dim, const int *ptrows, const int *indcols, const int i0, vector &list, vector &indic, vector &connect) { int n, nn, i1, i2, i1_prev, i2_prev, k1, k2; double profile; // compute nodal connectivity degree for (int i = 0; i < dim; i++) { connect[i] = ptrows[i + 1] - ptrows[i]; } #if 1 for (int i = 0; i < dim; i++) { indic[i] = 0; } n = 0; nn = (-1); list[0] = i0; indic[i0] = 1; while (n < (dim - 1)) { nn++; int j = list[nn]; // renumber un-numbered neigbours of j, in increasing connectivity order int k = 0; for (int l = ptrows[j]; l < ptrows[j + 1]; l++) { const int i = indcols[l]; if (indic[i] == 0) { int ki = 1; for ( ; ki <= k; ki++) { if (connect[i] < connect[list[n + ki]]) { break; } } k++; for (int kk = k; kk >= (ki + 1); kk--) { list[n + kk] = list[n + kk - 1]; } list[n + ki] = i; } // if (indic[i] == 0) } // update connectivity degree of un-numbered nodes for (int kk = (n + 1); kk <= (n + k); kk++) { const int ii = list[kk]; for (int m = ptrows[ii]; m < ptrows[ii + 1]; m++) { connect[indcols[m]]--; } } for (int kk = (n + 1); kk <= (n + k); kk++) { indic[list[kk]] = 1; } n += k; } // while (n < (dim - 1)) // build old to new correspondance for (int i = 0; i < dim; i++) { indic[list[i]] = i; } #else std::list idexlist; vector mask; mask.resize(dim, false); idexlist.push_back(i0); std::list::iterator it = idexlist.begin(); mask[(*it)] = true; n = 0; std::list::iterator nt = idexlist.begin(); while (n < (dim - 1)) { int k = 0; for (int l = ptrows[(*it)]; l < ptrows[(*it) + 1]; l++) { const int ii = indcols[l]; if (!mask[ii]) { bool flag = false; std::list::iterator kt = nt; ++kt; for (int kk = 0 ; kk < k; kk++, ++kt) { if (connect[ii] < connect[(*kt)]) { idexlist.insert(kt, ii); flag = true; break; } } if (!flag) { idexlist.push_back(ii); } k++; } } ++it; std::list::iterator kt = nt; int kk = 0; for ( ; kk < k; ++kt, kk++) { for (int m = ptrows[(*kt)]; m < ptrows[(*kt) + 1]; m++) { connect[indcols[m]]--; } mask[(*kt)] = true; ++nt; } n += k; } { int i = 0; std::list::iterator it = idexlist.begin(); for (; it != idexlist.end(); ++it, i++) { list[i] = (*it); indic[(*it)] = i; } } idexlist.clear(); #endif // compute profile i1_prev = 0; k1 = ptrows[list[i1_prev]]; k2 = ptrows[list[i1_prev] + 1]; i2_prev = indic[indcols[k1]]; for (int k = (k1 + 1); k < k2; k++) { i2_prev = indic[indcols[k]] > i2_prev ? indic[indcols[k]] : i2_prev; } profile = ((double)(i2_prev - i1_prev + 1) * (double)(i2_prev - i1_prev + 2) * 0.5); while (i2_prev < (dim - 1)) { i1 = i2_prev + 1; i2 = i1; for (int i = i1_prev; i <= i2_prev; i++) { k1 = ptrows[list[i]]; k2 = ptrows[list[i] + 1]; i2 = std::max((int)i2, (int)indic[indcols[k1]]); for (int k = (k1 + 1); k < k2; k++) { i2 = indic[indcols[k]] > i2 ? indic[indcols[k]] : i2; } } profile += ((double)(i2 - i1 + 1) * (double)(i2 - i1 + 2) * 0.5); i1_prev = i1; i2_prev = i2; } return profile; } int point_front(const int dim, const int *ptrows, const int *indcols, vector &new2old, vector &p_front, const bool verbose, FILE *fp) { int nfront, ilast; vector old2new, p_front1; vector mask; const int size_thrs = 24; old2new.resize(dim); for (int i = 0; i < dim; i++) { old2new[new2old[i]] = i; } p_front.resize(dim + 1); // for safty nfront = 0; p_front[0] = 0; ilast = (-1); while (ilast < (dim - 1)) { // loop ilast ilast++; bool flag_cont = false; bool flag_break = false; const int ii = new2old[ilast]; nfront++; int isup = (-1); for (int k = ptrows[ii]; k < ptrows[ii + 1]; k++) { const int jj = old2new[indcols[k]]; isup = jj > isup ? jj : isup; } p_front[nfront] = isup + 1; while (isup > ilast) { ilast = isup; for (int i = p_front[nfront - 1]; i < p_front[nfront]; i++) { const int ii = new2old[i]; for (int k = ptrows[ii]; k < ptrows[ii + 1]; k++) { const int jj = old2new[indcols[k]]; isup = jj > isup ? jj : isup; } } // loop : i if (isup == ilast) { flag_cont = true; break; // continue loop_ilast } nfront++; p_front[nfront] = isup + 1; if (isup == (dim - 1)) { flag_break = true; break; // exit loop_ilast } } if (flag_cont) { continue; } if (flag_break) { break; } } // loop ilast old2new.clear(); mask.resize(nfront + 1); p_front1.resize(nfront + 1); for (int k = 0; k < nfront; k++) { const int itmp = p_front[k + 1] - p_front[k]; if (itmp >= size_thrs) { mask[k] = true; } else { mask[k] = false; } } mask[nfront] = true; int n = 0; { int k = 0; p_front1[0] = p_front[0]; int k0 = k; while (k < nfront) { int flag = 0; if (!mask[k0]) { if (!mask[k + 1]) { if ((p_front[k + 1] - p_front[k0]) < size_thrs) { flag = 2; } else { flag = (-2); } } else { if ((k == 0) && mask[1]) { flag = 2; } else { if ((k0 == k) || (k == (nfront - 1))) { flag = 0; } else { flag = (-1); } } } // if (!mask[k + 1]) } // if (!mask[k0]) else { if (k == (nfront - 2) && !mask[nfront - 1]) { flag = 1; } } switch (flag) { case 1: p_front1[n + 1] = p_front[k + 2]; n++; k += 2; k0 = k; break; case (-2): p_front1[n + 1] = p_front[k]; n++; k0 = k; break; case (-1): p_front1[n + 1] = p_front[k]; p_front1[n + 2] = p_front[k + 1]; n += 2; k++; k0 = k; break; case (0): p_front1[n + 1] = p_front[k + 1]; n++; k++; k0 = k; break; case 2: k++; break; } } // while (k < nfront) } // scope for k, n etc. if ((p_front1[0] != 0)|| (p_front1[n] != p_front[nfront])) { diss_printf(verbose, fp, "%s %d : error %d -> %d\n", __FILE__, __LINE__, p_front[nfront], p_front1[n]); exit(-1); } nfront = n; p_front.resize(nfront + 1); for (int k = 0; k <= n; k++) { p_front[k] = p_front1[k]; } return nfront; } int getColorMaskCSR(int *color_mask, const CSR_indirect *csr, const bool verbose, FILE *fp) { const int dim = csr->n; int *prow = csr->ptRows; int *indcols = csr->indCols; for (int i = 0; i < dim; i++) { color_mask[i] = (-1); } list graph_start; int num_isolated = 0; for (int i = 0 ; i < dim; i++) { if ((prow[i] + 1) == prow[i + 1]) { num_isolated++; color_mask[i] = 0; } } if (num_isolated > 0) { diss_printf(verbose, fp, "%s %d : isolated = %d\n", __FILE__, __LINE__, num_isolated); } int color = 0; for (int i = 0; i < dim; i++) { if (color_mask[i] == (-1)) { color++; color_mask[i] = color; graph_start.clear(); graph_start.push_back(i); for (list::iterator it = graph_start.begin(); it != graph_start.end(); ++it) { for (int k = prow[(*it)]; k < prow[(*it) + 1]; k++) { if (color_mask[indcols[k]] == (-1)) { color_mask[indcols[k]] = color; graph_start.push_back(indcols[k]); } } } // loop : it } } // loop : i // post process merge color with small size into previous color int reduced = 0; diss_printf(verbose, fp, "%s %d : before color = %d\n", __FILE__, __LINE__, color); int m = 1; while (m <= color) { int count = 0; for (int i = 0; i < dim; i++) { if (color_mask[i] == m) { count++; } } if ((count <= DIM_AUG_KERN) && (color > 1)){ // to treat very small matrix reduced++; color--; for (int i = 0; i < dim; i++) { if (color_mask[i] == m) { color_mask[i] = (-1); } else if (color_mask[i] > m) { color_mask[i]--; } } } else { m++; } } diss_printf(verbose, fp, "%s %d : after fused = %d color = %d\n", __FILE__, __LINE__, reduced, color); return color; }