src/SparseLU/SparseLU_relax_snode.h

0001 // This file is part of Eigen, a lightweight C++ template library
0002 // for linear algebra.
0003 //
0004 // Copyright (C) 2012 Désiré Nuentsa-Wakam <desire.nuentsa_wakam@inria.fr>
0005 //
0006 // This Source Code Form is subject to the terms of the Mozilla
0007 // Public License v. 2.0. If a copy of the MPL was not distributed
0008 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
0009
0010 /* This file is a modified version of heap_relax_snode.c file in SuperLU
0011  * -- SuperLU routine (version 3.0) --
0012  * Univ. of California Berkeley, Xerox Palo Alto Research Center,
0013  * and Lawrence Berkeley National Lab.
0014  * October 15, 2003
0015  *
0016  * Copyright (c) 1994 by Xerox Corporation.  All rights reserved.
0017  *
0018  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY
0019  * EXPRESSED OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
0020  *
0021  * Permission is hereby granted to use or copy this program for any
0022  * purpose, provided the above notices are retained on all copies.
0023  * Permission to modify the code and to distribute modified code is
0024  * granted, provided the above notices are retained, and a notice that
0025  * the code was modified is included with the above copyright notice.
0026  */
0027
0028 #ifndef SPARSELU_RELAX_SNODE_H
0029 #define SPARSELU_RELAX_SNODE_H
0030
0031 namespace RivetEigen {
0032
0033 namespace internal {
0034
0035 /**
0036  * \brief Identify the initial relaxed supernodes
0037  *
0038  * This routine is applied to a column elimination tree.
0039  * It assumes that the matrix has been reordered according to the postorder of the etree
0040  * \param n  the number of columns
0041  * \param et elimination tree
0042  * \param relax_columns Maximum number of columns allowed in a relaxed snode
0043  * \param descendants Number of descendants of each node in the etree
0044  * \param relax_end last column in a supernode
0045  */
0046 template <typename Scalar, typename StorageIndex>
0047 void SparseLUImpl<Scalar,StorageIndex>::relax_snode (const Index n, IndexVector& et, const Index relax_columns, IndexVector& descendants, IndexVector& relax_end)
0048 {
0049
0050   // compute the number of descendants of each node in the etree
0051   Index parent;
0052   relax_end.setConstant(emptyIdxLU);
0053   descendants.setZero();
0054   for (Index j = 0; j < n; j++)
0055   {
0056     parent = et(j);
0057     if (parent != n) // not the dummy root
0058       descendants(parent) += descendants(j) + 1;
0059   }
0060   // Identify the relaxed supernodes by postorder traversal of the etree
0061   Index snode_start; // beginning of a snode
0062   for (Index j = 0; j < n; )
0063   {
0064     parent = et(j);
0065     snode_start = j;
0066     while ( parent != n && descendants(parent) < relax_columns )
0067     {
0068       j = parent;
0069       parent = et(j);
0070     }
0071     // Found a supernode in postordered etree, j is the last column
0072     relax_end(snode_start) = StorageIndex(j); // Record last column
0073     j++;
0074     // Search for a new leaf
0075     while (descendants(j) != 0 && j < n) j++;
0076   } // End postorder traversal of the etree
0077
0078 }
0079
0080 } // end namespace internal
0081
0082 } // end namespace RivetEigen
0083 #endif