/* * Copyright 1997, Regents of the University of Minnesota * * smbfactor.c * * This file performs the symbolic factorization of a matrix * * Started 8/1/97 * George * * $Id: smbfactor.c,v 1.1 1998/11/27 17:59:40 karypis Exp $ * */ #include /************************************************************************* * This function sets up data structures for fill-in computations **************************************************************************/ void ComputeFillIn(GraphType *graph, idxtype *iperm) { int i, j, k, nvtxs, maxlnz, maxsub; idxtype *xadj, *adjncy; idxtype *perm, *xlnz, *xnzsub, *nzsub; double opc; /* printf("\nSymbolic factorization... --------------------------------------------\n"); */ nvtxs = graph->nvtxs; xadj = graph->xadj; adjncy = graph->adjncy; maxsub = 4*xadj[nvtxs]; /* Relabel the vertices so that it starts from 1 */ k = xadj[nvtxs]; for (i=0; invtxs; xadj = graph->xadj; adjncy = graph->adjncy; maxsub = 4*xadj[nvtxs]; /* Relabel the vertices so that it starts from 1 */ k = xadj[nvtxs]; for (i=0; i= xadj[node+1]) { xlnz[k+1] = xlnz[k]; continue; } /* USE RCHLNK TO LINK THROUGH THE STRUCTURE OF A(*,K) BELOW DIAGONAL */ rchlnk[k] = neqns+1; for (j=xadj[node]; j lmax) { lmax = inz; xnzsub[k] = jstrt; } /* MERGE STRUCTURE OF L(*,I) IN NZSUB INTO RCHLNK. */ rchm = k; for (j = jstrt; j <= jstop; ++j) { nabor = nzsub[j]; do { m = rchm; rchm = rchlnk[m]; } while (rchm < nabor); if (rchm != nabor) { knz++; rchlnk[m] = nabor; rchlnk[nabor] = rchm; rchm = nabor; } } } /* CHECK IF SUBSCRIPTS DUPLICATE THOSE OF ANOTHER COLUMN */ if (knz == lmax) goto L1400; /* OR IF TAIL OF K-1ST COLUMN MATCHES HEAD OF KTH */ if (nzbeg > nzend) goto L1200; i = rchlnk[k]; for (jstrt = nzbeg; jstrt <= nzend; ++jstrt) { if (nzsub[jstrt] < i) continue; if (nzsub[jstrt] == i) goto L1000; else goto L1200; } goto L1200; L1000: xnzsub[k] = jstrt; for (j = jstrt; j <= nzend; ++j) { if (nzsub[j] != i) goto L1200; i = rchlnk[i]; if (i > neqns) goto L1400; } nzend = jstrt - 1; /* COPY THE STRUCTURE OF L(*,K) FROM RCHLNK TO THE DATA STRUCTURE (XNZSUB, NZSUB) */ L1200: nzbeg = nzend + 1; nzend += knz; if (nzend > *maxsub) { flag = 1; /* Out of memory */ break; } i = k; for (j=nzbeg; j<=nzend; ++j) { i = rchlnk[i]; nzsub[j] = i; marker[i] = k; } xnzsub[k] = nzbeg; marker[k] = k; /* * UPDATE THE VECTOR MRGLNK. NOTE COLUMN L(*,K) JUST FOUND * IS REQUIRED TO DETERMINE COLUMN L(*,J), WHERE * L(J,K) IS THE FIRST NONZERO IN L(*,K) BELOW DIAGONAL. */ L1400: if (knz > 1) { kxsub = xnzsub[k]; i = nzsub[kxsub]; mrglnk[k] = mrglnk[i]; mrglnk[i] = k; } xlnz[k + 1] = xlnz[k] + knz; } if (flag == 0) { *maxlnz = xlnz[neqns] - 1; *maxsub = xnzsub[neqns]; xnzsub[neqns + 1] = xnzsub[neqns]; } marker++; mrglnk++; rchlnk++; nzsub++; xnzsub++; xlnz++; invp++; perm++; adjncy++; xadj++; GKfree(&rchlnk, &mrglnk, &marker, LTERM); return flag; }