SCM

SCM Repository

[matrix] Annotation of /pkg/Matrix/src/CHOLMOD/Include/cholmod_partition.h
ViewVC logotype

Annotation of /pkg/Matrix/src/CHOLMOD/Include/cholmod_partition.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2915 - (view) (download) (as text)

1 : bates 912 /* ========================================================================== */
2 :     /* === Include/cholmod_partition.h ========================================== */
3 :     /* ========================================================================== */
4 :    
5 :     /* -----------------------------------------------------------------------------
6 : bates 1876 * CHOLMOD/Include/cholmod_partition.h.
7 : mmaechler 2915 * Copyright (C) 2005-2013, Univ. of Florida. Author: Timothy A. Davis
8 : bates 912 * CHOLMOD/Include/cholmod_partition.h is licensed under Version 2.1 of the GNU
9 :     * Lesser General Public License. See lesser.txt for a text of the license.
10 :     * CHOLMOD is also available under other licenses; contact authors for details.
11 :     * -------------------------------------------------------------------------- */
12 :    
13 :     /* CHOLMOD Partition module.
14 :     *
15 :     * Graph partitioning and graph-partition-based orderings. Includes an
16 :     * interface to CCOLAMD and CSYMAMD, constrained minimum degree ordering
17 :     * methods which order a matrix following constraints determined via nested
18 :     * dissection.
19 :     *
20 : mmaechler 2915 * These functions require METIS:
21 : bates 912 * cholmod_nested_dissection CHOLMOD nested dissection ordering
22 :     * cholmod_metis METIS nested dissection ordering (METIS_NodeND)
23 :     * cholmod_bisect graph partitioner (currently based on METIS)
24 :     * cholmod_metis_bisector direct interface to METIS_NodeComputeSeparator
25 :     *
26 : bates 1515 * Requires the Core and Cholesky modules, and three packages: METIS, CAMD,
27 :     * and CCOLAMD. Optionally used by the Cholesky module.
28 : bates 912 *
29 : dmbates 2798 * Note that METIS does not have a version that uses SuiteSparse_long integers.
30 :     * If you try to use cholmod_nested_dissection, cholmod_metis, cholmod_bisect,
31 :     * or cholmod_metis_bisector on a matrix that is too large, an error code will
32 :     * be returned. METIS does have an "idxtype", which could be redefined as
33 :     * SuiteSparse_long, if you wish to edit METIS or use compile-time flags to
34 :     * redefine idxtype.
35 : bates 912 */
36 :    
37 :     #ifndef CHOLMOD_PARTITION_H
38 :     #define CHOLMOD_PARTITION_H
39 :    
40 :     #include "cholmod_core.h"
41 : mmaechler 2915 #include "cholmod_camd.h"
42 : bates 912
43 :     /* -------------------------------------------------------------------------- */
44 :     /* cholmod_nested_dissection */
45 :     /* -------------------------------------------------------------------------- */
46 :    
47 :     /* Order A, AA', or A(:,f)*A(:,f)' using CHOLMOD's nested dissection method
48 :     * (METIS's node bisector applied recursively to compute the separator tree
49 :     * and constraint sets, followed by CCOLAMD using the constraints). Usually
50 :     * finds better orderings than METIS_NodeND, but takes longer.
51 :     */
52 :    
53 : dmbates 2798 SuiteSparse_long cholmod_nested_dissection /* returns # of components */
54 : bates 912 (
55 :     /* ---- input ---- */
56 :     cholmod_sparse *A, /* matrix to order */
57 :     int *fset, /* subset of 0:(A->ncol)-1 */
58 :     size_t fsize, /* size of fset */
59 :     /* ---- output --- */
60 :     int *Perm, /* size A->nrow, output permutation */
61 :     int *CParent, /* size A->nrow. On output, CParent [c] is the parent
62 :     * of component c, or EMPTY if c is a root, and where
63 :     * c is in the range 0 to # of components minus 1 */
64 :     int *Cmember, /* size A->nrow. Cmember [j] = c if node j of A is
65 :     * in component c */
66 :     /* --------------- */
67 :     cholmod_common *Common
68 :     ) ;
69 :    
70 : dmbates 2798 SuiteSparse_long cholmod_l_nested_dissection (cholmod_sparse *,
71 :     SuiteSparse_long *, size_t, SuiteSparse_long *, SuiteSparse_long *,
72 :     SuiteSparse_long *, cholmod_common *) ;
73 : bates 912
74 :     /* -------------------------------------------------------------------------- */
75 :     /* cholmod_metis */
76 :     /* -------------------------------------------------------------------------- */
77 :    
78 :     /* Order A, AA', or A(:,f)*A(:,f)' using METIS_NodeND. */
79 :    
80 :     int cholmod_metis
81 :     (
82 :     /* ---- input ---- */
83 :     cholmod_sparse *A, /* matrix to order */
84 :     int *fset, /* subset of 0:(A->ncol)-1 */
85 :     size_t fsize, /* size of fset */
86 :     int postorder, /* if TRUE, follow with etree or coletree postorder */
87 :     /* ---- output --- */
88 :     int *Perm, /* size A->nrow, output permutation */
89 :     /* --------------- */
90 :     cholmod_common *Common
91 :     ) ;
92 :    
93 : dmbates 2798 int cholmod_l_metis (cholmod_sparse *, SuiteSparse_long *, size_t, int,
94 :     SuiteSparse_long *, cholmod_common *) ;
95 : bates 912
96 :     /* -------------------------------------------------------------------------- */
97 :     /* cholmod_bisect */
98 :     /* -------------------------------------------------------------------------- */
99 :    
100 :     /* Finds a node bisector of A, A*A', A(:,f)*A(:,f)'. */
101 :    
102 : dmbates 2798 SuiteSparse_long cholmod_bisect /* returns # of nodes in separator */
103 : bates 912 (
104 :     /* ---- input ---- */
105 :     cholmod_sparse *A, /* matrix to bisect */
106 :     int *fset, /* subset of 0:(A->ncol)-1 */
107 :     size_t fsize, /* size of fset */
108 :     int compress, /* if TRUE, compress the graph first */
109 :     /* ---- output --- */
110 :     int *Partition, /* size A->nrow. Node i is in the left graph if
111 :     * Partition [i] = 0, the right graph if 1, and in the
112 :     * separator if 2. */
113 :     /* --------------- */
114 :     cholmod_common *Common
115 :     ) ;
116 :    
117 : dmbates 2798 SuiteSparse_long cholmod_l_bisect (cholmod_sparse *, SuiteSparse_long *,
118 :     size_t, int, SuiteSparse_long *, cholmod_common *) ;
119 : bates 912
120 :     /* -------------------------------------------------------------------------- */
121 :     /* cholmod_metis_bisector */
122 :     /* -------------------------------------------------------------------------- */
123 :    
124 :     /* Find a set of nodes that bisects the graph of A or AA' (direct interface
125 :     * to METIS_NodeComputeSeparator). */
126 :    
127 : dmbates 2798 SuiteSparse_long cholmod_metis_bisector /* returns separator size */
128 : bates 912 (
129 :     /* ---- input ---- */
130 :     cholmod_sparse *A, /* matrix to bisect */
131 :     int *Anw, /* size A->nrow, node weights */
132 :     int *Aew, /* size nz, edge weights */
133 :     /* ---- output --- */
134 :     int *Partition, /* size A->nrow. see cholmod_bisect above. */
135 :     /* --------------- */
136 :     cholmod_common *Common
137 :     ) ;
138 :    
139 : dmbates 2798 SuiteSparse_long cholmod_l_metis_bisector (cholmod_sparse *,
140 :     SuiteSparse_long *, SuiteSparse_long *, SuiteSparse_long *,
141 :     cholmod_common *) ;
142 : bates 912
143 : bates 1515 /* -------------------------------------------------------------------------- */
144 :     /* cholmod_collapse_septree */
145 :     /* -------------------------------------------------------------------------- */
146 :    
147 :     /* Collapse nodes in a separator tree. */
148 :    
149 : dmbates 2798 SuiteSparse_long cholmod_collapse_septree
150 : bates 1515 (
151 :     /* ---- input ---- */
152 :     size_t n, /* # of nodes in the graph */
153 :     size_t ncomponents, /* # of nodes in the separator tree (must be <= n) */
154 :     double nd_oksep, /* collapse if #sep >= nd_oksep * #nodes in subtree */
155 :     size_t nd_small, /* collapse if #nodes in subtree < nd_small */
156 :     /* ---- in/out --- */
157 :     int *CParent, /* size ncomponents; from cholmod_nested_dissection */
158 :     int *Cmember, /* size n; from cholmod_nested_dissection */
159 :     /* --------------- */
160 :     cholmod_common *Common
161 :     ) ;
162 :    
163 : dmbates 2798 SuiteSparse_long cholmod_l_collapse_septree (size_t, size_t, double, size_t,
164 :     SuiteSparse_long *, SuiteSparse_long *, cholmod_common *) ;
165 : bates 1515
166 : bates 912 #endif

root@r-forge.r-project.org
ViewVC Help
Powered by ViewVC 1.0.0  
Thanks to:
Vienna University of Economics and Business Powered By FusionForge