From 6f10c4d7e70b420a1f1d0e7e89e25ed3ba69e2c7 Mon Sep 17 00:00:00 2001 From: nivesh Date: Tue, 5 Dec 2017 14:11:14 +0100 Subject: [PATCH] color_sparsity_function added in sparsity tools --- doc/doxygen/images/color_undirected_graph.png | Bin 0 -> 17705 bytes doc/news/changes/minor/20171204NiveshD | 4 + include/deal.II/lac/sparsity_tools.h | 53 ++++++++++--- source/lac/sparsity_tools.cc | 73 +++++++++++++++++- 4 files changed, 117 insertions(+), 13 deletions(-) create mode 100755 doc/doxygen/images/color_undirected_graph.png create mode 100644 doc/news/changes/minor/20171204NiveshD diff --git a/doc/doxygen/images/color_undirected_graph.png b/doc/doxygen/images/color_undirected_graph.png new file mode 100755 index 0000000000000000000000000000000000000000..de5e0980346cfc4be9eb54468034d9bfea22b3f6 GIT binary patch literal 17705 zcmeIaWmr|=)-}9E1SA9zl?FjVy1S&iB?LuU8flPFkP@U3Y3Y&%rBk}3yE`RB8s5oy z&ikC_eXsBPaejP1zUw;t(7oM@wbz>WyyqNqjIj(N}I$+S!Gol#;sB+PbW3W}UgLCTJ@U_py#o4Zqisd0>4eO6Q|b}s6y#<`f)tvZ z3M>k?V#cq{q}}X{)!Y=-4c#mZd5tK9h0q0D_}~Oq#t!=AE>@P-_Ixga6#qCcAH2T) zXJ!iWe;ndqAxNR6piC}iV`ogx!NkGD!YJWl=EO!JgibDCXJo>sDlYlYQ@}exiq{Sf zwtURY&d$zE&g@J!cBag%yu7^3ENskdY>aROqrI!OgT4!+wLRtaDgNsm;>Pxdc4oE? zW;WL3*XPtXuyJ${q@aM$$^Uus>)8MI*{$vW83YIi^YtgptV}G-|MPGMGn4<9!>>R2 z*WuT{%%^PTVr;1;Zf0d{Z4Z|qNWsC*^^cSN>r?Ij@hKZC=RZEZJ`wo>)zdn#QHZy$p$W8w<7Rw9sHl{`cJt2tqA;E2mdF#{{Iy&^nZanV{1Tk&H&vK*&6Nx?7L|% zDx;2uhBi5`G>1TtBV@#%s=G{VCwd8}k6*RT_HbJ4QyTtyEz6OIazc{{DfxtesuYv|_YhIlVRj^pL)C;ATlZYRErhKv+Ti3I;> zFHVkwW)uSN-*?}I_hGygIB3XhQt)0`RXy8Tjv_p}rsn+b_T;BepWt>+%av?>3T5D_8^z;iv!>jBfE%`hCUCYnoffuvlwiVuFJZ3o$V{DM8VHadu>3ZcZxb#_{&=)-8+& zMdOy~sK}z3iNV2!hlgIhU-o`Z)ktb;rlt)lra9hxr=B}7l&+yy*s`ir=V&1il)-J2 zv^iC2KRh%P#vAdjs;cVe&!1UJ$!;z#^2tIZ%|$VI4}w~5-MTee@Z#-iqH|4ctqL

