00001 // This file is part of Eigen, a lightweight C++ template library 00002 // for linear algebra. 00003 // 00004 // Copyright (C) 2012 Désiré Nuentsa-Wakam <desire.nuentsa_wakam@inria.fr> 00005 // 00006 // This Source Code Form is subject to the terms of the Mozilla 00007 // Public License v. 2.0. If a copy of the MPL was not distributed 00008 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/. 00009 00010 /* This file is a modified version of heap_relax_snode.c file in SuperLU 00011 * -- SuperLU routine (version 3.0) -- 00012 * Univ. of California Berkeley, Xerox Palo Alto Research Center, 00013 * and Lawrence Berkeley National Lab. 00014 * October 15, 2003 00015 * 00016 * Copyright (c) 1994 by Xerox Corporation. All rights reserved. 00017 * 00018 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY 00019 * EXPRESSED OR IMPLIED. ANY USE IS AT YOUR OWN RISK. 00020 * 00021 * Permission is hereby granted to use or copy this program for any 00022 * purpose, provided the above notices are retained on all copies. 00023 * Permission to modify the code and to distribute modified code is 00024 * granted, provided the above notices are retained, and a notice that 00025 * the code was modified is included with the above copyright notice. 00026 */ 00027 00028 #ifndef SPARSELU_RELAX_SNODE_H 00029 #define SPARSELU_RELAX_SNODE_H 00030 00031 namespace Eigen { 00032 00033 namespace internal { 00034 00046 template <typename Scalar, typename Index> 00047 void SparseLUImpl<Scalar,Index>::relax_snode (const Index n, IndexVector& et, const Index relax_columns, IndexVector& descendants, IndexVector& relax_end) 00048 { 00049 00050 // compute the number of descendants of each node in the etree 00051 Index j, parent; 00052 relax_end.setConstant(emptyIdxLU); 00053 descendants.setZero(); 00054 for (j = 0; j < n; j++) 00055 { 00056 parent = et(j); 00057 if (parent != n) // not the dummy root 00058 descendants(parent) += descendants(j) + 1; 00059 } 00060 // Identify the relaxed supernodes by postorder traversal of the etree 00061 Index snode_start; // beginning of a snode 00062 for (j = 0; j < n; ) 00063 { 00064 parent = et(j); 00065 snode_start = j; 00066 while ( parent != n && descendants(parent) < relax_columns ) 00067 { 00068 j = parent; 00069 parent = et(j); 00070 } 00071 // Found a supernode in postordered etree, j is the last column 00072 relax_end(snode_start) = j; // Record last column 00073 j++; 00074 // Search for a new leaf 00075 while (descendants(j) != 0 && j < n) j++; 00076 } // End postorder traversal of the etree 00077 00078 } 00079 00080 } // end namespace internal 00081 00082 } // end namespace Eigen 00083 #endif