Amesos Package Browser (Single Doxygen Collection) Development
amesos_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 AMESOS_CHOLMOD_PARTITION_H
00040 #define AMESOS_CHOLMOD_PARTITION_H
00041 
00042 #include "amesos_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 amesos_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 amesos_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 amesos_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 amesos_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 amesos_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 amesos_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 amesos_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 amesos_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 amesos_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 amesos_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 amesos_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 amesos_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 amesos_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 amesos_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 amesos_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 amesos_cholmod_l_collapse_septree (size_t, size_t, double, size_t, UF_long *,
00231     UF_long *, cholmod_common *) ;
00232 
00233 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines