kusano 7d535a
kusano 7d535a
/*! @file spruneL.c
kusano 7d535a
 * \brief Prunes the L-structure
kusano 7d535a
 *
kusano 7d535a
 *
kusano 7d535a
 * -- SuperLU routine (version 2.0) --
kusano 7d535a
 * Univ. of California Berkeley, Xerox Palo Alto Research Center,
kusano 7d535a
 * and Lawrence Berkeley National Lab.
kusano 7d535a
 * November 15, 1997
kusano 7d535a
 *
kusano 7d535a
 * Copyright (c) 1994 by Xerox Corporation.  All rights reserved.
kusano 7d535a
 *
kusano 7d535a
 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY
kusano 7d535a
 * EXPRESSED OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
kusano 7d535a
 * 
kusano 7d535a
 * Permission is hereby granted to use or copy this program for any
kusano 7d535a
 * purpose, provided the above notices are retained on all copies.
kusano 7d535a
 * Permission to modify the code and to distribute modified code is
kusano 7d535a
 * granted, provided the above notices are retained, and a notice that
kusano 7d535a
 * the code was modified is included with the above copyright notice.
kusano 7d535a
 *
kusano 7d535a
 */
kusano 7d535a
kusano 7d535a
kusano 7d535a
#include "slu_sdefs.h"
kusano 7d535a
kusano 7d535a
/*! \brief
kusano 7d535a
 *
kusano 7d535a
 * 
kusano 7d535a
 * Purpose
kusano 7d535a
 * =======
kusano 7d535a
 *   Prunes the L-structure of supernodes whose L-structure
kusano 7d535a
 *   contains the current pivot row "pivrow"
kusano 7d535a
 * 
kusano 7d535a
 */
kusano 7d535a
kusano 7d535a
void
kusano 7d535a
spruneL(
kusano 7d535a
       const int  jcol,	     /* in */
kusano 7d535a
       const int  *perm_r,   /* in */
kusano 7d535a
       const int  pivrow,    /* in */
kusano 7d535a
       const int  nseg,	     /* in */
kusano 7d535a
       const int  *segrep,   /* in */
kusano 7d535a
       const int  *repfnz,   /* in */
kusano 7d535a
       int        *xprune,   /* out */
kusano 7d535a
       GlobalLU_t *Glu       /* modified - global LU data structures */
kusano 7d535a
       )
