📄 symfct.c
字号:
/* BROTHR - THE BROTHER VECTOR. */
/* INVPOS - THE INVERSE PERM VECTOR FOR THE */
/* POSTORDERING. */
/* PROGRAM SUBROUTINES: */
/* BTREE2, EPOST2, INVINV. */
/* *********************************************************************** */
/* Subroutine */ int chordr_(neqns, xadj, adjncy, perm, invp, colcnt, parent,
fson, brothr, invpos)
integer *neqns, *xadj, *adjncy, *perm, *invp, *colcnt, *parent, *fson, *
brothr, *invpos;
{
extern /* Subroutine */ int btree2_(), epost2_(), invinv_();
/* ***********************************************************************
*/
/* ***********************************************************************
*/
/* ---------------------------------------------------------- */
/* COMPUTE A BINARY REPRESENTATION OF THE ELIMINATION TREE, */
/* SO THAT EACH "LAST CHILD" MAXIMIZES AMONG ITS SIBLINGS THE */
/* NUMBER OF NONZEROS IN THE CORRESPONDING COLUMNS OF L. */
/* ---------------------------------------------------------- */
/* Parameter adjustments */
--invpos;
--brothr;
--fson;
--parent;
--colcnt;
--invp;
--perm;
--adjncy;
--xadj;
/* Function Body */
btree2_(neqns, &parent[1], &colcnt[1], &fson[1], &brothr[1], &invpos[1]);
/* ---------------------------------------------------- */
/* POSTORDER THE ELIMINATION TREE (USING THE NEW BINARY */
/* REPRESENTATION. */
/* ---------------------------------------------------- */
epost2_(neqns, &fson[1], &brothr[1], &invpos[1], &parent[1], &colcnt[1], &
perm[1]);
/* -------------------------------------------------------- */
/* COMPOSE THE ORIGINAL ORDERING WITH THE NEW POSTORDERING. */
/* -------------------------------------------------------- */
invinv_(neqns, &invp[1], &invpos[1], &perm[1]);
return 0;
} /* chordr_ */
/* *********************************************************************** */
/* *********************************************************************** */
/* Version: 0.3 */
/* Last modified: January 12, 1995 */
/* Authors: Esmond G. Ng and Barry W. Peyton */
/* Mathematical Sciences Section, Oak Ridge National Laboratory */
/* *********************************************************************** */
/* *********************************************************************** */
/* ****** BTREE2 ..... BINARY TREE REPRESENTATION OF ETREE ******* */
/* *********************************************************************** */
/* *********************************************************************** */
/* PURPOSE: */
/* TO DETERMINE A BINARY TREE REPRESENTATION OF THE ELIMINATION */
/* TREE, FOR WHICH EVERY "LAST CHILD" HAS THE MAXIMUM POSSIBLE */
/* COLUMN NONZERO COUNT IN THE FACTOR. THE RETURNED REPRESENTATION */
/* WILL BE GIVEN BY THE FIRST-SON AND BROTHER VECTORS. THE ROOT OF */
/* THE BINARY TREE IS ALWAYS NEQNS. */
/* INPUT PARAMETERS: */
/* NEQNS - NUMBER OF EQUATIONS. */
/* PARENT - THE PARENT VECTOR OF THE ELIMINATION TREE. */
/* IT IS ASSUMED THAT PARENT(I) > I EXCEPT OF */
/* THE ROOTS. */
/* COLCNT - COLUMN NONZERO COUNTS OF THE FACTOR. */
/* OUTPUT PARAMETERS: */
/* FSON - THE FIRST SON VECTOR. */
/* BROTHR - THE BROTHER VECTOR. */
/* WORKING PARAMETERS: */
/* LSON - LAST SON VECTOR. */
/* *********************************************************************** */
/* Subroutine */ int btree2_(neqns, parent, colcnt, fson, brothr, lson)
integer *neqns, *parent, *colcnt, *fson, *brothr, *lson;
{
/* System generated locals */
integer i__1;
/* Local variables */
static integer node, ndpar, lroot, ndlson;
/* ***********************************************************************
*/
/* ***********************************************************************
*/
/* ***********************************************************************
*/
/* Parameter adjustments */
--lson;
--brothr;
--fson;
--colcnt;
--parent;
/* Function Body */
if (*neqns <= 0) {
return 0;
}
i__1 = *neqns;
for (node = 1; node <= i__1; ++node) {
fson[node] = 0;
brothr[node] = 0;
lson[node] = 0;
/* L100: */
}
lroot = *neqns;
/* ------------------------------------------------------------ */
/* FOR EACH NODE := NEQNS-1 STEP -1 DOWNTO 1, DO THE FOLLOWING. */
/* ------------------------------------------------------------ */
if (*neqns <= 1) {
return 0;
}
for (node = *neqns - 1; node >= 1; --node) {
ndpar = parent[node];
if (ndpar <= 0 || ndpar == node) {
/* -------------------------------------------------
*/
/* NODE HAS NO PARENT. GIVEN STRUCTURE IS A FOREST.
*/
/* SET NODE TO BE ONE OF THE ROOTS OF THE TREES. */
/* -------------------------------------------------
*/
brothr[lroot] = node;
lroot = node;
} else {
/* ------------------------------------------- */
/* OTHERWISE, BECOMES FIRST SON OF ITS PARENT. */
/* ------------------------------------------- */
ndlson = lson[ndpar];
if (ndlson != 0) {
if (colcnt[node] >= colcnt[ndlson]) {
brothr[node] = fson[ndpar];
fson[ndpar] = node;
} else {
brothr[ndlson] = node;
lson[ndpar] = node;
}
} else {
fson[ndpar] = node;
lson[ndpar] = node;
}
}
/* L300: */
}
brothr[lroot] = 0;
return 0;
} /* btree2_ */
/* *********************************************************************** */
/* *********************************************************************** */
/* Version: 0.3 */
/* Last modified: December 27, 1994 */
/* Authors: Esmond G. Ng and Barry W. Peyton */
/* Mathematical Sciences Section, Oak Ridge National Laboratory */
/* *********************************************************************** */
/* *********************************************************************** */
/* *************** EPOST2 ..... ETREE POSTORDERING #2 *************** */
/* *********************************************************************** */
/* *********************************************************************** */
/* PURPOSE: */
/* BASED ON THE BINARY REPRESENTATION (FIRST-SON,BROTHER) OF THE */
/* ELIMINATION TREE, A POSTORDERING IS DETERMINED. THE */
/* CORRESPONDING PARENT AND COLCNT VECTORS ARE ALSO MODIFIED TO */
/* REFLECT THE REORDERING. */
/* INPUT PARAMETERS: */
/* ROOT - ROOT OF THE ELIMINATION TREE (USUALLY IT */
/* IS NEQNS). */
/* FSON - THE FIRST SON VECTOR. */
/* BROTHR - THE BROTHR VECTOR. */
/* UPDATED PARAMETERS: */
/* PARENT - THE PARENT VECTOR. */
/* COLCNT - COLUMN NONZERO COUNTS OF THE FACTOR. */
/* OUTPUT PARAMETERS: */
/* INVPOS - INVERSE PERMUTATION FOR THE POSTORDERING. */
/* WORKING PARAMETERS: */
/* STACK - THE STACK FOR POSTORDER TRAVERSAL OF THE */
/* TREE. */
/* *********************************************************************** */
/* Subroutine */ int epost2_(root, fson, brothr, invpos, parent, colcnt,
stack)
integer *root, *fson, *brothr, *invpos, *parent, *colcnt, *stack;
{
/* System generated locals */
integer i__1;
/* Local variables */
static integer node, itop, ndpar, nunode, num;
/* ***********************************************************************
*/
/* ***********************************************************************
*/
/* ***********************************************************************
*/
/* Parameter adjustments */
--stack;
--colcnt;
--parent;
--invpos;
--brothr;
--fson;
/* Function Body */
num = 0;
itop = 0;
node = *root;
/* ------------------------------------------------------------- */
/* TRAVERSE ALONG THE FIRST SONS POINTER AND PUSH THE TREE NODES */
/* ALONG THE TRAVERSAL INTO THE STACK. */
/* ------------------------------------------------------------- */
L100:
++itop;
stack[itop] = node;
node = fson[node];
if (node > 0) {
goto L100;
}
/* ---------------------------------------------------------- */
/* IF POSSIBLE, POP A TREE NODE FROM THE STACK AND NUMBER IT. */
/* ---------------------------------------------------------- */
L200:
if (itop <= 0) {
goto L300;
}
node = stack[itop];
--itop;
++num;
invpos[node] = num;
/* ---------------------------------------------------- */
/* THEN, TRAVERSE TO ITS YOUNGER BROTHER IF IT HAS ONE. */
/* ---------------------------------------------------- */
node = brothr[node];
if (node <= 0) {
goto L200;
}
goto L100;
L300:
/* ------------------------------------------------------------ */
/* DETERMINE THE NEW PARENT VECTOR OF THE POSTORDERING. BROTHR */
/* IS USED TEMPORARILY FOR THE NEW PARENT VECTOR. */
/* ------------------------------------------------------------ */
i__1 = num;
for (node = 1; node <= i__1; ++node) {
nunode = invpos[node];
ndpar = parent[node];
if (ndpar > 0) {
ndpar = invpos[ndpar];
}
brothr[nunode] = ndpar;
/* L400: */
}
i__1 = num;
for (nunode = 1; nunode <= i__1; ++nunode) {
parent[nunode] = brothr[nunode];
/* L500: */
}
/* ---------------------------------------------- */
/* PERMUTE COLCNT(*) TO REFLECT THE NEW ORDERING. */
/* ---------------------------------------------- */
i__1 = num;
for (node = 1; node <= i__1; ++node) {
nunode = invpos[node];
stack[nunode] = colcnt[node];
/* L600: */
}
i__1 = num;
for (node = 1; node <= i__1; ++node) {
colcnt[node] = stack[node];
/* L700: */
}
return 0;
} /* epost2_ */
/* *********************************************************************** */
/* *********************************************************************** */
/* Version: 0.3 */
/* Last modified: January 12, 1995 */
/* Authors: Esmond G. Ng and Barry W. Peyton */
/* Mathematical Sciences Section, Oak Ridge National Laboratory */
/* *********************************************************************** */
/* *********************************************************************** */
/* ************** FCNTHN ..... FIND NONZERO COUNTS *************** */
/* *********************************************************************** */
/* *********************************************************************** */
/* PURPOSE: */
/* THIS SUBROUTINE DETERMINES THE ROW COUNTS AND COLUMN COUNTS IN */
/* THE CHOLESKY FACTOR. IT USES A DISJOINT SET UNION ALGORITHM. */
/* TECHNIQUES: */
/* 1) SUPERNODE DETECTION. */
/* 2) PATH HALVING. */
/* 3) NO UNION BY RANK. */
/* NOTES: */
/* 1) ASSUMES A POSTORDERING OF THE ELIMINATION TREE. */
/* INPUT PARAMETERS: */
/* (I) NEQNS - NUMBER OF EQUATIONS. */
/* (I) ADJLEN - LENGTH OF ADJACENCY STRUCTURE. */
/* (I) XADJ(*) - ARRAY OF LENGTH NEQNS+1, CONTAINING POINTERS */
/* TO THE ADJACENCY STRUCTURE. */
/* (I) ADJNCY(*) - ARRAY OF LENGTH XADJ(NEQNS+1)-1, CONTAINING */
/* THE ADJACENCY STRUCTURE. */
/* (I) PERM(*) - ARRAY OF LENGTH NEQNS, CONTAINING THE */
/* POSTORDERING. */
/* (I) INVP(*) - ARRAY OF LENGTH NEQNS, CONTAINING THE */
/* INVERSE OF THE POSTORDERING. */
/* (I) ETPAR(*) - ARRAY OF LENGTH NEQNS, CONTAINING THE */
/* ELIMINATION TREE OF THE POSTORDERED MATRIX. */
/* OUTPUT PARAMETERS: */
/* (I) ROWCNT(*) - ARRAY OF LENGTH NEQNS, CONTAINING THE NUMBER */
/* OF NONZEROS IN EACH ROW OF THE FACTOR, */
/* INCLUDING THE DIAGONAL ENTRY. */
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -