33 grid->delete_top_level_A =
false;
40 if (
grid->level == 0) {
41 if (
grid->delete_top_level_A) {
55 int i, ii, j, *ia, *ja, m, n;
59 int *matched, nz, nz0;
61 int nsuper, *super =
NULL, *superp =
NULL;
64 assert(
A->is_pattern_symmetric);
71 *clusterp =
gv_calloc(m + 1,
sizeof(
int));
74 for (i = 0; i < m; i++) matched[i] = i;
86 for (i = 0; i < nsuper; i++){
87 if (superp[i+1] - superp[i] <= 1)
continue;
88 nz0 = (*clusterp)[*ncluster];
89 for (j = superp[i]; j < superp[i+1]; j++){
90 matched[super[j]] = MATCHED;
91 (*cluster)[nz++] = super[j];
93 (*clusterp)[++(*ncluster)] = nz;
97 if (nz > nz0) (*clusterp)[++(*ncluster)] = nz;
101 for (ii = 0; ii < m; ii++){
104 if (matched[i] == MATCHED)
continue;
105 for (j = ia[i]; j < ia[i+1]; j++){
106 if (i == ja[j])
continue;
107 if (matched[ja[j]] != MATCHED && matched[i] != MATCHED){
121 matched[jamax] = MATCHED;
122 matched[i] = MATCHED;
123 (*cluster)[nz++] = i;
124 (*cluster)[nz++] = jamax;
125 (*clusterp)[++(*ncluster)] = nz;
129 for (i = 0; i < m; i++){
130 if (matched[i] == i){
131 (*cluster)[nz++] = i;
132 (*clusterp)[++(*ncluster)] = nz;
150 int *cluster=
NULL, *clusterp=
NULL, ncluster;
152 assert(
A->m ==
A->n);
159 assert(ncluster <= n);
164 fprintf(stderr,
"nc = %d, nf = %d, minsz = %d, coarsen_factor = %f coarsening stops\n",nc, n,
minsize,
min_coarsen_factor);
172 for (i = 0; i < ncluster; i++){
173 for (j = clusterp[i]; j < clusterp[i+1]; j++){
174 assert(clusterp[i+1] > clusterp[i]);
175 irn[nzc] = cluster[j];
189 (*cA)->is_symmetric =
true;
190 (*cA)->is_pattern_symmetric =
true;
216 if (
Verbose) fprintf(stderr,
"nc=%d n = %d\n",nc,n);
243 for (i = 0; i < n; i++) fputs (
" ", stderr);
254 fprintf(stderr,
"level -- %d, n = %d, nz = %d nz/n = %f\n",
grid->level,
grid->n,
grid->A->nz,
grid->A->nz/(
double)
grid->n);
262 fprintf(stderr,
" maxlevel reached, coarsening stops\n");
268 if (!cA)
return grid;
293 if (
A != A0)
grid->delete_top_level_A =
true;
void print_padding(int n)
static const double min_coarsen_factor
Multilevel Multilevel_get_coarsest(Multilevel grid)
static void maximal_independent_edge_set_heavest_edge_pernode_supernodes_first(SparseMatrix A, int **cluster, int **clusterp, int *ncluster)
void Multilevel_delete(Multilevel grid)
static void Multilevel_coarsen(SparseMatrix A, SparseMatrix *cA, SparseMatrix *P, SparseMatrix *R)
static Multilevel Multilevel_init(SparseMatrix A)
static Multilevel Multilevel_establish(Multilevel grid, const Multilevel_control ctrl)
Multilevel Multilevel_new(SparseMatrix A0, const Multilevel_control ctrl)
static void Multilevel_coarsen_internal(SparseMatrix A, SparseMatrix *cA, SparseMatrix *P, SparseMatrix *R)
void SparseMatrix_decompose_to_supervariables(SparseMatrix A, int *ncluster, int **cluster, int **clusterp)
SparseMatrix SparseMatrix_transpose(SparseMatrix A)
bool SparseMatrix_is_symmetric(SparseMatrix A, bool test_pattern_symmetry_only)
SparseMatrix SparseMatrix_multiply(SparseMatrix A, SparseMatrix B)
SparseMatrix SparseMatrix_divide_row_by_degree(SparseMatrix A)
SparseMatrix SparseMatrix_from_coordinate_arrays(int nz, int m, int n, int *irn, int *jcn, void *val0, int type, size_t sz)
void SparseMatrix_delete(SparseMatrix A)
SparseMatrix SparseMatrix_get_real_adjacency_matrix_symmetrized(SparseMatrix A)
SparseMatrix SparseMatrix_multiply3(SparseMatrix A, SparseMatrix B, SparseMatrix C)
SparseMatrix SparseMatrix_remove_diagonal(SparseMatrix A)
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
static void * gv_alloc(size_t size)
int * gv_permutation(int bound)