1 // This file is part of Eigen, a lightweight C++ template library 2 // for linear algebra. 3 // 4 // Copyright (C) 2012 Dsir Nuentsa-Wakam <desire.nuentsa_wakam (at) inria.fr> 5 // 6 // This Source Code Form is subject to the terms of the Mozilla 7 // Public License v. 2.0. If a copy of the MPL was not distributed 8 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/. 9 10 /* This file is a modified version of heap_relax_snode.c file in SuperLU 11 * -- SuperLU routine (version 3.0) -- 12 * Univ. of California Berkeley, Xerox Palo Alto Research Center, 13 * and Lawrence Berkeley National Lab. 14 * October 15, 2003 15 * 16 * Copyright (c) 1994 by Xerox Corporation. All rights reserved. 17 * 18 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY 19 * EXPRESSED OR IMPLIED. ANY USE IS AT YOUR OWN RISK. 20 * 21 * Permission is hereby granted to use or copy this program for any 22 * purpose, provided the above notices are retained on all copies. 23 * Permission to modify the code and to distribute modified code is 24 * granted, provided the above notices are retained, and a notice that 25 * the code was modified is included with the above copyright notice. 26 */ 27 28 #ifndef SPARSELU_RELAX_SNODE_H 29 #define SPARSELU_RELAX_SNODE_H 30 31 namespace Eigen { 32 33 namespace internal { 34 35 /** 36 * \brief Identify the initial relaxed supernodes 37 * 38 * This routine is applied to a column elimination tree. 39 * It assumes that the matrix has been reordered according to the postorder of the etree 40 * \param n the number of columns 41 * \param et elimination tree 42 * \param relax_columns Maximum number of columns allowed in a relaxed snode 43 * \param descendants Number of descendants of each node in the etree 44 * \param relax_end last column in a supernode 45 */ 46 template <typename Scalar, typename Index> 47 void SparseLUImpl<Scalar,Index>::relax_snode (const Index n, IndexVector& et, const Index relax_columns, IndexVector& descendants, IndexVector& relax_end) 48 { 49 50 // compute the number of descendants of each node in the etree 51 Index j, parent; 52 relax_end.setConstant(emptyIdxLU); 53 descendants.setZero(); 54 for (j = 0; j < n; j++) 55 { 56 parent = et(j); 57 if (parent != n) // not the dummy root 58 descendants(parent) += descendants(j) + 1; 59 } 60 // Identify the relaxed supernodes by postorder traversal of the etree 61 Index snode_start; // beginning of a snode 62 for (j = 0; j < n; ) 63 { 64 parent = et(j); 65 snode_start = j; 66 while ( parent != n && descendants(parent) < relax_columns ) 67 { 68 j = parent; 69 parent = et(j); 70 } 71 // Found a supernode in postordered etree, j is the last column 72 relax_end(snode_start) = j; // Record last column 73 j++; 74 // Search for a new leaf 75 while (descendants(j) != 0 && j < n) j++; 76 } // End postorder traversal of the etree 77 78 } 79 80 } // end namespace internal 81 82 } // end namespace Eigen 83 #endif 84