1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
/*! @file heap_relax_snode.c
* \brief Identify the initial relaxed supernodes
*
* <pre>
* -- SuperLU routine (version 3.0) --
* Univ. of California Berkeley, Xerox Palo Alto Research Center,
* and Lawrence Berkeley National Lab.
* October 15, 2003
*
* Copyright (c) 1994 by Xerox Corporation. All rights reserved.
*
* THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY
* EXPRESSED OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
*
* Permission is hereby granted to use or copy this program for any
* purpose, provided the above notices are retained on all copies.
* Permission to modify the code and to distribute modified code is
* granted, provided the above notices are retained, and a notice that
* the code was modified is included with the above copyright notice.
* </pre>
*/
#include "slu_ddefs.h"
/*! \brief
*
* <pre>
* Purpose
* =======
* relax_snode() - Identify the initial relaxed supernodes, assuming that
* the matrix has been reordered according to the postorder of the etree.
* </pre>
*/
void
heap_relax_snode (
const int n,
int *et, /* column elimination tree */
const int relax_columns, /* max no of columns allowed in a
relaxed snode */
int *descendants, /* no of descendants of each node
in the etree */
int *relax_end /* last column in a supernode */
)
{
register int i, j, k, l, parent;
register int snode_start; /* beginning of a snode */
int *et_save, *post, *inv_post, *iwork;
int nsuper_et = 0, nsuper_et_post = 0;
/* The etree may not be postordered, but is heap ordered. */
iwork = (int*) intMalloc(3*n+2);
if ( !iwork ) ABORT("SUPERLU_MALLOC fails for iwork[]");
inv_post = iwork + n+1;
et_save = inv_post + n+1;
/* Post order etree */
post = (int *) TreePostorder(n, et);
for (i = 0; i < n+1; ++i) inv_post[post[i]] = i;
/* Renumber etree in postorder */
for (i = 0; i < n; ++i) {
iwork[post[i]] = post[et[i]];
et_save[i] = et[i]; /* Save the original etree */
}
for (i = 0; i < n; ++i) et[i] = iwork[i];
/* Compute the number of descendants of each node in the etree */
ifill (relax_end, n, EMPTY);
for (j = 0; j < n; j++) descendants[j] = 0;
for (j = 0; j < n; j++) {
parent = et[j];
if ( parent != n ) /* not the dummy root */
descendants[parent] += descendants[j] + 1;
}
/* Identify the relaxed supernodes by postorder traversal of the etree. */
for (j = 0; j < n; ) {
parent = et[j];
snode_start = j;
while ( parent != n && descendants[parent] < relax_columns ) {
j = parent;
parent = et[j];
}
/* Found a supernode in postordered etree; j is the last column. */
++nsuper_et_post;
k = n;
for (i = snode_start; i <= j; ++i)
k = SUPERLU_MIN(k, inv_post[i]);
l = inv_post[j];
if ( (l - k) == (j - snode_start) ) {
/* It's also a supernode in the original etree */
relax_end[k] = l; /* Last column is recorded */
++nsuper_et;
} else {
for (i = snode_start; i <= j; ++i) {
l = inv_post[i];
if ( descendants[i] == 0 ) {
relax_end[l] = l;
++nsuper_et;
}
}
}
j++;
/* Search for a new leaf */
while ( descendants[j] != 0 && j < n ) j++;
}
#if ( PRNTlevel>=1 )
printf(".. heap_snode_relax:\n"
"\tNo of relaxed snodes in postordered etree:\t%d\n"
"\tNo of relaxed snodes in original etree:\t%d\n",
nsuper_et_post, nsuper_et);
#endif
/* Recover the original etree */
for (i = 0; i < n; ++i) et[i] = et_save[i];
SUPERLU_FREE(post);
SUPERLU_FREE(iwork);
}
|
