61 #define ASSERT(expression) (assert (expression)) 63 #define ASSERT(expression) 82 static void dumpgraph (idxtype *Mp, idxtype *Mi,
UF_long n,
88 printf (
"Dumping METIS graph n %ld nz %ld\n",
n, nz) ;
89 f = fopen (
"metisgraph",
"w") ;
92 ERROR (-99,
"cannot open metisgraph") ;
95 fprintf (
f,
"%ld %ld\n",
n, nz/2) ;
96 for (j = 0 ; j <
n ; j++)
98 for (p = Mp [j] ; p < Mp [j+1] ; p++)
101 fprintf (
f,
" %ld", i+1) ;
142 #define GUESS(nz,n) (10 * (nz) + 50 * (n) + 4096) 155 if (
Common->metis_memory <= 0)
165 s =
GUESS ((
double) nz, (
double)
n) ;
166 s *=
Common->metis_memory ;
168 if (s *
sizeof (idxtype) >= ((
double)
Size_max))
175 metis_guard =
GUESS ((
size_t) nz, (
size_t)
n) ;
176 metis_guard *=
Common->metis_memory ;
179 p =
CHOLMOD(malloc) (metis_guard,
sizeof (idxtype),
Common) ;
217 idxtype *Mp, *Mi, *Mnw, *Mew, *Mpart ;
218 Int n, nleft, nright, j, p, csep, total_weight, lightest, nz ;
219 int Opt [8], nn, csp ;
233 if (
A->stype ||
A->nrow !=
A->ncol)
237 " and with both upper/lower parts present") ;
251 n1 = ((size_t)
n) + 1 ;
266 if (
sizeof (
Int) >
sizeof (idxtype) &&
MAX (
n,nz) > INT_MAX /
sizeof (int))
286 DEBUG (
for (j = 0 ; j < n ; j++) ASSERT (Anw [j] > 0)) ;
292 DEBUG (
for (j = 0 ; j < nz ; j++) ASSERT (Aew [j] > 0)) ;
293 if (
sizeof (
Int) ==
sizeof (idxtype))
296 Mi = (idxtype *) Ai ;
297 Mew = (idxtype *) Aew ;
298 Mp = (idxtype *) Ap ;
299 Mnw = (idxtype *) Anw ;
300 Mpart = (idxtype *) Partition ;
319 for (p = 0 ; p < nz ; p++)
323 for (p = 0 ; p < nz ; p++)
327 for (j = 0 ; j <=
n ; j++)
331 for (j = 0 ; j <
n ; j++)
344 if (
sizeof (
Int) !=
sizeof (idxtype))
360 PRINT1 ((
"Metis graph, n = "ID"\n",
n)) ;
361 for (j = 0 ; j <
n ; j++)
364 PRINT2 ((
"M(:,"ID") node weight "ID"\n", j, (
Int) Mnw [j])) ;
366 for (ppp = Mp [j] ; ppp < Mp [j+1] ; ppp++)
376 METIS_NodeComputeSeparator (&nn, Mp, Mi, Mnw, Mew, Opt, &csp, Mpart) ;
380 PRINT1 ((
"METIS csep "ID"\n", csep)) ;
386 if (
sizeof (
Int) !=
sizeof (idxtype))
388 for (j = 0 ; j <
n ; j++)
390 Partition [j] = Mpart [j] ;
417 for (j = 0 ; j <
n ; j++)
419 if (Anw [j] <= Anw [lightest])
424 PRINT1 ((
"Force "ID" as sep\n", lightest)) ;
425 Partition [lightest] = 2 ;
426 csep = Anw [lightest] ;
433 for (j = 0 ; j <
n ; j++)
435 PRINT1 ((
"Partition ["ID"] = "ID"\n", j, Partition [j])) ;
436 if (Partition [j] == 0)
440 else if (Partition [j] == 1)
447 ASSERT (Partition [j] == 2) ;
454 total_weight = nleft + nright + csep ;
456 if (csep < total_weight)
461 nleft, nright, csep, total_weight)) ;
462 ASSERT (nleft + nright + csep == total_weight) ;
463 ASSERT (nleft > 0 || nright > 0) ;
464 if ((nleft == 0 && nright > 0) || (nleft > 0 && nright == 0))
467 PRINT1 ((
"Force all in sep\n")) ;
468 csep = total_weight ;
469 for (j = 0 ; j <
n ; j++)
513 Int *Iperm, *Iwork, *Bp, *Bi ;
514 idxtype *Mp, *Mi, *Mperm, *Miperm ;
516 Int i, j,
n, nz, p, identity, uncol ;
517 int Opt [8], nn, zero = 0 ;
540 n1 = ((size_t)
n) + 1 ;
547 uncol = (
A->stype == 0) ?
A->ncol : 0 ;
607 if (
sizeof (
Int) >
sizeof (idxtype) &&
MAX (
n,nz) > INT_MAX /
sizeof (
int))
636 if (
sizeof (
Int) ==
sizeof (idxtype))
639 Miperm = (idxtype *) Iperm ;
640 Mperm = (idxtype *) Perm ;
641 Mp = (idxtype *) Bp ;
642 Mi = (idxtype *) Bi ;
661 for (j = 0 ; j <=
n ; j++)
665 for (p = 0 ; p < nz ; p++)
682 PRINT1 ((
"METIS:: no nz\n")) ;
684 else if (
Common->metis_nswitch > 0)
701 d = ((double) nz) / (((double)
n) * ((double)
n)) ;
705 PRINT1 ((
"METIS:: nswitch/dswitch activated\n")) ;
723 for (i = 0 ; i <
n ; i++)
731 printf (
"Calling METIS_NodeND n "ID" nz "ID"" 732 "density %g\n",
n, nz, ((
double) nz) / (((
double)
n) * ((
double)
n)));
733 dumpgraph (Mp, Mi,
n,
Common) ;
737 METIS_NodeND (&nn, Mp, Mi, &zero, Opt, Mperm, Miperm) ;
740 PRINT0 ((
"METIS_NodeND done\n")) ;
747 if (
sizeof (
Int) !=
sizeof (idxtype))
749 for (i = 0 ; i <
n ; i++)
751 Perm [i] = (
Int) (Mperm [i]) ;
767 Int *Parent, *Post, *NewPerm ;
770 Parent = Iwork + 2*((size_t)
n) + uncol ;
780 for (k = 0 ; k <
n ; k++)
782 NewPerm [k] = Perm [Post [k]] ;
784 for (k = 0 ; k <
n ; k++)
786 Perm [k] = NewPerm [k] ;
792 PRINT1 ((
"cholmod_metis done\n")) ;
#define CHOLMOD_TOO_LARGE
static int metis_memory_ok(Int n, Int nz, cholmod_common *Common)
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)
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)
#define ASSERT(expression)
UF_long CHOLMOD(metis_bisector)
#define ERROR(status, msg)
#define RETURN_IF_XTYPE_INVALID(A, xtype1, xtype2, result)
cholmod_sparse *CHOLMOD() copy(cholmod_sparse *A, int stype, int mode, cholmod_common *Common)