Line data Source code
1 : /*! \file
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 : /*! @file dpruneL.c
13 : * \brief Prunes the L-structure
14 : *
15 : *<pre>
16 : * -- SuperLU routine (version 2.0) --
17 : * Univ. of California Berkeley, Xerox Palo Alto Research Center,
18 : * and Lawrence Berkeley National Lab.
19 : * November 15, 1997
20 : *
21 : * Copyright (c) 1994 by Xerox Corporation. All rights reserved.
22 : *
23 : * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY
24 : * EXPRESSED OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
25 : *
26 : * Permission is hereby granted to use or copy this program for any
27 : * purpose, provided the above notices are retained on all copies.
28 : * Permission to modify the code and to distribute modified code is
29 : * granted, provided the above notices are retained, and a notice that
30 : * the code was modified is included with the above copyright notice.
31 : *</pre>
32 : */
33 :
34 :
35 : #include "slu_ddefs.h"
36 :
37 : /*! \brief
38 : *
39 : * <pre>
40 : * Purpose
41 : * =======
42 : * Prunes the L-structure of supernodes whose L-structure
43 : * contains the current pivot row "pivrow"
44 : * </pre>
45 : */
46 :
47 : void
48 0 : dpruneL(
49 : const int jcol, /* in */
50 : const int *perm_r, /* in */
51 : const int pivrow, /* in */
52 : const int nseg, /* in */
53 : const int *segrep, /* in */
54 : const int *repfnz, /* in */
55 : int_t *xprune, /* out */
56 : GlobalLU_t *Glu /* modified - global LU data structures */
57 : )
58 : {
59 :
60 : double utemp;
61 : int jsupno, irep, irep1, kmin, kmax, krow, movnum;
62 : int_t i, ktemp, minloc, maxloc;
63 : int do_prune; /* logical variable */
64 : int *xsup, *supno;
65 : int_t *lsub, *xlsub;
66 : double *lusup;
67 : int_t *xlusup;
68 :
69 0 : xsup = Glu->xsup;
70 0 : supno = Glu->supno;
71 0 : lsub = Glu->lsub;
72 0 : xlsub = Glu->xlsub;
73 0 : lusup = (double *) Glu->lusup;
74 0 : xlusup = Glu->xlusup;
75 :
76 : /*
77 : * For each supernode-rep irep in U[*,j]
78 : */
79 0 : jsupno = supno[jcol];
80 0 : for (i = 0; i < nseg; i++) {
81 :
82 0 : irep = segrep[i];
83 0 : irep1 = irep + 1;
84 : do_prune = FALSE;
85 :
86 : /* Don't prune with a zero U-segment */
87 0 : if ( repfnz[irep] == SLU_EMPTY )
88 0 : continue;
89 :
90 : /* If a snode overlaps with the next panel, then the U-segment
91 : * is fragmented into two parts -- irep and irep1. We should let
92 : * pruning occur at the rep-column in irep1's snode.
93 : */
94 0 : if ( supno[irep] == supno[irep1] ) /* Don't prune */
95 0 : continue;
96 :
97 : /*
98 : * If it has not been pruned & it has a nonz in row L[pivrow,i]
99 : */
100 0 : if ( supno[irep] != jsupno ) {
101 0 : if ( xprune[irep] >= xlsub[irep1] ) {
102 0 : kmin = xlsub[irep];
103 0 : kmax = xlsub[irep1] - 1;
104 0 : for (krow = kmin; krow <= kmax; krow++)
105 0 : if ( lsub[krow] == pivrow ) {
106 : do_prune = TRUE;
107 : break;
108 : }
109 : }
110 :
111 0 : if ( do_prune ) {
112 :
113 : /* Do a quicksort-type partition
114 : * movnum=TRUE means that the num values have to be exchanged.
115 : */
116 : movnum = FALSE;
117 0 : if ( irep == xsup[supno[irep]] ) /* Snode of size 1 */
118 : movnum = TRUE;
119 :
120 0 : while ( kmin <= kmax ) {
121 :
122 0 : if ( perm_r[lsub[kmax]] == SLU_EMPTY )
123 0 : kmax--;
124 0 : else if ( perm_r[lsub[kmin]] != SLU_EMPTY )
125 0 : kmin++;
126 : else { /* kmin below pivrow (not yet pivoted), and kmax
127 : * above pivrow: interchange the two subscripts
128 : */
129 : ktemp = lsub[kmin];
130 0 : lsub[kmin] = lsub[kmax];
131 0 : lsub[kmax] = ktemp;
132 :
133 : /* If the supernode has only one column, then we
134 : * only keep one set of subscripts. For any subscript
135 : * interchange performed, similar interchange must be
136 : * done on the numerical values.
137 : */
138 0 : if ( movnum ) {
139 0 : minloc = xlusup[irep] + (kmin - xlsub[irep]);
140 0 : maxloc = xlusup[irep] + (kmax - xlsub[irep]);
141 0 : utemp = lusup[minloc];
142 0 : lusup[minloc] = lusup[maxloc];
143 0 : lusup[maxloc] = utemp;
144 : }
145 :
146 0 : kmin++;
147 0 : kmax--;
148 :
149 : }
150 :
151 : } /* while */
152 :
153 0 : xprune[irep] = kmin; /* Pruning */
154 :
155 : #ifdef CHK_PRUNE
156 : printf(" After dpruneL(),using col %d: xprune[%d] = %d\n",
157 : jcol, irep, kmin);
158 : #endif
159 : } /* if do_prune */
160 :
161 : } /* if */
162 :
163 : } /* for each U-segment... */
164 0 : }
|
