cholmod_partition.h
Go to the documentation of this file.00001 /* ========================================================================== */ 00002 /* === Include/cholmod_partition.h ========================================== */ 00003 /* ========================================================================== */ 00004 00005 /* ----------------------------------------------------------------------------- 00006 * CHOLMOD/Include/cholmod_partition.h. 00007 * Copyright (C) 2005-2006, Univ. of Florida. Author: Timothy A. Davis 00008 * CHOLMOD/Include/cholmod_partition.h is licensed under Version 2.1 of the GNU 00009 * Lesser General Public License. See lesser.txt for a text of the license. 00010 * CHOLMOD is also available under other licenses; contact authors for details. 00011 * http://www.cise.ufl.edu/research/sparse 00012 * -------------------------------------------------------------------------- */ 00013 00014 /* CHOLMOD Partition module. 00015 * 00016 * Graph partitioning and graph-partition-based orderings. Includes an 00017 * interface to CCOLAMD and CSYMAMD, constrained minimum degree ordering 00018 * methods which order a matrix following constraints determined via nested 00019 * dissection. 00020 * 00021 * cholmod_nested_dissection CHOLMOD nested dissection ordering 00022 * cholmod_metis METIS nested dissection ordering (METIS_NodeND) 00023 * cholmod_ccolamd interface to CCOLAMD ordering 00024 * cholmod_csymamd interface to CSYMAMD ordering 00025 * cholmod_camd interface to CAMD ordering 00026 * cholmod_bisect graph partitioner (currently based on METIS) 00027 * cholmod_metis_bisector direct interface to METIS_NodeComputeSeparator 00028 * 00029 * Requires the Core and Cholesky modules, and three packages: METIS, CAMD, 00030 * and CCOLAMD. Optionally used by the Cholesky module. 00031 * 00032 * Note that METIS does not have a version that uses UF_long integers. If you 00033 * try to use cholmod_nested_dissection, cholmod_metis, cholmod_bisect, or 00034 * cholmod_metis_bisector on a matrix that is too large, an error code will be 00035 * returned. METIS does have an "idxtype", which could be redefined as UF_long, 00036 * if you wish to edit METIS or use compile-time flags to redefine idxtype. 00037 */ 00038 00039 #ifndef CHOLMOD_PARTITION_H 00040 #define CHOLMOD_PARTITION_H 00041 00042 #include "cholmod_core.h" 00043 00044 /* -------------------------------------------------------------------------- */ 00045 /* cholmod_nested_dissection */ 00046 /* -------------------------------------------------------------------------- */ 00047 00048 /* Order A, AA', or A(:,f)*A(:,f)' using CHOLMOD's nested dissection method 00049 * (METIS's node bisector applied recursively to compute the separator tree 00050 * and constraint sets, followed by CCOLAMD using the constraints). Usually 00051 * finds better orderings than METIS_NodeND, but takes longer. 00052 */ 00053 00054 UF_long cholmod_nested_dissection /* returns # of components */ 00055 ( 00056 /* ---- input ---- */ 00057 cholmod_sparse *A, /* matrix to order */ 00058 int *fset, /* subset of 0:(A->ncol)-1 */ 00059 size_t fsize, /* size of fset */ 00060 /* ---- output --- */ 00061 int *Perm, /* size A->nrow, output permutation */ 00062 int *CParent, /* size A->nrow. On output, CParent [c] is the parent 00063 * of component c, or EMPTY if c is a root, and where 00064 * c is in the range 0 to # of components minus 1 */ 00065 int *Cmember, /* size A->nrow. Cmember [j] = c if node j of A is 00066 * in component c */ 00067 /* --------------- */ 00068 cholmod_common *Common 00069 ) ; 00070 00071 UF_long cholmod_l_nested_dissection (cholmod_sparse *, UF_long *, size_t, 00072 UF_long *, UF_long *, UF_long *, cholmod_common *) ; 00073 00074 /* -------------------------------------------------------------------------- */ 00075 /* cholmod_metis */ 00076 /* -------------------------------------------------------------------------- */ 00077 00078 /* Order A, AA', or A(:,f)*A(:,f)' using METIS_NodeND. */ 00079 00080 int cholmod_metis 00081 ( 00082 /* ---- input ---- */ 00083 cholmod_sparse *A, /* matrix to order */ 00084 int *fset, /* subset of 0:(A->ncol)-1 */ 00085 size_t fsize, /* size of fset */ 00086 int postorder, /* if TRUE, follow with etree or coletree postorder */ 00087 /* ---- output --- */ 00088 int *Perm, /* size A->nrow, output permutation */ 00089 /* --------------- */ 00090 cholmod_common *Common 00091 ) ; 00092 00093 int cholmod_l_metis (cholmod_sparse *, UF_long *, size_t, int, UF_long *, 00094 cholmod_common *) ; 00095 00096 /* -------------------------------------------------------------------------- */ 00097 /* cholmod_ccolamd */ 00098 /* -------------------------------------------------------------------------- */ 00099 00100 /* Order AA' or A(:,f)*A(:,f)' using CCOLAMD. */ 00101 00102 int cholmod_ccolamd 00103 ( 00104 /* ---- input ---- */ 00105 cholmod_sparse *A, /* matrix to order */ 00106 int *fset, /* subset of 0:(A->ncol)-1 */ 00107 size_t fsize, /* size of fset */ 00108 int *Cmember, /* size A->nrow. Cmember [i] = c if row i is in the 00109 * constraint set c. c must be >= 0. The # of 00110 * constraint sets is max (Cmember) + 1. If Cmember is 00111 * NULL, then it is interpretted as Cmember [i] = 0 for 00112 * all i */ 00113 /* ---- output --- */ 00114 int *Perm, /* size A->nrow, output permutation */ 00115 /* --------------- */ 00116 cholmod_common *Common 00117 ) ; 00118 00119 int cholmod_l_ccolamd (cholmod_sparse *, UF_long *, size_t, UF_long *, 00120 UF_long *, cholmod_common *) ; 00121 00122 /* -------------------------------------------------------------------------- */ 00123 /* cholmod_csymamd */ 00124 /* -------------------------------------------------------------------------- */ 00125 00126 /* Order A using CSYMAMD. */ 00127 00128 int cholmod_csymamd 00129 ( 00130 /* ---- input ---- */ 00131 cholmod_sparse *A, /* matrix to order */ 00132 /* ---- output --- */ 00133 int *Cmember, /* size nrow. see cholmod_ccolamd above */ 00134 int *Perm, /* size A->nrow, output permutation */ 00135 /* --------------- */ 00136 cholmod_common *Common 00137 ) ; 00138 00139 int cholmod_l_csymamd (cholmod_sparse *, UF_long *, UF_long *, 00140 cholmod_common *) ; 00141 00142 /* -------------------------------------------------------------------------- */ 00143 /* cholmod_camd */ 00144 /* -------------------------------------------------------------------------- */ 00145 00146 /* Order A using CAMD. */ 00147 00148 int cholmod_camd 00149 ( 00150 /* ---- input ---- */ 00151 cholmod_sparse *A, /* matrix to order */ 00152 int *fset, /* subset of 0:(A->ncol)-1 */ 00153 size_t fsize, /* size of fset */ 00154 /* ---- output --- */ 00155 int *Cmember, /* size nrow. see cholmod_ccolamd above */ 00156 int *Perm, /* size A->nrow, output permutation */ 00157 /* --------------- */ 00158 cholmod_common *Common 00159 ) ; 00160 00161 int cholmod_l_camd (cholmod_sparse *, UF_long *, size_t, UF_long *, UF_long *, 00162 cholmod_common *) ; 00163 00164 /* -------------------------------------------------------------------------- */ 00165 /* cholmod_bisect */ 00166 /* -------------------------------------------------------------------------- */ 00167 00168 /* Finds a node bisector of A, A*A', A(:,f)*A(:,f)'. */ 00169 00170 UF_long cholmod_bisect /* returns # of nodes in separator */ 00171 ( 00172 /* ---- input ---- */ 00173 cholmod_sparse *A, /* matrix to bisect */ 00174 int *fset, /* subset of 0:(A->ncol)-1 */ 00175 size_t fsize, /* size of fset */ 00176 int compress, /* if TRUE, compress the graph first */ 00177 /* ---- output --- */ 00178 int *Partition, /* size A->nrow. Node i is in the left graph if 00179 * Partition [i] = 0, the right graph if 1, and in the 00180 * separator if 2. */ 00181 /* --------------- */ 00182 cholmod_common *Common 00183 ) ; 00184 00185 UF_long cholmod_l_bisect (cholmod_sparse *, UF_long *, size_t, int, UF_long *, 00186 cholmod_common *) ; 00187 00188 /* -------------------------------------------------------------------------- */ 00189 /* cholmod_metis_bisector */ 00190 /* -------------------------------------------------------------------------- */ 00191 00192 /* Find a set of nodes that bisects the graph of A or AA' (direct interface 00193 * to METIS_NodeComputeSeparator). */ 00194 00195 UF_long cholmod_metis_bisector /* returns separator size */ 00196 ( 00197 /* ---- input ---- */ 00198 cholmod_sparse *A, /* matrix to bisect */ 00199 int *Anw, /* size A->nrow, node weights */ 00200 int *Aew, /* size nz, edge weights */ 00201 /* ---- output --- */ 00202 int *Partition, /* size A->nrow. see cholmod_bisect above. */ 00203 /* --------------- */ 00204 cholmod_common *Common 00205 ) ; 00206 00207 UF_long cholmod_l_metis_bisector (cholmod_sparse *, UF_long *, UF_long *, 00208 UF_long *, cholmod_common *) ; 00209 00210 /* -------------------------------------------------------------------------- */ 00211 /* cholmod_collapse_septree */ 00212 /* -------------------------------------------------------------------------- */ 00213 00214 /* Collapse nodes in a separator tree. */ 00215 00216 UF_long cholmod_collapse_septree 00217 ( 00218 /* ---- input ---- */ 00219 size_t n, /* # of nodes in the graph */ 00220 size_t ncomponents, /* # of nodes in the separator tree (must be <= n) */ 00221 double nd_oksep, /* collapse if #sep >= nd_oksep * #nodes in subtree */ 00222 size_t nd_small, /* collapse if #nodes in subtree < nd_small */ 00223 /* ---- in/out --- */ 00224 int *CParent, /* size ncomponents; from cholmod_nested_dissection */ 00225 int *Cmember, /* size n; from cholmod_nested_dissection */ 00226 /* --------------- */ 00227 cholmod_common *Common 00228 ) ; 00229 00230 UF_long cholmod_l_collapse_septree (size_t, size_t, double, size_t, UF_long *, 00231 UF_long *, cholmod_common *) ; 00232 00233 #endif