22 size_t *r_maxlnz,
size_t *r_opc)
24 idx_t i,
j, k, nvtxs, maxlnz, maxsub;
26 idx_t *xlnz, *xnzsub, *nzsub;
37 maxsub = 8*(nvtxs+
xadj[nvtxs]);
42 for (
i=0;
i<nvtxs+1;
i++)
44 for (
i=0;
i<nvtxs;
i++) {
50 xlnz =
imalloc(nvtxs+2,
"ComputeFillIn: xlnz");
51 xnzsub =
imalloc(nvtxs+2,
"ComputeFillIn: xnzsub");
52 nzsub =
imalloc(maxsub+1,
"ComputeFillIn: nzsub");
57 printf(
"Realocating nzsub...\n");
61 nzsub =
imalloc(maxsub+1,
"ComputeFillIn: nzsub");
63 errexit(
"MAXSUB is too small!");
66 for (
i=0;
i<nvtxs;
i++)
68 for (opc=0,
i=0;
i<nvtxs;
i++)
69 opc += (xlnz[
i+1]-xlnz[
i])*(xlnz[
i+1]-xlnz[
i]) - (xlnz[
i+1]-xlnz[
i]);
77 for (
i=0;
i<nvtxs;
i++) {
81 for (
i=0;
i<nvtxs+1;
i++)
116 idx_t node, rchm, mrgk, lmax,
i,
j, k,
m, nabor, nzbeg, nzend;
117 idx_t kxsub, jstop, jstrt, mrkflg, inz, knz, flag;
118 idx_t *mrglnk, *marker, *rchlnk;
120 rchlnk =
ismalloc(neqns+1, 0,
"smbfct: rchlnk");
121 marker =
ismalloc(neqns+1, 0,
"smbfct: marker");
122 mrglnk =
ismalloc(neqns+1, 0,
"smbfct: mgrlnk");
143 for (k=1; k<=neqns; k++) {
151 assert(mrgk > 0 && mrgk <= neqns);
152 marker[k] = marker[mrgk];
161 assert(k <= neqns && k > 0);
171 assert(
m > 0 &&
m <= neqns);
173 }
while (rchm <= nabor);
176 assert(
m > 0 &&
m <= neqns);
178 assert(nabor > 0 && nabor <= neqns);
179 rchlnk[nabor] = rchm;
180 assert(k > 0 && k <= neqns);
181 if (marker[nabor] != marker[k])
188 assert(mrgk >= 0 && mrgk <= neqns);
189 if (mrkflg != 0 || mrgk == 0 || mrglnk[mrgk] != 0)
191 xnzsub[k] = xnzsub[mrgk] + 1;
192 knz = xlnz[mrgk + 1] - (xlnz[mrgk] + 1);
199 assert(
i > 0 &&
i <= neqns);
200 while ((
i = mrglnk[
i]) != 0) {
201 assert(
i > 0 &&
i <= neqns);
202 inz = xlnz[
i+1] - (xlnz[
i]+1);
203 jstrt = xnzsub[
i] + 1;
204 jstop = xnzsub[
i] + inz;
213 for (
j=jstrt;
j<=jstop;
j++) {
217 assert(
m > 0 &&
m <= neqns);
219 }
while (rchm < nabor);
223 assert(
m > 0 &&
m <= neqns);
225 assert(nabor > 0 && nabor <= neqns);
226 rchlnk[nabor] = rchm;
241 assert(k > 0 && k <= neqns);
243 for (jstrt = nzbeg; jstrt <= nzend; ++jstrt) {
244 if (nzsub[jstrt] <
i)
247 if (nzsub[jstrt] ==
i)
257 for (
j = jstrt;
j <= nzend; ++
j) {
261 assert(
i > 0 &&
i <= neqns);
274 if (nzend >= *maxsub) {
280 for (
j=nzbeg;
j<=nzend;
j++) {
281 assert(
i > 0 &&
i <= neqns);
284 assert(
i > 0 &&
i <= neqns);
288 assert(k > 0 && k <= neqns);
300 assert(
i > 0 &&
i <= neqns);
301 assert(k > 0 && k <= neqns);
302 mrglnk[k] = mrglnk[
i];
306 xlnz[k + 1] = xlnz[k] + knz;
310 *maxlnz = xlnz[neqns] - 1;
311 *maxsub = xnzsub[neqns];
312 xnzsub[neqns + 1] = xnzsub[neqns];