Line data    Source code

       1              : /*
       2              : Copyright (c) 2003, The Regents of the University of California, through
       3              : Lawrence Berkeley National Laboratory (subject to receipt of any required 
       4              : approvals from U.S. Dept. of Energy) 
       5              : 
       6              : All rights reserved. 
       7              : 
       8              : The source code is distributed under BSD license, see the file License.txt
       9              : at the top-level directory.
      10              : */
      11              : /*
      12              :  * -- SuperLU routine (version 2.0) --
      13              :  * Univ. of California Berkeley, Xerox Palo Alto Research Center,
      14              :  * and Lawrence Berkeley National Lab.
      15              :  * November 15, 1997
      16              :  *
      17              :  * Copyright (c) 1994 by Xerox Corporation.  All rights reserved.
      18              :  *
      19              :  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY
      20              :  * EXPRESSED OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
      21              :  *
      22              :  * Permission is hereby granted to use or copy this program for any
      23              :  * purpose, provided the above notices are retained on all copies.
      24              :  * Permission to modify the code and to distribute modified code is
      25              :  * granted, provided the above notices are retained, and a notice that
      26              :  * the code was modified is included with the above copyright notice.
      27              :  */
      28              : /*! \file
      29              :  * \brief Identify initial relaxed supernodes
      30              :  *
      31              :  * \ingroup Common
      32              :  */
      33              : 
      34              : #include "slu_ddefs.h"
      35              : /*! \brief
      36              :  *
      37              :  * <pre>
      38              :  * Purpose
      39              :  * =======
      40              :  *    relax_snode() - Identify the initial relaxed supernodes, assuming that 
      41              :  *    the matrix has been reordered according to the postorder of the etree.
      42              :  * </pre>
      43              :  */ 
      44              : void
      45            0 : relax_snode (
      46              :              const     int n,
      47              :                   const int *et,           /* column elimination tree */
      48              :              const int relax_columns, /* max no of columns allowed in a
      49              :                                          relaxed snode */
      50              :              int       *descendants,  /* no of descendants of each node
      51              :                                          in the etree */
      52              :              int       *relax_end     /* last column in a supernode */
      53              :              )
      54              : {
      55              : 
      56              :     register int j, parent;
      57              :     register int snode_start;   /* beginning of a snode */
      58              :     
      59            0 :     ifill (relax_end, n, SLU_EMPTY);
      60            0 :     for (j = 0; j < n; j++) descendants[j] = 0;
      61              : 
      62              :     /* Compute the number of descendants of each node in the etree */
      63            0 :     for (j = 0; j < n; j++) {
      64            0 :         parent = et[j];
      65            0 :         if ( parent != n )  /* not the dummy root */
      66            0 :             descendants[parent] += descendants[j] + 1;
      67              :     }
      68              : 
      69              :     /* Identify the relaxed supernodes by postorder traversal of the etree. */
      70            0 :     for (j = 0; j < n; ) { 
      71            0 :         parent = et[j];
      72              :         snode_start = j;
      73            0 :         while ( parent != n && descendants[parent] < relax_columns ) {
      74              :             j = parent;
      75            0 :             parent = et[j];
      76              :         }
      77              :         /* Found a supernode with j being the last column. */
      78            0 :         relax_end[snode_start] = j;             /* Last column is recorded */
      79            0 :         j++;
      80              :         /* Search for a new leaf */
      81            0 :         while ( descendants[j] != 0 && j < n ) j++;
      82              :     }
      83              : 
      84              :     /*printf("No of relaxed snodes: %d; relaxed columns: %d\n", 
      85              :                 nsuper, no_relaxed_col); */
      86            0 : }