kusano 7d535a
{
kusano 7d535a
kusano 7d535a
    float     utemp;
kusano 7d535a
    int        jsupno, irep, irep1, kmin, kmax, krow, movnum;
kusano 7d535a
    int        i, ktemp, minloc, maxloc;
kusano 7d535a
    int        do_prune; /* logical variable */
kusano 7d535a
    int        *xsup, *supno;
kusano 7d535a
    int        *lsub, *xlsub;
kusano 7d535a
    float     *lusup;
kusano 7d535a
    int        *xlusup;
kusano 7d535a
kusano 7d535a
    xsup       = Glu->xsup;
kusano 7d535a
    supno      = Glu->supno;
kusano 7d535a
    lsub       = Glu->lsub;
kusano 7d535a
    xlsub      = Glu->xlsub;
kusano 7d535a
    lusup      = Glu->lusup;
kusano 7d535a
    xlusup     = Glu->xlusup;
kusano 7d535a
    
kusano 7d535a
    /*
kusano 7d535a
     * For each supernode-rep irep in U[*,j]
kusano 7d535a
     */
kusano 7d535a
    jsupno = supno[jcol];
kusano 7d535a
    for (i = 0; i < nseg; i++) {
kusano 7d535a
kusano 7d535a
	irep = segrep[i];
kusano 7d535a
	irep1 = irep + 1;
kusano 7d535a
	do_prune = FALSE;
kusano 7d535a
kusano 7d535a
	/* Don't prune with a zero U-segment */
kusano 7d535a
 	if ( repfnz[irep] == EMPTY )
kusano 7d535a
		continue;
kusano 7d535a
kusano 7d535a
     	/* If a snode overlaps with the next panel, then the U-segment 
kusano 7d535a
   	 * is fragmented into two parts -- irep and irep1. We should let
kusano 7d535a
	 * pruning occur at the rep-column in irep1's snode. 
kusano 7d535a
	 */
kusano 7d535a
	if ( supno[irep] == supno[irep1] ) 	/* Don't prune */
kusano 7d535a
		continue;
kusano 7d535a
kusano 7d535a
	/*
kusano 7d535a
	 * If it has not been pruned & it has a nonz in row L[pivrow,i]
kusano 7d535a
	 */
kusano 7d535a
	if ( supno[irep] != jsupno ) {
kusano 7d535a
	    if ( xprune[irep] >= xlsub[irep1] ) {
kusano 7d535a
		kmin = xlsub[irep];
kusano 7d535a
		kmax = xlsub[irep1] - 1;
kusano 7d535a
		for (krow = kmin; krow <= kmax; krow++) 
kusano 7d535a
		    if ( lsub[krow] == pivrow ) {
kusano 7d535a
			do_prune = TRUE;
kusano 7d535a
			break;
kusano 7d535a
		    }
kusano 7d535a
	    }
kusano 7d535a
	    
kusano 7d535a
    	    if ( do_prune ) {
kusano 7d535a
kusano 7d535a
	     	/* Do a quicksort-type partition
kusano 7d535a
	     	 * movnum=TRUE means that the num values have to be exchanged.
kusano 7d535a
	     	 */
kusano 7d535a
	        movnum = FALSE;
kusano 7d535a
	        if ( irep == xsup[supno[irep]] ) /* Snode of size 1 */
kusano 7d535a
			movnum = TRUE;
kusano 7d535a
kusano 7d535a
	        while ( kmin <= kmax ) {
kusano 7d535a
kusano 7d535a
	    	    if ( perm_r[lsub[kmax]] == EMPTY ) 
kusano 7d535a
			kmax--;
kusano 7d535a
		    else if ( perm_r[lsub[kmin]] != EMPTY )
kusano 7d535a
			kmin++;
kusano 7d535a
		    else { /* kmin below pivrow (not yet pivoted), and kmax
kusano 7d535a
                            * above pivrow: interchange the two subscripts
kusano 7d535a
			    */
kusano 7d535a
		        ktemp = lsub[kmin];
kusano 7d535a
		        lsub[kmin] = lsub[kmax];
kusano 7d535a
		        lsub[kmax] = ktemp;
kusano 7d535a
kusano 7d535a
			/* If the supernode has only one column, then we
kusano 7d535a
 			 * only keep one set of subscripts. For any subscript 
kusano 7d535a
			 * interchange performed, similar interchange must be 
kusano 7d535a
			 * done on the numerical values.
kusano 7d535a
 			 */
kusano 7d535a
		        if ( movnum ) {
kusano 7d535a
		    	    minloc = xlusup[irep] + (kmin - xlsub[irep]);
kusano 7d535a
		    	    maxloc = xlusup[irep] + (kmax - xlsub[irep]);
kusano 7d535a
			    utemp = lusup[minloc];
kusano 7d535a
		  	    lusup[minloc] = lusup[maxloc];
kusano 7d535a
			    lusup[maxloc] = utemp;
kusano 7d535a
		        }
kusano 7d535a
kusano 7d535a
		        kmin++;
kusano 7d535a
		        kmax--;
kusano 7d535a
kusano 7d535a
		    }
kusano 7d535a
kusano 7d535a
	        } /* while */
kusano 7d535a
kusano 7d535a
	        xprune[irep] = kmin;	/* Pruning */
kusano 7d535a
kusano 7d535a
#ifdef CHK_PRUNE
kusano 7d535a
	printf("    After spruneL(),using col %d:  xprune[%d] = %d\n", 
kusano 7d535a
			jcol, irep, kmin);
kusano 7d535a
#endif
kusano 7d535a
	    } /* if do_prune */
kusano 7d535a
kusano 7d535a
	} /* if */
kusano 7d535a
kusano 7d535a
    } /* for each U-segment... */
kusano 7d535a
}