From d5a8b20ef4abd7e732263bfc285709b72885d259 Mon Sep 17 00:00:00 2001 From: Kahina <kahina@kahina-VPCEH3K1E.(none)> Date: Sun, 25 Oct 2015 01:30:55 +0200 Subject: [PATCH] MAJ The comparative study --- figures/EA_DK.pdf | Bin 7711 -> 7882 bytes figures/EA_DK.txt | 14 +++++++------- paper.tex | 9 ++++++--- 3 files changed, 13 insertions(+), 10 deletions(-) diff --git a/figures/EA_DK.pdf b/figures/EA_DK.pdf index 5eb980829bce00777b3105f5491fcd948aca0002..69144ae1f91db330922568a4b3aa6209ef35f4f1 100644 GIT binary patch delta 2657 zcma)-d03L!0>;Oju11Y!i{_4{wp>y8;6p(LQ`5$gG}qE_NeC&(LK>~K&u)`Gjiy~m zO|7AE%e`_<=<1l6xsVG*ZnS8GYgDABC|+yqxzC-R``pf7=lPxYyytz-ALnrG+Uzg6 zLi^iU2D{eYmHBu4u>O0e24h!s0|Rx9X!ffiWTIARUoQ~)@iY%8;YF35GaJ8tHLG;= z%_&LJ{FzAp^Q-eCGXJO>vY^M4Qwy#9N#XW4OoilC4R?<qA5l{!z7|mA5V5D|eBlG1 zMDKCb$D1B9iOT!jh9EJMIG9AM6(mf)hEmpN$ODu45p+A-NjksI)}B)q6Dxl@Ix86U zFU<<$_=f$h$CvJ2tyT@IEV%Bzvn@}{J>Yzw*WLm+wMX5&EMz)|rcLPxn&_x9N+Cq( zN+&~0FU{PO2XRIG3HFgVUQX6+T=h9a7Et35CUnP6hO{t#{~m)CP=p#kvq(^iMmQtu zcyu*U`JrwCXS2T|scq<;cxpECw&{xgVoYR8)j4va*}AS?42NXfTlT0Iw!ByK(IcxR zDxa?+D(8!22(Yi!Zei-(xsr5G2eOZ#H>bZ*<H<VMl6z}`;Y6=RRosJuOh$j>9@NM? zm5U^F^3Cb31`xENA#cn5`UKs$&dryy^EY&f@-z8)h7<jW{AK;oSQr26x9R5DKi@iC zaZ+u`PgkYi*!b+;nLe|V*DFtM)w-jxlP&Ing>%vmF}x>3Txs-`U;1eW{aKnq(}&_X z*QDS1D2AQZx@g|-iqGY4>9S9PRH_eM$J{&dFMR`E%MF3}Zi^_-+H#nX@gcW_P5R@N zJld}8fba1*d$aWf2WnF><6uSN%meL0#=bO?`_H6Dy(`jwD5<#6s-5puv%G%#D&uTh zyl>zA5H%@6Gmav3t2szb=?<Mxxrp!!Q{_wwV`?1CGySNlL{I?LXNV<l_h<S4mar+{ zH<c3^x5jw)2dT_-+84K)4wW7He$@5n49RFLyss*?><Z(#MP%IPBPa>@zU2hTeJqvb zSg<d<sh#R8fX*ttz_;FV1E;=3E3WjU*(nU)OwY4+Rf(m05)(3Sct%;7N-BATKUmT7 z0sEzd_m$-m6lqA2st>lb&D@-yG|={E^U?`|$M&w?*lVd*CIarA;@3J0@zO>250ctA z2lF{MM4_99J6q4HqdLFcncHw&a@NmOs_<;qtI?#z{NrI~B6mZ~$M<R%ET+q#(y`%7 z`R|PGy4L4hU9@kQlMYYvYX@2e`0|D6fy#l}frW_RcI|?K^Sl|mp_|$B3UT)0vwA*1 zcJ_6NVsb`4t|_hTsvKyEG2E+8mkkJHH)x#=&k5o)^O5{Tg(N{CubF=%T_qW|5LpgM zroB$<%94jeR_WoDCd}&fC6L!;BSzdBF-ycEP^*FsZ@*s|>@>0>*uF}9F}Pk{_Qx<; zr_Zgi{RnNhpQKTK-jkqxFM3tYDUIP~jXQ0t>7{;kChXqGH2;pZWiC$lo_Xo6T$dW* zchLk)3D9?4lNr3z>xhZYN57XFh~t)*J@@+B#keVY<6zXZC_x8*iv`3==zdr2Tjz}r zKB$Y}s$K)5i?X8FTD5CEGiz09G4%<%dQVKXNTU0)m0J$H%`i<;;P4;OTN4hMMTzg4 z7YW2IUiR~=>%)hm{~1q|M~9pLL?7$CpFE9P)V>Xxo*tBG1qug^vlh~y1SgtUEk1J1 zb$CTEE}LTQYtAcG8bQwyt(g!jO`4IDsz{T{@LHbK`lmTc3*PZVa^tOOf!mzxxLSH; z?M{CeR#TMQ9^;2I937ROcZbg;J>-hshdyC6H?`j?-nvURlJfq?R_ff5g<GmIGh?0c z;nZ3Gax2p2nbl8eod*42{Rz2Rtzb@9vy=~NQ{aWfaaUUeG%$B3iC)G%oC~$g)w#?? zk&VT=#gY_3fWMLzGM|6e#3G5PnC(hV77_bjltA&YV~eX6IBqYMoN3J)aTbNjO)xW$ z#i2Wp?uN~TWQBClhQYcYu4H981u88_Yjobx=wqcgM!(Gf(Mr(|(K{d!vDxP}S3Y`c zl>~7Hx?^#s`R1ty9`RQm{vI}OBh<KdSTE03pS5P4Y+Pw}Yv`szYG5~kt_xT=h7|b{ ztBWCrg{op@<5<fDpgI$(OJYtEse^z(SDGHU!&WC%F{0VHHzoH}&B(ZsN%qpyNCgK2 zM+p~c6Xmu~<KNcBc7({ry_&m)-Wykz?3ja0zQgu8se5a?3Y|I4aAt0W%`tHQn#|N+ ziu``%R_qg|HoM`PUKQ>*53JN%jQJ(`=zNntuQIBE(yn-6#XfRCAOc_Zs9s^cWVt=P zaw4N=qvJ_9+2%v4<;BL(y~k!9d5&!KlsQ@b@e;{)^Y5Bv(ax6sg!kdC9W*2B9f8uy zUq<w_zPQ-~jygJ~v*~9v+PfIB2hyL+nUi-9rCJI`L-$X;PH7(#jT{r<n}c^}h|aqC zZ(DHV9fr1%LGq9Oq>LWl*CP}ZIcX24yseww<I7~{47FW0(teTup^)vHW|UTr&vz}Z z3Rnp5E}zTndGfK=gHv8Gm76xnbYc%z@IfAlr?=R{=xGi@j*hhsrC1s0_|KDgd7+kh z?Q;p0Z5buq8{3+?^UpQ9=+K&uPZ=9%5=?_qisVG0&CGj_r<$HB&Kj&_s>NxVT7wuY z1`NX>4gz5)1PXNsi9jw5#6c_;N5!B+DHtk_qou>N`WE3<cr=r7G!h@pJjS`Lt<7oD z(c9#G;wT*95r$yHeE<*-N8(X<6dI2QI8!=X{`VqsQ|z}z>)zz}ZNeZO_%{hFPwVbp z0enjB5yplCARPHQFbaSJNEEmoW<`piIES*S+nn*A0163!NE8YUa;EfuB?34k{L}Rz z;YZ=H&l99I004hw0Dwk)#gH~gPQ8ICr@&wX1fapCga6wIz<}7V7;fp4`>PI(`<h{Z zuNWGz{wgeBgTXBMX)Rg)rvZqyw&BDZ+L5u&jwl-^%r0;zW)~J?1E4Wja3=t|IHR0! lpyN(wg5CdBkYNM@ERr3{Vn?&6hhWwi00%QO+vVW``#1hW#y0=} delta 2435 zcma)&c~lct8pT~u6cow`5<wuW1vQd|tSpg5PyrFtq7ADF#9#;txU?El4T>THLy$FW zibFv}))X5^#2`Tt(6R*sQVj@5*u$1}v{UDtsWWGMf4y_R-}~;p@3~`vL#hYuSR2KN zuQNFGFe{LtmMxK0C55_bn%}%oFKJ1Q(p`Uta1+XuQ_DUub2!C1Sr+;Zhhxgv6N9{9 zRwW-aW~<^{td}pyIE}Q1=1Rr6XEK2@Zlh4>*-2`<OV-YGx?iN73HAF&rDUtMW4uZ^ zcXM|kS3W-#Dw7`UHO6@fX@gi>!EVaEshITYk?PFJskd|PDRVu8T-%{Hfyz*JFXC)p z#^y8r8$1hc_=P2BJv-uN72gtnBpW8nNo<XOnU!h~qxHJHHQUNA*VHkH9Hn=Wn0EGl zeXp1r5t+oh1#UI6Vexz^;<RfudKkkKm8QsZ4@O^W<ZXrsQVrQnw7e6)IuntYBS|Il zk>1Qlqq?ze9Ab`1{_CMpl5ena34j<M&~KCO#&WK<K_Et2lH2<bW8~{i*9HVOXJ1FX z?EfZLk<NXhto_C8XxcjgTd3+@UE17bag_sVMp+EEQ0nY)MKz}D4Wsc(XDS|i<msCq zRjD)YYXOiQMzORC%&NIed!VOusn-o69*=!|SbI2iz>5CnqzfkU&VZoQgSaym(H!DR z5j*7myFzKZeZC9PH7Q?xrOh$5Sj}bp4q%DpF!N&FSnZVq<DFV-cLw>NKPx`7$vbGe z+NZ%7KkH7ZY~Io4nizP4@oXN|ukj3F)BiYxcFMyPXWDONX$TM_%4+n|BK@i_H%-k4 zd=^c;s{a)8CkZ<(gvErlhPa%Zf@Yu~^@_I_t2nD>omp!t1~+?(x1Bg}*t_#d!#idK zYUya};hc2Y8c}*9lYEtsn@$d?B#Jw}+sE4fY(0XN{@6nJX#>rB6YGU0@n4JSdCyO? zT&lefAi#p(jF=Bn$&9qkUW)<ZM}qllj{5BGt^-%E!-@%pagodsIoqpj^i0s@j=SnZ z$4pa5ew0mQ{w@gS)7t8u)pSs!@N>zDa<k8Maysh%tV209$?B!hkf(mhtrI4Fiz}=- z`hm;~S=!n+xJbyAkX1LSF<ZX7z6ZN)>vq_~2HU!Z^NqIUdxBNlUr&ec-T33&%dW+h z2>sIvg%Z>>isd9vgwtLH;xkHh!@P(|qZ71>={QBSYFxB9qI@f@SIoRuiWZl7{y)aY z6z|8p-_f3vAYbXCC8*-$lG7?t0@jg&4IH9zf^G-31=ZXdukM_jDrw7&Qn3{0R3pJc zQ71Mou7Tn?JzIMS>s=kNOel<RT<C8(#5<6Ii_9?5#1%Yd>Ne(6Ek9h_^++H#NEPZj zgwG~k-?AkBrZy&#o+Yz^)zGuDPR;Ggd>`7E6tHgI_yG;gG>EmlrIzqEJJ+D%`=b>Z z(OYih->uFVXO(4^-M&j&FN!7EliqoH#(>&MLpu<^x!Bth{<aixe4WTuIFe0|R?FLP zDVNQ;eEv>xGUwH|RL`iV8et9@fB<{-<NJfMT^AH&X`<3`fM;`f$e0}v6Bry2A#I-u zduKmpZk0guxHmI%fjQzprRYfwP(Ro*_!1pH&pcZpms*>j&!g?zT&k?qF5OkrD$$YA zU+J$c>?HiG=q^a(G@3a}8ZSLB{;(1a#`{fld#tG&mRg38Ja<r2?q%Z>h{vtF`66aX zT=_O>4`nDV{^i3P(u{00o8#0QE9Dj^Dd0bt&}!o<vC%6tWG#t_F%G5hAATMwl^;vD zAxc|SbiG49sv=;9>HuXXn69$GdT}4A$|E8)E28#V1h-WL`^Cpqrqmf2O4f3?$4UJP zVu~Y3wIA(lGK8snEC0Ej-qW8W(|-DWri$R))whP#bixDgXi`2FG)S|a`Bm;u;?lM@ za!M3qtJT?irt`5UHK-##t|!ZV$7Y;Q3Xodol6@8OlNMolT)p8GgnmzFtBE9s$Mz0a z^y9VAyA@7Fo!J6S$qLrwoV9MLHvcEHr?OT>i6S#hZ7Rxfa;9RdW85Numl$jt&V@Vm z*oI?ezgIcwlt!gMK&pj<RL(T5d)m05kU_d27ei9?xL00EUzBbD@jKdEsk7%p^wr0f zla&usqc}1Vsa|^{`S0*Wuqyz%{KWX4e`~vxnP^i{n)ME?hi6R_C&Z=6^Hw=IR8JiL z_Nsim@9Bjq>*QObx4|v%@sJWh@7Rrv=(*nw%{(Xx+S+fs_{N>H3|d4!Qp7J?>0hp* zKb&>7N5vHfvYj^JWU^%lzHhl`G682o;ipWlkmXtQ-sK{$*3z*tq{u_kDVd+e9}E;F zI4#b?*qOG>H@(Zl%T;^IXL<Ff<ylV*u*aFoOY&ngz00Ay&~a`}3pxXa)MOLQWdkfx z?rU4+Xk$X^;Og%*u`0>*Neps|QmMig8wpC)D)U<xml!g2gS9BIT@7HvPudn?VPQxx z0SN(}fP_Lo5J)%}1patHZ~_vICfFgs=ujx5K|k{AKyQFOz&)A-1o_}WvA`ox7zPNz z*kRys3<k_71epKtp%6g*I*Uu&T)qz62mpQ+SYu_dZ_SoZseSOVKqw3d`6DnC%(%RL z+j<zp4i2|t6mCz{hd|K4Pk#djQh*wNT);>$9KxU)S*StKU^IhdWI=<VP+w3`2+HoS zFQHHr{0j|<_)>#H|BD9yLW6<PpL{L<BOVlig#Fb74hJI{5Mzfx_(v4tj<$1kb3wtu zC_5y~%?%BMxx@CtT@i417bl1RO9W~-IcdbihDOI;hz<+aKtkat4NJ?tKJFU-1m;j@ AS^xk5 diff --git a/figures/EA_DK.txt b/figures/EA_DK.txt index dca073f..d3939a5 100644 --- a/figures/EA_DK.txt +++ b/figures/EA_DK.txt @@ -10,7 +10,7 @@ 300000 138.94 21 1089.61 27 350000 159.65 18 1746.53 22 400000 258.91 22 3112 20 -450000 339.47 23 +450000 339.47 23 500000 419.78 23 550000 415.94 19 600000 549.70 21 @@ -35,12 +35,12 @@ 250000 1958.24 348 11.33 18 300000 2800.53 319 20.47 21 350000 4071.47 378 35.07 26 -400000 -450000 -500000 -550000 -600000 -650000 +400000 3339.4 238 +450000 3983.34 221 +500000 5737.84 257 +550000 6783.73 235 +600000 12339 398 +650000 700000 750000 800000 diff --git a/paper.tex b/paper.tex index 5bef5e8..35896ae 100644 --- a/paper.tex +++ b/paper.tex @@ -334,7 +334,6 @@ Q(z_{k})=\exp\left( \ln (p(z_{k}))-\ln(p(z_{k}^{'}))+\ln \left( \end{equation} This solution is applied when the root except the circle unit, represented by the radius $R$ evaluated as: - $$R = \exp( \log(DBL\_MAX) / (2*n) )$$ where $DBL\_MAX$ stands for the maximum representable double value. \section{The implementation of simultaneous methods in a parallel computer} @@ -493,7 +492,7 @@ There exists two ways to execute the iterative function that we call a Jacobi on H(i,z^{k+1})=\frac{p(z^{(k)}_{i})}{p'(z^{(k)}_{i})-p(z^{(k)}_{i})\sum^{n}_{j=1 j\neq i}\frac{1}{z^{(k)}_{i}-z^{(k)}_{j}}}, i=1,...,n. \end{equation} -With the the Gauss-seidel iteration, we have: +With the Gauss-seidel iteration, we have: \begin{equation} \label{eq:Aberth-H-GS} H(i,z^{k+1})=\frac{p(z^{(k)}_{i})}{p'(z^{(k)}_{i})-p(z^{(k)}_{i})(\sum^{i-1}_{j=1}\frac{1}{z^{(k)}_{i}-z^{(k+1)}_{j}}+\sum^{n}_{j=i+1}\frac{1}{z^{(k)}_{i}-z^{(k)}_{j}})}, i=1,...,n. @@ -622,7 +621,11 @@ E5620@2.40GHz and a GPU K40 (with 6 Go of ram). \subsection{Comparative study} -We initially carried out the convergence of Aberth algorithm with various sizes of polynomial, in second we evaluate the influence of the size of the threads per block.... +In this section, we discuss the performance Ehrlish-Aberth method of root finding polynomials implemented on CPUs and on GPUs. + +We performed a set of experiments on the sequential and the parallel algorithms, for both sparse and full polynomials and different sizes. We took into account the execution time,the polynomial size and the number of threads per block performed by sum or each experiment on CPUs and on GPUs. + +All experimental results obtained from the simulations are made in double precision data, for a convergence tolerance of the methods set to $10^{-7}$. Since we were more interested in the comparison of the performance behaviors of Ehrlish-Aberth and Durand-Kerner methods on CPUs versus on GPUs. \subsubsection{Aberth algorithm on CPU and GPU} -- 2.39.5