CpR@rII;tr>DLNH=ft68DndVWy>R@9aF??_x%E=0SS;vNuUEGSZ&n z@#DdUudcSH?VYD*mG(Ff9!ScZgiR7-prfm*srmT$w0$DtUW<&1ib~JO*d8nP=`f;b zB$vGH>+4IS)G8sK&K^6ElCZil+`w*%&+oir#Db59aW^n)fA{1Z0)s`wh1o)IqhVyk z>F?G!>K)>SH^gQrtb}t1CxL-`dhTyL1A5UA2diy5+WImwGDAVQfjxV3jXpv`Le2ZF zuJcX4JRz$qD-`48k~eSP)Jvgc9qU$(5PLzR=W85$mbWUr3yd2y&o_{qe=LawMr zgq+9g@_e}~h6=X>gKq3-sUyOhQjaDqoX|#azLY&M{slR?nAhbm+q}?M5tNrOl>VJ=%uSZiAIu;wXgBI z5(-%y%v7LMJ)X3w7qnYyZ~a6BxrmN|!N|bi?c);^6m%Bj;N;ZX(<4C{iiWPHrx&`| zV`35-h{r_xu0f>eyI(Gy%P|hp%|}dk{%%LAsj8LwbhYH==7#Zxuy9*X6%`ectCpmt z8D3ppl$!KR)Ol2ggoNbetQQ-$sXu#m)RCvp6`!A#B~^?rNq(xTs>)%AlKg6(gkMDB z*1$l+Pvk#`^RrhdG&E!77)wq#J>AzQ78o8L79b6k?r3UiT3InsQtF#gDl02n=}Y!H z+!ziCx#N1@QsepakB>imr5hfu{}PW85EUi+hz50PN<{O>i|q8&TMN_G)vl9>Q0V+X z$tZ-fr`aEyM*fRPdiu8~?3|q2XDK;3W>QjZ)78#rG06h1Y=7R_2=f`^&!tVX*Qi#_U z7HKaZ;34%(@f+H@WA5$Soq3mB8VYOo6JS1ro5hUm!0Y0>xS3K=a0hYp`^vb^!qAWs z(azbpva-@&`kBT6ugM_iqxgpr{iyZD{1Ncv8!t7@%g)xVaVb8Ege>>=M&jq^uPk)v?CQ$@_U$@izHOz2 zxoqTr-BFyJY!5f|R1JC)Z{ENEgy&jN?V&CJc5sp4|Xd70fCvB z8JlTvKme5Y&5`^~y^8Yk@`8fifdO0@w5QK3EobPMk|c|ETR-j2-EiM)@jBnjN}gMi zIiB-bogF}k$OX|Q7fP^hhuQfs8X7MC{reXcn^ZoI!-b&hLkRf~5%<+)o?ypajuOlCzp+2T=jqSRK zkBMP!L6R7u>SDn>+ik`UB^5mVv(CaW78@SkKQptlvl9~K^Hl)fFJHS*A;DEvM&W=K@NVp4?t(;sJT>18NwdM{k?$48*>ff-cP{jLRQyN6QGBe|KF3=JG z5US3X{^O3ec1?{y9u|@4lN=JloWi=aG_e;iF5+$K2z0ORw(SiK4aLO~l7?pG=UPlfvl8s^a)%mJ02{Ccq z=|&!$!1s>V?%Y#(d3g(q&4L%zva+(sNH=gX4WfSKCC0J~HaC0F(`V5;xV%Vo6914T z{b!~(5%v7y;^5%GSM<@XHnQ(llad2+N(u^`Y;1A7_SB(m>?|zOva-3~z9q2eH@%C$ zi|*Srn5ATDY+PAg4eP0@prG*V*&!5Y`<3peB~ODRKM_qonwy=?f*;)5+uPJ6S{W%Kjio)S5!A8}78X|f_UNxQ7vrQ5 z3nitPf8Y8ey^YimtTT}eX-it0;T3>$r z_)%LcsCvhHf4cSIYnm4?NPd)BBne$S6s)CT&>-?VbZ{~-U|pPVeltAm*V1Am`#6`B z^kr|awFfEzY)dgw(UC$u8xs@21xw-Ek(lP4=4ku}<{h4l&QGSFhe>@=?&r>*!2oC42I1!Qt)g z?LTHc-|pycq-#d*`^q~xeUFSBEE+8+Ec{(*zbZ~~Hv-2y_ZrSTdyR_FDA09o5 zgtL$TF*Y@2)+%~6*7q$d>&L4`@1-T9$B&SoRevg!=107;w6wIgP6`iy-~Hxsybuu) z5m)>Lo#M{=y0(sv&WjhHK79CU^kZ+>OzQ8J<9yStPJy@K-NeQUvkNUjdi^Ks4pndo z^UePKifm}IPDFZ%PKb9c2DL{sZ`(r2q*kOGGqDlG#Kf@43trZKT>2m~Eh(X0_PRe` z=f|Br&|Hz0Ro-cgv`-%m>uCA_RT(q57k4zJ821|hqfsc>R!^5Mz zvW|G)-q+_PIB^3ZB_)-k{v04i_a0~e_;_q=?E3opiQ8pjXsFVgH^r8d7RcU1&~HqP zjB38$KViX)6nq=*@f_Q%o0Xe;bZqQP^L$N`S5{``%J%lfVyG~M*`xLld43cWl)`P{ zxY$^zug1p4kL=wQ6q0`&S-eoTzdS#|4g7$lgo-v~<=!*#{wh-)XG)JWc2PNANKCAG z^hAjj69WxRT2V1`Al>Wd+7?%x$u6 z(*x09Q2c;FD=Z?yJIaszAy0^2g{?kv`Ar1uD8Te(Wq7fRyJ}im*;!fKstU=N&dx_~ zAvLQUG1jr3QUCyQba0T=;D_S&yqu1gH#YdBLe?sTCnPH)lXt0!eDNs5SwJb(UNP7VW?6v>h3ep5rktCjB9^!US+nw4yISYcb9 z1Sq5_A1shJxbAoxcYR)7UJkcF)m-Lm3l7FyHaj(PadnN3j#e?`rAGGc=ayiAs_q=lfM*muOpqio@?&(n=$5GeNfMaoK zl#>4J?kYE7#0z`XSz_2f7X2__zRLM+k_TPccuB!^=)kWUa>%Rg(|VDFbm%n&1D3Q>+|Q&wDW}T%h=J3zGdU~_x=k9j3Zem}p)7To8?HCyu`;r8My2HKU)>&e^VJr&U947MK2h9JZ-pR-# zDCi+G-IW1Tr*TNhxiOW^sS$&2g)%u#R7?z|0!7q&s71tWGASh5vlN`1_hZwL(zCMa zzrQf>L-W(O82Kh6FE4(36wP?<&-x(70|xT0VVD>-pk9uQP}o17_`}J?1;bfnhPN@n z;c8#9RHrztj}tKoNrzpd1K)I8n^XsCW>h<|QnFC3%bo#dv-F=dOf)p8Fi1Jvog&I< zlhSQkyIbBUggL#cDlYvx1o*+x^qQ$=f&q8m_pL^1@+0OJ7t_jas>$ky zz|MYbb!yb^8FzAWBApj7D(~i2vpF{>vN8Kw zM5JMFu}$X32&?x{dl|d)j;`vgZ&sG6wzf8O1h%$SUdN57tSp*DMHAadMWo1U;mmmwiWR8B&tj2bBe>UL6(?diQ&gcj7^CP{7H->W{LrcDrWS(z)xA zfTnX2u*e~?qlqz_p`Zbj$W=cvp)?CoH$OG1Ioqkm!oqqy-9-Gp>Jw!^WhJkFb4O>V z=n5JlEIj;aY-Zt)8xUS;d3p5-*L*Z{TPU?3&Hho!0gI#v*lY@JdiSCMKSTOAn2WjZIHu zAz+MxMlvukFf^pT^Y~j?8HcH<=|@hFTCBN|d>s-J5^aVNTVIT)GU5~}04j`)Gg2qs zI64}$;16L0gogG(liJzX=$yBe)aAeCA5fehhb+QS`jAN%5aRc;GWUZXZUCUM^3ObjW2ryod8x%;`8V@a;jY5c{*0};Y1oREmX^!@ zl8lGPh4ZY3b7#~O<|j{Z(3teUD(5;l$hjgfZ)xNyW@@GHe!iq#$u-ItY>RZ>zCM(}4UDwZ|4ZF_(I{K?JD4ZKG~NJyw! zvA#(qAfU_e0E&YL?fgWUS>)8-L*#WH0PV2}2?viJVPj$9sXYmq%uLsciXO)&wBt$W z|C$J2&Bev_Jhc2y0LE8m+P@}9WIkCn(W)jY4{8KmXeS!4foD;+7Q;-rMNDL5WOa45 zWxD*M*BsZq_>*K;U!Pu`d*%17Dhz&tE=do-L<3V;j;CuewNSR4$^ z>D}Fnlivf!EtStl$%{(NTZ)q8Vl#Y~0N1q4Dnutr<^fZ~UXK)FwjO3E~B0TZsE6`#M?d(c|g1Rc+ zEC%2~VUUFk#l(b6xh`Z13fmhSZguq^^+`!dg)jcxqoUVJu{|7^nyRrJFZuWpop<`J ztbfoxv5@0N%zb(^9kUzm`?qT@xEP)zS3CREP?caHA$c;==M@xWraMi|+M3Ro(z(si z>~@6ircD(h?IU%163ADeaJ50lh53Njeg(%tQdqdY++tMY*)xSCffFbyTJ@e65ma)g zXK5K3#&6$N;}+QRisPYc&Q@4WRR9S5QCX>NeIwT|Xn!iN@ZtQip*Qx>+26(l-ms)Q zr>Er6qAomN;zaAW1FP_ZNb7D6IdOOk_!9%D&v00R<2 zSy%UbKOzeA;c`k~iz;>TCH!*zN^X$nKPmriEa7_?KOQt zR&&7id*2hTnC0x?fJq^kmYOQcg>mXn=J{)2U_bcXyd79Wvx;F>L z$7P0H>+v#Cn_K5xLQ^*}KeiOTzKi#;`SN1dTf%A`_qLi2|H`jNbY@by6vhs<5iO^W zF#}WOVzC5P+6{_-?o;d3CUnIxccJtH7kwsd(FG7YqMDc?2j(+U@rnSE4k$pT44>nq z)5loL%jf10_2)=$-r(T?k&-oOA~yaH`tYz$gy(3YQ(pp>8>mailV26{u|4N`%3ku>wa zy}V?e{!NpD^WY7J*zV^MN_eDSFEp1FJ$>H(zMXFZD+5D!Z|@EarD|D<9x@%(&cEXX zxRDe*zvbuOM}PQ+mVl`Af(O4hS=f^QbYH}d7Plq&+n zhG79RT3cxz<8D_~QHwR-_$Vm}bZ;behfE-^6XxZq^y~1%Z5Dg#mcLn`#Q50|K8VBX z%_m&J5-qVRHRYotW)j6vIzBl`^rPqok{|O#$0OKa|KV zOES97HfP`8x2x}2*_1uOH@Z*BV&Hv#l8&{3HQqYzV@s4e`Pltv+L?pUs$%O~cJ>-D z@^|mvRgeA&+zBhD*t{r01U2N$_rrOOQ-0Vh(s_}J)}P-N?PAr@$fJ&p5H=h1j&_#JIAxvf1wYB3GM^3*$}@ z$~~r3`uD*1KiAPA<8ugTF~BlLY6SMH{$zznSXlUD?d!K0^UsS7ZngN$ND*mR{$(Wg zqU0>M{=2pFsC#ME*m(RQ-qv`H>n|CL^j{&vIvS{XccAery7RrE&FWk*zTeF-R$~!1 zulmY|5oUyY_aepo?*RW9e9V;Q0ZbbRI4mqIUj*NBMRufrCxsPRb2wEJzWA_stlYG` zwRH}RBZb!^{@=SUzDGM|$-D=v!2~Zp{^k=#X|uX_kCFMssr&Zx<{Puy$|C%Pf6_D4 zcXq5J{Tk)L((fw=l^2Wx;1Ybgzv9Vn$+)p2n z!^6Wx`K`=GhkIs!^bwLbOkey;5la*2-{dZ+r>^>&w^FD^lw~e3Nbc#9=rmn-a@KH% z%d1w~dV#GUMJB}~?`pA=Cn+h(b8kTc*eFfS(Hm#)oPW;<+OJ@SECS&jd6<%$muF~b zcoPX}YkT{NcJ=u9IM6ow`ufCovbc2tZbDZ7Y(DIlBC9=FiEme~-qz&WFt5gWXVgAAC5=hMiI?{q??3D7Kd5K- zosOLTI+HF$W400-mz9?%!m@C4!`wOA)a2c@ys@^%5-X3{3<_mjd_15kT^Ki2RNm{4 zL1jvw#!CSaG&XvTE9+8(C-6ImysG%jpuOdU>&yAikfY6Wh;)H`rtw&oq_jm^5OfXZClGyT>bk6W8`< zCVv0^9YasAovF`+yVw-XMBd^{CQZL#d2tcxw|kp->_4&F1iy{sF(s)p^oO~0@7ccm zEx^Dof@%{|I}9U`Be3uw-ezV}7i$GC@+2yffyf2QPEU6?)Vxo@!Ap}hA~^T&F9X-M zvLYEfp&%Oc$8h;eyi`} zeR|N%&>n!stD>UfMwQsotzlY-nio>NtI$mC0N@v4W(3$yXsyo(L zPxCRwRKrB9SvJ_P3o3n6bMp&b-R!Cw9B=W6Tfzke?*;1UqPm>N~-l$V#6 zmX-zypUn}2^whjPgT%|ri)!?a!tKHim@u20Df#%S>grzdrfER`A|k3b=^@NDc|tDz zF+P6s?03Bq`Zf@$w5}{>ovzw2-R5cJe+&-(R#2ev-J;s_!VPo-Wo4Yhzb+!m?||i? z+{VP{ti~>>t*!O*leDzlfXVuKL=I45NYVc2M_+j zqQQjrX)F3M71fJMJ1Po_R2x|Vq?Dxz8Ch9XlvVJ&ft*e_L{TLk! z>lxrkH?c5`SSM)zVNTg*A-l62Z-tV{h=|T62Bb4o&D7QL5HOQ}O*cc9c{-6&!Hb0O zX+*=oxcTnOmoKAXl5`J(U^Oarcc6=@3~+c41qV1`VqwYTlMq%i#VBUkOjW47c;Nx5 zRah2c{A3R>KcqlA!CgF&OcLOAM>7-Oy+f#4_)AvNx3X*j3%z1j33^5$?I(3|oDaUf zz?>+*B2Yn2Ep!5zJKTxZBIKGdU+sy1c>g}Ki=8?%B7ycZZ=`po_U-j?IfXOB!;bia(uI2Ub%4#j zekCtUK=$5mFDr$-oF52bFpHC&P(M zxpO=;WEj5yqf0*u=nt0XufIIaOPxruE%cTwKGSCdqAlEA=&IrUO=cNN*y!M_Kz;{s zJ`L6$yea_!kma3ml-Eq;kJxdP`uhFl-$W{B_SvEMQg&TD0B;*}K9?R7?y;`azX! zl8^C*z$x3=*}=|^=_)TSzKxDPQSVhBvE}_qBute5zZh|d0iYQCXA>zUyfESl(9qC8 zjpE*mY+JMfYzukG&rfu5Ds_MQ1rK@?PWipNcUg1G#CjgG@r2M&QSF_aUj`-<-=P80 zg_=4OycUqy(kN*kKKo^Q^u8x_>*hAqQHVEWZw$_}_%K2cUYHmag;yyvNPNe%>oX&; zQUp{JDk(O>vYL^4%$LEoZ8* zD#`J?z=PVaVx!aNMe`C@iho3oQw!tBgj`iji!xGjN*A@S`uO?z2tB=i?VkCRuxm~x z%W^n;5n^r3?0x;$8)-tnbUY0#3P6?m9R<^Ce3O=uA;>ukm(74^mS|rxC;w!QmIXZ1 zV^TVruj8+3d>T=_Jy-sFaLF?xS4iU%r{a#L!!S3;VcD{$gj!=6^;+H9Y%z7Q-k<0Z zWWl(P=iy{MdkoRsYj*Xjrk~WF5lvnlY|@n2*C~>U5&7g~%O|oMzWFm-P7|V;+a4*$ z4;QjIT9{SjL~9%Z4jl;0ye$v%V0^mj`um%xGcJptfHV1`m_@0R&eemREYAPU)8gdq zZ{Oqk_BN?}-aF6vuYY}G|K5=6BgzLskPw~Ac7aF81elVxwk!y7DXDtD#NNApN_cp9I5_-)ZY8|-QwjPT%y}S|hD(1K^2QfzFI$|SXT{qd8y{CuVo@8M!+EwlEma#!WaxN~%MZXr?MQ8GY-G*-r&hE;+X1?t zm{@?}$sXWCD9G0}vLuoj3DWK!4vq*oBF2b=K7I@#=EcRsGcqyZ(p`11wbd#$Q2?6J z*qCYn+dH=geH$ub;fw0evJ;Q;c!A3S5(en-J(rq!!BVhlC@U+=%VWwmN-9TaW|55V z--_zL^Q31FWU)erA5$|N1K@0+V0@JQ)8bc%<%##y6nH!ep=I=9G z?Tn^RAGu@JtpecZ=TAgKkm`coEs(5%*>o2Ye)MRb>c0+U9#C|57mz6zqmTBZpS-3W0ShB+3b}txPTn?iVol+`-0PwW}lpV@UwR z4T{NiVgytlWpplYacI9REVk)o(3M41w`r?+(UHBgv$J7N__Vd~2Hy`Dxc*I0mxipV&J(`T>rs7^kRF zVn9NWf>q|jba3=?C7qt0UX=GIWxFUf{*q-3Xg}?#BvhPjpxc80(kFB#fBWdJv%Nj| z9D+hZRt`@7fm?jbNUGg1iEE$3sRHKzalp zz&l_NrN=M(qw!iy1MwYtmY#~+pe-nZg&7$@0F*jyKc})xy_<$(X9oRLkj&#xIGcr3 zrCSJ;R(Ko-K$GmtYBm>vmmo#J**rakRH>27q#kWUnU?4%PZMAH5*4Km$b*!$0E}aw z_0m&P^dSj=euu~!7?mGv7S>0o@IxO}eZEcW%e%niIoEIlU<(1k2_deq|HJMtCW_Vzcu6on| zD5lE!_e*WuO}U-rN?S)~=bMN|+efs1(vRtwnG3&t!wVG0`h*42r{Qp$-B`jCNwqL1 zlmSICXXl5AqH$tMq(2uN_|u>mSn!xGW473T+DVfHT!BT`R8e{KAP8Xc z)YR1J4@+pkAUeWwQO3`3)b#N{zTyTx=HWT6JR@H*e6I?TTo}+9n9+7^ZPRA zEK6EyNMRENftBKCmj7gxTIyN)#>&FV`UVm-akIhiePd z2Ia4pR)KZTPDk>Ok?GNyowlN2Yfm#LnzQd#xu4)Eku$U+S8-S64k$_cFi@<(xExHjv5%ZKk-Fw+po9y9PXW{V!^=%5G ze50I!oe`@G3yz&$tvd2#!b3mW8W+>wM!t3HFeDjzG{i(yufC^?KBnz#k;;E`)WX>0 z`R5p-lhcAP{G(QDqyH@|fw#-$?OUZpzUX6Y3Mf@QCN^V5PXRl9KIV;@wu?>xsT_nQ zKYxFAd`#`@QIySUqO8#ug82|P;Oz{(XcC0%y9rO5@r)))5li%+$077@( zo>+z*K0p76=!qH{*j7zUB-8p~rUa%L%of@C$S+<@!wcA8D9Ff|RJu|j#L%MGJw&C# zqRyMnDPyG+ZTK1W4%_Si%H6~-5|r2 z7C6*gi5^!dpHMyl|bJzbs0~Z!KTxjpDzOJ$?ABJTlp9 zc=qb2ZQ`%ta+A&|ei@lrtOYI6l`jbiTU%QK)>AwZeRUpZP8Jpxycf?f4|aEt*Rzso zwHqNln3$N5n-7740COmO&>InB*q2?RJFBv z19+W5+MTHf+2(AY=-QSAhRCWazK_ENqVwjKmhNCJhok{8!EHH)KtT5n`SgiIa6VO_ z{II;orL+lqC=`K&*tt>G$$m?6)G>MUNzN1Xp4 zO)*gn!4b~Fi~83miS7)7=LSP?zh*~EX~di0yG4QEEc~* z9$rB;j%)H=nO5B)ydq61^kt0;E6DL;VvAHQ|1A`yDD!xpyLkKlu$lD)OIBSn-ouB0 z58D+4{~?>PHjzv&Xz{? zZp<+!|7jVk(CEJwawx*3b#&s72~ONES9;=w&$ie>j*5vP=6ABx(IIO2`So>$5eGLn z$j~P?US~Si);pl1!K^1K1JW;bYr1?>{J8Ut;~Qf)kg;_C&ZNH;O$jpq{Yk~;s|cO% zg27nHt)}M2mRmDkdY;8Hk-7J=V$k1TF_Q2*G4ywCZ=hphF4b{L@s%x~SrpJreF8j#eEpIS0kJXcTFCA7>;bKX| zun`>>$F&#)wir;X(lIez?>bNfL5=)93okD(Mn*Ic6<$|$Q&u(cadBD<4_bag96aXj zDnY97gq;Z39G2_a@~VQ%)OipLyZ4oWv=qziGgoRhXTPhJ_V<<~P4HU5(!3_UIPaxWFEV{6n1^tc?Br zfGRdOqk;a@Wzw{+Kw-^7XKnIcT`$cW6FqqU@)rIL%T3dmb;L`=2x6bBH%?bzd_(Y` zqF2Rn!6&Sg+uWCzwtr|jI7DXeG)K}P5O%BWcn>%0vtC`xY;WJ5f#Pv?e2iHk>;ukI zdyMem(b2B%VlVxFs9_p~FBMo>+ndVWPwXfrwP7$bHZodTUhauMN|wkrs%H4(MMH_9 zDI$U>A+np-Uwp$n|MH|{|9ubZLSgdxv7UVt&E4S#&*pBn5X!-Km6hEi^W^bsXEQD} zY3xrcvLV}=I!RV4c`Rjd-4acQ9J?K z%$>s4q5`^;KWu=4KSw2V#~~yMY9rsYpI-Py*#PxmHt=|0yEahkRn4n! zM&F#KS+07mO07st`3BYbf?jI)gb0g;wY8sKjMEg8DYOK6?oF8g6Q zZU;#o5D*X?9K1Rs+tpO=u&%nqY4lS+$H%dxyvcw4W;bdWw`}IjS0T=~xj%kz9~yu= z$$8;}qs}DJP2q#wh77qPE262&o5>z1yu3I#2yW|l#d`--M1(`7rJqplGJ(zpKfwg- zCKVfLFnLu}xBxe&KHLnxC#kf4*cS~}+oY1oG~ zN*^56^XSq92WodO7Z8H-%QX9Yb5jS(ys|ROAB+2F$S~ZzC^x_FdpNhc>fhuW_FiAB zA@1GyUMazX{utYz{6(ACvM&|Y)oPr&b#?Teox%3@S=e3UA!NzJ15HG_6#)gv1porA ztUT6!0ifrMx{VBuqKlPy8*nho)E*51RC&nyNpSn_Wj1~J=FHaHX*wSzd$u07#Aht@ z=JrG6B}LNdB=q!?KB#$)j`7rrc-YJ8+S-}7Zk2M|gb?di;ElbK17GgY&>zs9U=(BD zxiV5hq$s<~p&TfuvBCw{)avK@ZI%l|bZ+jbk+sSg~ zY3=Bji*iE)gS%v2SL5tcKaE)4%FP{r`T0}Z*VieY`)c-UbH;AnFiaw_s8Cbk;SBWr zkpp<-2ui!F-_^V$IlK6_ z7Fi_h=cMx!$Hr(;7Bxf~`YfF=_HJ%&z!<$!q{Rh;c3;W|IemL%;Jf=0cq5~ujlt!= zvB5WY9s!~^Se@s1EI<~QxTbeL~)MfI;vO8TMw?Z)Q}9JJPqES;GuE&X~Nz2<&Dim z8H%9b?Vw>leZj=UFIwF$$F{nTA2AtgJPZOxWY}59|nhLP83`KYp9NiTp6e((0livf;5A#=eXEeeN9Tk3qYn zHK=P}o74%qNG({0n|fNUY}1C-hZP+i4{hp=hli%_2BuS}JPf&+c;{N#5_H;7hxQON zk2R{?bN$36?QJaI>&G+y$CH;LD*^vck7*juUEQGJHy3!NxyEq)KZ?jmD2f+|zViNG DB3@ +(Nivesh Dommaraju, 2017/12/04) diff --git a/include/deal.II/lac/sparsity_tools.h b/include/deal.II/lac/sparsity_tools.h index e76d6d4b8c..0a2ee7cc23 100644 --- a/include/deal.II/lac/sparsity_tools.h +++ b/include/deal.II/lac/sparsity_tools.h @@ -71,21 +71,22 @@ namespace SparsityTools * an edge between two nodes in the connection graph. The goal is then to * decompose this graph into groups of nodes so that a minimal number of * edges are cut by the boundaries between node groups. This partitioning is - * done by METIS or ZOLTAN, depending upon which partitioner is chosen in the fourth argument. - * The default is METIS. Note that METIS and ZOLTAN can only partition symmetric sparsity - * patterns, and that of course the sparsity pattern has to be square. We do - * not check for symmetry of the sparsity pattern, since this is an - * expensive operation, but rather leave this as the responsibility of - * caller of this function. + * done by METIS or ZOLTAN, depending upon which partitioner is chosen + * in the fourth argument. The default is METIS. Note that METIS and + * ZOLTAN can only partition symmetric sparsity patterns, and that of + * course the sparsity pattern has to be square. We do not check for + * symmetry of the sparsity pattern, since this is an expensive operation, + * but rather leave this as the responsibility of caller of this function. * * After calling this function, the output array will have values between * zero and @p n_partitions-1 for each node (i.e. row or column of the * matrix). * - * If deal.II was not installed with packages ZOLTAN or METIS, this function will generate an error - * when corresponding partition method is chosen, unless @p n_partitions is one. - * I.e., you can write a program so that it runs in the single-processor single-partition - * case without the packages installed, and only requires them installed when + * If deal.II was not installed with packages ZOLTAN or METIS, this + * function will generate an error when corresponding partition method + * is chosen, unless @p n_partitions is one. I.e., you can write a program + * so that it runs in the single-processor single-partition case without + * the packages installed, and only requires them installed when * multiple partitions are required. * * Note that the sparsity pattern itself is not changed by calling this @@ -103,6 +104,38 @@ namespace SparsityTools const Partitioner partitioner = Partitioner::metis ); + /** + * Using a coloring algorithm provided by ZOLTAN to color nodes whose + * connections are represented using a SparsityPattern object. In effect, + * we view this sparsity pattern as a graph of connections between nodes, + * where each nonzero entry in the @p sparsity_pattern corresponds to + * an edge between two nodes. The goal is to assign each node a color index + * such that no two directly connected nodes have the same color. + * The assigned colors are listed in @p color_indices indexed from one and + * the function returns total number of colors used. Note that this function + * requires that SparsityPattern be symmetric (and hence square) i.e an + * undirected graph representation. We do not check for symmetry of the + * sparsity pattern, since this is an expensive operation, but rather leave + * this as the responsibility of caller of this function. + * + * ZOLTAN coloring algorithm is run in serial by each processor. Hence all + * processors have coloring information of all the nodes. + * + * @image html color_undirected_graph.png + * For example, the above image shows 5 nodes numbered from 0 to 4. + * The connections shown are bidirectional. After coloring, no two connected + * nodes have the same color. + * + * If deal.II was not installed with package ZOLTAN, this function will + * generate an error. + * + * @note The current function is an alternative to + * GraphColoring::make_graph_coloring() which is tailored to graph + * coloring arising in shared-memory parallel assembly of matrices. + */ + unsigned int color_sparsity_pattern (const SparsityPattern &sparsity_pattern, + std::vector &color_indices); + /** * For a given sparsity pattern, compute a re-enumeration of row/column * indices based on the algorithm by Cuthill-McKee. diff --git a/source/lac/sparsity_tools.cc b/source/lac/sparsity_tools.cc index 995cdf7a0b..ea3d33bd0e 100644 --- a/source/lac/sparsity_tools.cc +++ b/source/lac/sparsity_tools.cc @@ -165,8 +165,8 @@ namespace SparsityTools for (unsigned int i=0; i < n_dofs; i++) { - globalID[i] = i; //global ids run from 0 to n_dofs-1 - localID[i] = i; //same as global ids + globalID[i] = i; + localID[i] = i; //Same as global ids. } } @@ -183,7 +183,12 @@ namespace SparsityTools Assert ( numEdges != nullptr , ExcInternalError() ); for (int i=0; irow_length(globalID[i])-1; + { + if ( graph->exists(i,i) ) //Check if diagonal element is present + numEdges[i] = graph->row_length(globalID[i])-1; + else + numEdges[i] = graph->row_length(globalID[i]); + } } @@ -326,6 +331,68 @@ namespace SparsityTools } + unsigned int color_sparsity_pattern (const SparsityPattern &sparsity_pattern, + std::vector &color_indices) + { + // Make sure that ZOLTAN is actually + // installed and detected +#ifndef DEAL_II_TRILINOS_WITH_ZOLTAN + (void)sparsity_pattern; + AssertThrow (false, ExcZOLTANNotInstalled()); + return 0; +#else + //coloring algorithm is run in serial by each processor. + std::unique_ptr zz = std_cxx14::make_unique (MPI_COMM_SELF); + + //Coloring parameters + zz->Set_Param ("COLORING_PROBLEM", "DISTANCE-1"); //Standard coloring + zz->Set_Param ("NUM_GID_ENTRIES", "1"); // 1 entry represents global ID + zz->Set_Param ("NUM_LID_ENTRIES", "1"); // 1 entry represents local ID + zz->Set_Param ("OBJ_WEIGHT_DIM", "0"); // object weights not used + zz->Set_Param ("RECOLORING_NUM_OF_ITERATIONS", "0"); + zz->Set_Param ("DEBUG_LEVEL", "0" ); //level of debug info + + //Zoltan::Color function requires a non-const SparsityPattern object + SparsityPattern graph; + graph.copy_from (sparsity_pattern); + + //Set query functions required by coloring function + zz->Set_Num_Obj_Fn (get_number_of_objects, &graph); + zz->Set_Obj_List_Fn (get_object_list, &graph); + zz->Set_Num_Edges_Multi_Fn (get_num_edges_list, &graph); + zz->Set_Edge_List_Multi_Fn (get_edge_list, &graph); + + //Variables needed by coloring function + int num_gid_entries=1; + const int num_objects = graph.n_rows(); + + //Preallocate input variables. Element type fixed by ZOLTAN. + std::vector global_ids (num_objects); + std::vector color_exp (num_objects); + + //Set ids for which coloring needs to be done + for (int i=0; i < num_objects; i++) + global_ids[i] = i; + + //Call ZOLTAN coloring algorithm + int rc = zz->Color (num_gid_entries, + num_objects, + global_ids.data(), + color_exp.data()); + + //Check for error code + Assert (rc == ZOLTAN_OK , ExcInternalError()); + + //Allocate and assign color + std::copy (color_exp.begin(), color_exp.end(), color_indices.begin()); + + unsigned int n_colors = *(std::max_element (color_indices.begin(), + color_indices.end())); + return n_colors; +#endif + } + + namespace internal { /** -- 2.39.5