29 if (wflg < 2 || wflg >= wbig)
31 for (x = 0 ; x <
n ; x++)
33 if (W [x] != 0) W [x] = 1 ;
464 Int deg, degme, dext, lemax, e, elenme, eln, i, ilast, inext, j,
465 jlast, jnext, k, knt1, knt2, knt3, lenj, ln, me, mindeg, nel, nleft,
466 nvi, nvj, nvpiv, slenme, wbig, we, wflg, wnvi, ok, ndense, ncmpa,
519 double f, r, ndiv, s, nms_lu, nms_ldl, dmax, alpha, lnz, lnzme ;
541 Int p, p1, p2, p3, p4, pdst, pend, pj, pme, pme1, pme2, pn, psrc ;
588 if (Control != (
double *)
NULL)
606 dense = alpha * sqrt ((
double)
n) ;
608 dense =
MAX (16, dense) ;
609 dense =
MIN (
n, dense) ;
611 alpha, aggressive)) ;
613 for (i = 0 ; i <
n ; i++)
624 Degree [i] = Len [i] ;
629 AMD_dump (
n, Pe, Iw, Len, iwlen, pfree, Nv, Next, Last,
630 Head, Elen, Degree, W, -1) ;
643 for (i = 0 ; i <
n ; i++)
657 Elen [i] =
FLIP (1) ;
663 else if (deg > dense)
690 if (inext !=
EMPTY) Last [inext] = i ;
708 AMD_dump (
n, Pe, Iw, Len, iwlen, pfree, Nv, Next,
709 Last, Head, Elen, Degree, W, nel) ;
721 ASSERT (mindeg >= 0 && mindeg <
n) ;
722 for (deg = mindeg ; deg <
n ; deg++)
725 if (me !=
EMPTY) break ;
765 ASSERT (Pe [me] >= 0 && Pe [me] < iwlen) ;
777 for (p = pme1 ; p <= pme1 + Len [me] - 1 ; p++)
780 ASSERT (i >= 0 && i <
n && Nv [i] >= 0) ;
803 if (inext !=
EMPTY) Last [inext] = ilast ;
806 Next [ilast] = inext ;
811 ASSERT (Degree [i] >= 0 && Degree [i] <
n) ;
812 Head [Degree [i]] = inext ;
826 slenme = Len [me] - elenme ;
828 for (knt1 = 1 ; knt1 <= elenme + 1 ; knt1++)
847 ASSERT (Elen [e] <
EMPTY && W [e] > 0 && pj >= 0) ;
849 ASSERT (ln >= 0 && (ln == 0 || (pj >= 0 && pj < iwlen))) ;
858 for (knt2 = 1 ; knt2 <= ln ; knt2++)
861 ASSERT (i >= 0 && i <
n && (i == me || Elen [i] >=
EMPTY));
864 i, Elen [i], Nv [i], wflg)) ;
886 if (Len [me] == 0) Pe [me] =
EMPTY ;
888 Len [e] = ln - knt2 ;
890 if (Len [e] == 0) Pe [e] =
EMPTY ;
896 for (j = 0 ; j <
n ; j++)
901 ASSERT (pn >= 0 && pn < iwlen) ;
915 j =
FLIP (Iw [psrc++]) ;
923 for (knt3 = 0 ; knt3 <= lenj - 2 ; knt3++)
925 Iw [pdst++] = Iw [psrc++] ;
932 for (psrc = pme1 ; psrc <= pfree-1 ; psrc++)
934 Iw [pdst++] = Iw [psrc] ;
962 if (inext !=
EMPTY) Last [inext] = ilast ;
965 Next [ilast] = inext ;
970 ASSERT (Degree [i] >= 0 && Degree [i] <
n) ;
971 Head [Degree [i]] = inext ;
994 Degree [me] = degme ;
996 Len [me] = pme2 - pme1 + 1 ;
997 ASSERT (Pe [me] >= 0 && Pe [me] < iwlen) ;
999 Elen [me] =
FLIP (nvpiv + degme) ;
1004 AMD_DEBUG2 ((
"New element structure: length= "ID"\n", pme2-pme1+1)) ;
1005 for (pme = pme1 ; pme <= pme2 ; pme++)
AMD_DEBUG3 ((
" "ID"", Iw[pme]));
1037 for (pme = pme1 ; pme <= pme2 ; pme++)
1047 ASSERT (nvi > 0 && Pe [i] >= 0 && Pe [i] < iwlen) ;
1049 for (p = Pe [i] ; p <= Pe [i] + eln - 1 ; p++)
1058 AMD_DEBUG4 ((
" unabsorbed, first time seen")) ;
1066 we = Degree [e] + wnvi ;
1086 for (pme = pme1 ; pme <= pme2 ; pme++)
1089 ASSERT (i >= 0 && i <
n && Nv [i] < 0 && Elen [i] >= 0) ;
1092 p2 = p1 + Elen [i] - 1 ;
1096 ASSERT (p1 >= 0 && p1 < iwlen && p2 >= -1 && p2 < iwlen) ;
1105 for (p = p1 ; p <= p2 ; p++)
1128 Pe [e] =
FLIP (me) ;
1136 for (p = p1 ; p <= p2 ; p++)
1155 Elen [i] = pn - p1 + 1 ;
1166 for (p = p2 + 1 ; p < p4 ; p++)
1189 ASSERT (
IMPLIES (aggressive, (deg==0) == (Elen[i]==1 && p3==pn))) ;
1191 if (Elen [i] == 1 && p3 == pn)
1219 Pe [i] =
FLIP (me) ;
1238 Degree [i] =
MIN (Degree [i], deg) ;
1251 Len [i] = pn - p1 + 1 ;
1269 Next [i] =
FLIP (j) ;
1270 Head [hash] =
FLIP (i) ;
1276 Next [i] = Last [j] ;
1289 Degree [me] = degme ;
1296 lemax =
MAX (lemax, degme) ;
1305 AMD_DEBUG1 ((
"Detecting supervariables:\n")) ;
1306 for (pme = pme1 ; pme <= pme2 ; pme++)
1322 ASSERT (Last [i] >= 0 && Last [i] <
n) ;
1336 Head [hash] =
EMPTY ;
1364 ASSERT (ln >= 0 && eln >= 0) ;
1365 ASSERT (Pe [i] >= 0 && Pe [i] < iwlen) ;
1367 for (p = Pe [i] + 1 ; p <= Pe [i] + ln - 1 ; p++)
1369 ASSERT (Iw [p] >= 0 && Iw [p] <
n) ;
1390 ASSERT (Len [j] >= 0 && Elen [j] >= 0) ;
1391 ASSERT (Pe [j] >= 0 && Pe [j] < iwlen) ;
1392 ok = (Len [j] == ln) && (Elen [j] == eln) ;
1394 for (p = Pe [j] + 1 ; ok && p <= Pe [j] + ln - 1 ; p++)
1396 ASSERT (Iw [p] >= 0 && Iw [p] <
n) ;
1397 if (W [Iw [p]] != wflg) ok = 0 ;
1449 for (pme = pme1 ; pme <= pme2 ; pme++)
1465 deg = Degree [i] + degme - nvi ;
1466 deg =
MIN (deg, nleft - nvi) ;
1473 inext = Head [deg] ;
1475 if (inext !=
EMPTY) Last [inext] = i ;
1484 mindeg =
MIN (mindeg, deg) ;
1504 Len [me] = p - pme1 ;
1526 if (Info != (
double *)
NULL)
1529 r = degme + ndense ;
1530 dmax =
MAX (dmax,
f + r) ;
1533 lnzme =
f*r + (
f-1)*
f/2 ;
1540 s =
f*r*r + r*(
f-1)*
f + (
f-1)*
f*(2*
f-1)/6 ;
1544 nms_ldl += (s + lnzme)/2 ;
1549 for (pme = Pe [me] ; pme <= Pe [me] + Len [me] - 1 ; pme++)
1562 if (Info != (
double *)
NULL)
1567 dmax =
MAX (dmax, (
double) ndense) ;
1577 s = (
f-1)*
f*(2*
f-1)/6 ;
1581 nms_ldl += (s + lnzme)/2 ;
1637 for (i = 0 ; i <
n ; i++)
1639 Pe [i] =
FLIP (Pe [i]) ;
1643 for (i = 0 ; i <
n ; i++)
1645 Elen [i] =
FLIP (Elen [i]) ;
1653 for (i = 0 ; i <
n ; i++)
1667 for (e = 0 ; e <
n ; e++)
1672 Elen [e], Nv [e])) ;
1676 for (i = 0 ; i <
n ; i++)
1698 if (cnt >
n) break ;
1711 for (i = 0 ; i <
n ; i++)
1723 AMD_DEBUG1 ((
"Path compression, i unordered: "ID"\n", i)) ;
1781 for (k = 0 ; k <
n ; k++)
1786 for (e = 0 ; e <
n ; e++)
1800 for (k = 0 ; k <
n ; k++)
1803 if (e ==
EMPTY) break ;
1804 ASSERT (e >= 0 && e <
n && Nv [e] > 0) ;
1811 for (i = 0 ; i <
n ; i++)
1824 Next [i] = Next [e] ;
1838 for (i = 0 ; i <
n ; i++)
#define AMD_NMULTSUBS_LDL
#define AMD_DEBUG1(params)
#define AMD_DEBUG3(params)
#define AMD_DEFAULT_AGGRESSIVE
#define ASSERT(expression)
static Int amesos_clear_flag(Int wflg, Int wbig, Int W [], Int n)
#define AMD_DEBUG4(params)
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 AMD_DEBUG2(params)
#define AMD_DEFAULT_DENSE