26 if (wflg < 2 || wflg >= wbig)
28 for (x = 0 ; x <
n ; x++)
30 if (W [x] != 0) W [x] = 1 ;
461 Int deg, degme, dext, lemax, e, elenme, eln, i, ilast, inext, j,
462 jlast, jnext, k, knt1, knt2, knt3, lenj, ln, me, mindeg, nel, nleft,
463 nvi, nvj, nvpiv, slenme, wbig, we, wflg, wnvi, ok, ndense, ncmpa,
516 double f, r, ndiv, s, nms_lu, nms_ldl, dmax, alpha, lnz, lnzme ;
538 Int p, p1, p2, p3, p4, pdst, pend, pj, pme, pme1, pme2, pn, psrc ;
585 if (Control != (
double *)
NULL)
603 dense = (int) ( alpha * sqrt ((
double)
n) ) ;
605 dense =
MAX (16, dense) ;
606 dense =
MIN (
n, dense) ;
608 alpha, aggressive)) ;
610 for (i = 0 ; i <
n ; i++)
621 Degree [i] = Len [i] ;
626 AMD_dump (
n, Pe, Iw, Len, iwlen, pfree, Nv, Next, Last,
627 Head, Elen, Degree, W, -1) ;
640 for (i = 0 ; i <
n ; i++)
654 Elen [i] =
FLIP (1) ;
660 else if (deg > dense)
687 if (inext !=
EMPTY) Last [inext] = i ;
705 AMD_dump (
n, Pe, Iw, Len, iwlen, pfree, Nv, Next,
706 Last, Head, Elen, Degree, W, nel) ;
718 ASSERT (mindeg >= 0 && mindeg <
n) ;
719 for (deg = mindeg ; deg <
n ; deg++)
722 if (me !=
EMPTY) break ;
762 ASSERT (Pe [me] >= 0 && Pe [me] < iwlen) ;
774 for (p = pme1 ; p <= pme1 + Len [me] - 1 ; p++)
777 ASSERT (i >= 0 && i <
n && Nv [i] >= 0) ;
800 if (inext !=
EMPTY) Last [inext] = ilast ;
803 Next [ilast] = inext ;
808 ASSERT (Degree [i] >= 0 && Degree [i] <
n) ;
809 Head [Degree [i]] = inext ;
823 slenme = Len [me] - elenme ;
825 for (knt1 = 1 ; knt1 <= elenme + 1 ; knt1++)
844 ASSERT (Elen [e] <
EMPTY && W [e] > 0 && pj >= 0) ;
846 ASSERT (ln >= 0 && (ln == 0 || (pj >= 0 && pj < iwlen))) ;
855 for (knt2 = 1 ; knt2 <= ln ; knt2++)
858 ASSERT (i >= 0 && i <
n && (i == me || Elen [i] >=
EMPTY));
861 i, Elen [i], Nv [i], wflg)) ;
883 if (Len [me] == 0) Pe [me] =
EMPTY ;
885 Len [e] = ln - knt2 ;
887 if (Len [e] == 0) Pe [e] =
EMPTY ;
893 for (j = 0 ; j <
n ; j++)
898 ASSERT (pn >= 0 && pn < iwlen) ;
912 j =
FLIP (Iw [psrc++]) ;
920 for (knt3 = 0 ; knt3 <= lenj - 2 ; knt3++)
922 Iw [pdst++] = Iw [psrc++] ;
929 for (psrc = pme1 ; psrc <= pfree-1 ; psrc++)
931 Iw [pdst++] = Iw [psrc] ;
959 if (inext !=
EMPTY) Last [inext] = ilast ;
962 Next [ilast] = inext ;
967 ASSERT (Degree [i] >= 0 && Degree [i] <
n) ;
968 Head [Degree [i]] = inext ;
991 Degree [me] = degme ;
993 Len [me] = pme2 - pme1 + 1 ;
994 ASSERT (Pe [me] >= 0 && Pe [me] < iwlen) ;
996 Elen [me] =
FLIP (nvpiv + degme) ;
1001 AMD_DEBUG2 ((
"New element structure: length= "ID"\n", pme2-pme1+1)) ;
1002 for (pme = pme1 ; pme <= pme2 ; pme++)
AMD_DEBUG3 ((
" "ID"", Iw[pme]));
1034 for (pme = pme1 ; pme <= pme2 ; pme++)
1044 ASSERT (nvi > 0 && Pe [i] >= 0 && Pe [i] < iwlen) ;
1046 for (p = Pe [i] ; p <= Pe [i] + eln - 1 ; p++)
1055 AMD_DEBUG4 ((
" unabsorbed, first time seen")) ;
1063 we = Degree [e] + wnvi ;
1083 for (pme = pme1 ; pme <= pme2 ; pme++)
1086 ASSERT (i >= 0 && i <
n && Nv [i] < 0 && Elen [i] >= 0) ;
1089 p2 = p1 + Elen [i] - 1 ;
1093 ASSERT (p1 >= 0 && p1 < iwlen && p2 >= -1 && p2 < iwlen) ;
1102 for (p = p1 ; p <= p2 ; p++)
1125 Pe [e] =
FLIP (me) ;
1133 for (p = p1 ; p <= p2 ; p++)
1152 Elen [i] = pn - p1 + 1 ;
1163 for (p = p2 + 1 ; p < p4 ; p++)
1186 ASSERT (
IMPLIES (aggressive, (deg==0) == (Elen[i]==1 && p3==pn))) ;
1188 if (Elen [i] == 1 && p3 == pn)
1216 Pe [i] =
FLIP (me) ;
1235 Degree [i] =
MIN (Degree [i], deg) ;
1248 Len [i] = pn - p1 + 1 ;
1266 Next [i] =
FLIP (j) ;
1267 Head [hash] =
FLIP (i) ;
1273 Next [i] = Last [j] ;
1286 Degree [me] = degme ;
1293 lemax =
MAX (lemax, degme) ;
1302 AMD_DEBUG1 ((
"Detecting supervariables:\n")) ;
1303 for (pme = pme1 ; pme <= pme2 ; pme++)
1319 ASSERT (Last [i] >= 0 && Last [i] <
n) ;
1333 Head [hash] =
EMPTY ;
1361 ASSERT (ln >= 0 && eln >= 0) ;
1362 ASSERT (Pe [i] >= 0 && Pe [i] < iwlen) ;
1364 for (p = Pe [i] + 1 ; p <= Pe [i] + ln - 1 ; p++)
1366 ASSERT (Iw [p] >= 0 && Iw [p] <
n) ;
1387 ASSERT (Len [j] >= 0 && Elen [j] >= 0) ;
1388 ASSERT (Pe [j] >= 0 && Pe [j] < iwlen) ;
1389 ok = (Len [j] == ln) && (Elen [j] == eln) ;
1391 for (p = Pe [j] + 1 ; ok && p <= Pe [j] + ln - 1 ; p++)
1393 ASSERT (Iw [p] >= 0 && Iw [p] <
n) ;
1394 if (W [Iw [p]] != wflg) ok = 0 ;
1446 for (pme = pme1 ; pme <= pme2 ; pme++)
1462 deg = Degree [i] + degme - nvi ;
1463 deg =
MIN (deg, nleft - nvi) ;
1470 inext = Head [deg] ;
1472 if (inext !=
EMPTY) Last [inext] = i ;
1481 mindeg =
MIN (mindeg, deg) ;
1501 Len [me] = p - pme1 ;
1523 if (Info != (
double *)
NULL)
1526 r = degme + ndense ;
1527 dmax =
MAX (dmax,
f + r) ;
1530 lnzme =
f*r + (
f-1)*
f/2 ;
1537 s =
f*r*r + r*(
f-1)*
f + (
f-1)*
f*(2*
f-1)/6 ;
1541 nms_ldl += (s + lnzme)/2 ;
1546 for (pme = Pe [me] ; pme <= Pe [me] + Len [me] - 1 ; pme++)
1559 if (Info != (
double *)
NULL)
1564 dmax =
MAX (dmax, (
double) ndense) ;
1574 s = (
f-1)*
f*(2*
f-1)/6 ;
1578 nms_ldl += (s + lnzme)/2 ;
1634 for (i = 0 ; i <
n ; i++)
1636 Pe [i] =
FLIP (Pe [i]) ;
1640 for (i = 0 ; i <
n ; i++)
1642 Elen [i] =
FLIP (Elen [i]) ;
1650 for (i = 0 ; i <
n ; i++)
1664 for (e = 0 ; e <
n ; e++)
1669 Elen [e], Nv [e])) ;
1673 for (i = 0 ; i <
n ; i++)
1695 if (cnt >
n) break ;
1708 for (i = 0 ; i <
n ; i++)
1720 AMD_DEBUG1 ((
"Path compression, i unordered: "ID"\n", i)) ;
1778 for (k = 0 ; k <
n ; k++)
1783 for (e = 0 ; e <
n ; e++)
1797 for (k = 0 ; k <
n ; k++)
1800 if (e ==
EMPTY) break ;
1801 ASSERT (e >= 0 && e <
n && Nv [e] > 0) ;
1808 for (i = 0 ; i <
n ; i++)
1821 Next [i] = Next [e] ;
1835 for (i = 0 ; i <
n ; i++)
#define AMD_NMULTSUBS_LDL
static Int amesos_clear_flag(Int wflg, Int wbig, Int W [], Int n)
#define AMD_DEBUG1(params)
#define AMD_DEBUG3(params)
#define AMD_DEFAULT_AGGRESSIVE
GLOBAL void AMD_2(Int n, Int Pe [], Int Iw [], Int Len [], Int iwlen, Int pfree, Int Nv [], Int Next [], Int Last [], Int Head [], Int Elen [], Int Degree [], Int W [], double Control [], double Info [])
#define ASSERT(expression)
#define AMD_DEBUG4(params)
#define AMD_DEBUG2(params)
#define AMD_DEFAULT_DENSE