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 dsnode_dfs.c
13 : * \brief Determines the union of row structures of columns within the relaxed node
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 : * dsnode_dfs() - Determine the union of the row structures of those
43 : * columns within the relaxed snode.
44 : * Note: The relaxed snodes are leaves of the supernodal etree, therefore,
45 : * the portion outside the rectangular supernode must be zero.
46 : *
47 : * Return value
48 : * ============
49 : * 0 success;
50 : * >0 number of bytes allocated when run out of memory.
51 : * </pre>
52 : */
53 :
54 : int_t
55 0 : dsnode_dfs (
56 : const int jcol, /* in - start of the supernode */
57 : const int kcol, /* in - end of the supernode */
58 : const int_t *asub, /* in */
59 : const int_t *xa_begin, /* in */
60 : const int_t *xa_end, /* in */
61 : int_t *xprune, /* out */
62 : int *marker, /* modified */
63 : GlobalLU_t *Glu /* modified */
64 : )
65 : {
66 :
67 : int_t i, k, ifrom, ito, nextl, new_next, nzlmax;
68 : int nsuper, krow, kmark;
69 : int_t mem_error;
70 : int *xsup, *supno;
71 : int_t *lsub, *xlsub;
72 :
73 0 : xsup = Glu->xsup;
74 0 : supno = Glu->supno;
75 0 : lsub = Glu->lsub;
76 0 : xlsub = Glu->xlsub;
77 0 : nzlmax = Glu->nzlmax;
78 :
79 0 : nsuper = ++supno[jcol]; /* Next available supernode number */
80 0 : nextl = xlsub[jcol];
81 :
82 0 : for (i = jcol; i <= kcol; i++) {
83 : /* For each nonzero in A[*,i] */
84 0 : for (k = xa_begin[i]; k < xa_end[i]; k++) {
85 0 : krow = asub[k];
86 0 : kmark = marker[krow];
87 0 : if ( kmark != kcol ) { /* First time visit krow */
88 0 : marker[krow] = kcol;
89 0 : lsub[nextl++] = krow;
90 0 : if ( nextl >= nzlmax ) {
91 0 : mem_error = dLUMemXpand(jcol, nextl, LSUB, &nzlmax, Glu);
92 0 : if ( mem_error ) return (mem_error);
93 0 : lsub = Glu->lsub;
94 : }
95 : }
96 : }
97 0 : supno[i] = nsuper;
98 : }
99 :
100 : /* Supernode > 1, then make a copy of the subscripts for pruning */
101 0 : if ( jcol < kcol ) {
102 0 : new_next = nextl + (nextl - xlsub[jcol]);
103 0 : while ( new_next > nzlmax ) {
104 0 : mem_error = dLUMemXpand(jcol, nextl, LSUB, &nzlmax, Glu);
105 0 : if ( mem_error ) return (mem_error);
106 0 : lsub = Glu->lsub;
107 : }
108 : ito = nextl;
109 0 : for (ifrom = xlsub[jcol]; ifrom < nextl; )
110 0 : lsub[ito++] = lsub[ifrom++];
111 0 : for (i = jcol+1; i <= kcol; i++) xlsub[i] = nextl;
112 : nextl = ito;
113 : }
114 :
115 0 : xsup[nsuper+1] = kcol + 1;
116 0 : supno[kcol+1] = nsuper;
117 0 : xprune[kcol] = nextl;
118 0 : xlsub[kcol+1] = nextl;
119 :
120 0 : return 0;
121 : }
122 :
|
