58 #define ASSERT(expression) (assert (expression)) 60 #define ASSERT(expression) 79 static void dumpgraph (idxtype *Mp, idxtype *Mi,
UF_long n,
85 printf (
"Dumping METIS graph n %ld nz %ld\n",
n, nz) ;
86 f = fopen (
"metisgraph",
"w") ;
89 ERROR (-99,
"cannot open metisgraph") ;
92 fprintf (
f,
"%ld %ld\n",
n, nz/2) ;
93 for (j = 0 ; j <
n ; j++)
95 for (p = Mp [j] ; p < Mp [j+1] ; p++)
98 fprintf (
f,
" %ld", i+1) ;
139 #define GUESS(nz,n) (10 * (nz) + 50 * (n) + 4096) 152 if (
Common->metis_memory <= 0)
162 s =
GUESS ((
double) nz, (
double)
n) ;
163 s *=
Common->metis_memory ;
165 if (s *
sizeof (idxtype) >= ((
double)
Size_max))
172 metis_guard =
GUESS ((
size_t) nz, (
size_t)
n) ;
173 metis_guard *=
Common->metis_memory ;
176 p =
CHOLMOD(malloc) (metis_guard,
sizeof (idxtype),
Common) ;
214 idxtype *Mp, *Mi, *Mnw, *Mew, *Mpart ;
215 Int n, nleft, nright, j, p, csep, total_weight, lightest, nz ;
216 int Opt [8], nn, csp ;
230 if (
A->stype ||
A->nrow !=
A->ncol)
234 " and with both upper/lower parts present") ;
248 n1 = ((size_t)
n) + 1 ;
263 if (
sizeof (
Int) >
sizeof (idxtype) &&
MAX (
n,nz) > INT_MAX /
sizeof (int))
283 DEBUG (
for (j = 0 ; j < n ; j++) ASSERT (Anw [j] > 0)) ;
289 DEBUG (
for (j = 0 ; j < nz ; j++) ASSERT (Aew [j] > 0)) ;
290 if (
sizeof (
Int) ==
sizeof (idxtype))
293 Mi = (idxtype *) Ai ;
294 Mew = (idxtype *) Aew ;
295 Mp = (idxtype *) Ap ;
296 Mnw = (idxtype *) Anw ;
297 Mpart = (idxtype *) Partition ;
316 for (p = 0 ; p < nz ; p++)
320 for (p = 0 ; p < nz ; p++)
324 for (j = 0 ; j <=
n ; j++)
328 for (j = 0 ; j <
n ; j++)
341 if (
sizeof (
Int) !=
sizeof (idxtype))
357 PRINT1 ((
"Metis graph, n = "ID"\n",
n)) ;
358 for (j = 0 ; j <
n ; j++)
361 PRINT2 ((
"M(:,"ID") node weight "ID"\n", j, (
Int) Mnw [j])) ;
363 for (ppp = Mp [j] ; ppp < Mp [j+1] ; ppp++)
373 METIS_NodeComputeSeparator (&nn, Mp, Mi, Mnw, Mew, Opt, &csp, Mpart) ;
377 PRINT1 ((
"METIS csep "ID"\n", csep)) ;
383 if (
sizeof (
Int) !=
sizeof (idxtype))
385 for (j = 0 ; j <
n ; j++)
387 Partition [j] = Mpart [j] ;
414 for (j = 0 ; j <
n ; j++)
416 if (Anw [j] <= Anw [lightest])
421 PRINT1 ((
"Force "ID" as sep\n", lightest)) ;
422 Partition [lightest] = 2 ;
423 csep = Anw [lightest] ;
430 for (j = 0 ; j <
n ; j++)
432 PRINT1 ((
"Partition ["ID"] = "ID"\n", j, Partition [j])) ;
433 if (Partition [j] == 0)
437 else if (Partition [j] == 1)
444 ASSERT (Partition [j] == 2) ;
451 total_weight = nleft + nright + csep ;
453 if (csep < total_weight)
458 nleft, nright, csep, total_weight)) ;
459 ASSERT (nleft + nright + csep == total_weight) ;
460 ASSERT (nleft > 0 || nright > 0) ;
461 if ((nleft == 0 && nright > 0) || (nleft > 0 && nright == 0))
464 PRINT1 ((
"Force all in sep\n")) ;
465 csep = total_weight ;
466 for (j = 0 ; j <
n ; j++)
510 Int *Iperm, *Iwork, *Bp, *Bi ;
511 idxtype *Mp, *Mi, *Mperm, *Miperm ;
513 Int i, j,
n, nz, p, identity, uncol ;
514 int Opt [8], nn, zero = 0 ;
537 n1 = ((size_t)
n) + 1 ;
544 uncol = (
A->stype == 0) ?
A->ncol : 0 ;
604 if (
sizeof (
Int) >
sizeof (idxtype) &&
MAX (
n,nz) > INT_MAX /
sizeof (
int))
633 if (
sizeof (
Int) ==
sizeof (idxtype))
636 Miperm = (idxtype *) Iperm ;
637 Mperm = (idxtype *) Perm ;
638 Mp = (idxtype *) Bp ;
639 Mi = (idxtype *) Bi ;
658 for (j = 0 ; j <=
n ; j++)
662 for (p = 0 ; p < nz ; p++)
679 PRINT1 ((
"METIS:: no nz\n")) ;
681 else if (
Common->metis_nswitch > 0)
698 d = ((double) nz) / (((double)
n) * ((double)
n)) ;
702 PRINT1 ((
"METIS:: nswitch/dswitch activated\n")) ;
720 for (i = 0 ; i <
n ; i++)
728 printf (
"Calling METIS_NodeND n "ID" nz "ID"" 729 "density %g\n",
n, nz, ((
double) nz) / (((
double)
n) * ((
double)
n)));
730 dumpgraph (Mp, Mi,
n,
Common) ;
734 METIS_NodeND (&nn, Mp, Mi, &zero, Opt, Mperm, Miperm) ;
737 PRINT0 ((
"METIS_NodeND done\n")) ;
744 if (
sizeof (
Int) !=
sizeof (idxtype))
746 for (i = 0 ; i <
n ; i++)
748 Perm [i] = (
Int) (Mperm [i]) ;
764 Int *Parent, *Post, *NewPerm ;
767 Parent = Iwork + 2*((size_t)
n) + uncol ;
777 for (k = 0 ; k <
n ; k++)
779 NewPerm [k] = Perm [Post [k]] ;
781 for (k = 0 ; k <
n ; k++)
783 Perm [k] = NewPerm [k] ;
789 PRINT1 ((
"cholmod_metis done\n")) ;
#define CHOLMOD_TOO_LARGE
size_t CHOLMOD() add_size_t(size_t a, size_t b, int *ok)
#define RETURN_IF_NULL_COMMON(result)
size_t CHOLMOD() mult_size_t(size_t a, size_t k, int *ok)
cholmod_sparse *CHOLMOD() aat(cholmod_sparse *A, Int *fset, size_t fsize, int mode, cholmod_common *Common)
int CHOLMOD() dump_work(int flag, int head, UF_long wsize, cholmod_common *Common)
int CHOLMOD() dump_partition(UF_long n, Int *Cp, Int *Ci, Int *Cnw, Int *Part, UF_long sepsize, cholmod_common *Common)
int CHOLMOD() free_sparse(cholmod_sparse **AHandle, cholmod_common *Common)
int CHOLMOD() metis(cholmod_sparse *A, Int *fset, size_t fsize, int postorder, Int *Perm, cholmod_common *Common)
static int metis_memory_ok(Int n, Int nz, cholmod_common *Common)
int CHOLMOD() allocate_work(size_t nrow, size_t iworksize, size_t xworksize, cholmod_common *Common)
int CHOLMOD() analyze_ordering(cholmod_sparse *A, int ordering, Int *Perm, Int *fset, size_t fsize, Int *Parent, Int *Post, Int *ColCount, Int *First, Int *Level, cholmod_common *Common)
#define RETURN_IF_NULL(A, result)
UF_long CHOLMOD(metis_bisector)
#define ERROR(status, msg)
#define RETURN_IF_XTYPE_INVALID(A, xtype1, xtype2, result)
#define ASSERT(expression)
cholmod_sparse *CHOLMOD() copy(cholmod_sparse *A, int stype, int mode, cholmod_common *Common)