Home | History | Annotate | Download | only in SparseLU 
      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 StorageIndex>
     47 void SparseLUImpl<Scalar,StorageIndex>::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 parent;
     52   relax_end.setConstant(emptyIdxLU);
     53   descendants.setZero();
     54   for (Index 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 (Index 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) = StorageIndex(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