From 0f0f3e13155ce0a172b0325568594615b632eb61 Mon Sep 17 00:00:00 2001 From: Kahina Date: Tue, 27 Oct 2015 09:57:18 +0100 Subject: [PATCH 1/1] Ajout de la figure Spare and full polynomial with or no Log.exp --- figures/sparse_full_explog.pdf | Bin 0 -> 8424 bytes figures/sparse_full_explog.plot | 21 ++++++++++++ figures/sparse_full_explog.txt | 59 ++++++++++++++++++++++++++++++++ paper.tex | 14 ++++---- 4 files changed, 87 insertions(+), 7 deletions(-) create mode 100644 figures/sparse_full_explog.pdf create mode 100644 figures/sparse_full_explog.plot create mode 100644 figures/sparse_full_explog.txt diff --git a/figures/sparse_full_explog.pdf b/figures/sparse_full_explog.pdf new file mode 100644 index 0000000000000000000000000000000000000000..7100f34a697742e4821ca5dbf7c1c527e472237b GIT binary patch literal 8424 zcmb_ic|4Tu*KZ}$LW?}4x?3zI?pchn?>yOsEXguv2E#1OV#}IDNuEd|ktj=9Qj#Sq zQIbg6vn6EDl6`sa8C1`&=Y8MbAJ5FkXRiBP=X}q(&NsK~N{)sCa^+B8<+U5wK*KM_h(Q z<>kG3+gsbSzFLts^nF`s92q z^ObUw(4_Bw%ny7BA6qk1TGG}|_A3ymrrh9ese854x;O9YRGU$=UGoPwru(es-LauM zB?G@=*#)ciSe@v+YpEgBAVl3hM_&8!E4nK97pc1DK}|^t#ym0bqdQFrljZ2m$h!i} zs_cDP*3^9iLs)rCcul`oLT3G(eW>AUOzr*1B&(()lDN&1Qg3ZbGY8{(A8r)bW1o#R zb5oIiRm&?-2)~6JeN^K6J#7Rb?MY}o6g?83Su&Y_yWpTcs%KMScA!oGDG2}JKB+ls zC{)2R@d1`&j~gM_FyA+*{Jcej!Q7tu{gV-zQ5)JPod)~_{QsIi9ie^Up8)-n8S%O9t?)(mEGD+~77=(9?atKl=24=6v+AImv6aEM2f>xoHlQhVjaXAgOliJaPL ziZ`~Hjy^6B^Q}IhrGMj%qQ2ZnM3)$^aKft(*fO09fz4{yNdfqKQ6$@JoKyMkQHjZEBi@0D*_Zx@b5KkmpI&H*U~849i4xmC}3sw?V2YSI>^2ylGjPt(k*d z3VUU`Zt$bSjuT{YwRA)zIOlQmq(p!?i>M2h$W6YSj%Puy1EM!cFskvWz z6+whLyNs~KZStD>vM#)VkiO1^4~K;G!>>w5#oU5bNQkLic%FHnO0L2mf3NN`xeVVR zvooMP(^>eLty00rrk9#ZM6O2Nq6cCUu35FbnPG}cZBcxCRcJo=pnKRkTD|kN`I$wz zv*6M~tq?dDSXB4w{h8_amoy}?y*BSg{ARuAOT;-Zy1Q?q?{rVkhskfHdB`Bof{(?~ zt_?Y%&7(7|(ZS=B!ykf&x(xF2T6*VN{Co;Z3O(KD3WJAAXJ#vB=7GhGK^bjM-rBaj zd)y!BG9v*q>z^(oc~cn>0s0NE}4-tNUre%oI6uT`<=#6!-f^w&C%&`Z5)|gatjH6C7#3hva4 zK5uL^?x9g48MnR&_jLMOEVHWkTqyU*mC}XUbmKQp`wG2@(?e-W+|}<7ZN$`;wQQXr zNG*Dgf8P&|yAC=EVya!I+~$ryK|Z4OV84lR2ikb1^6B(obL7>v4{|qbAG8_`AFHX7 z7qq~P^O)`IIY9fv)4cGA-?sy?nZd3GJLKay>pz*+ZAeJA z$EMLlpB&r$RLzSzD@Sqdx16~6WCFuTiHq$n4y0<_PD*t5CSU2QiSoQ77<(=EGEeR; zu4>`z*&@z88vKa+o+RuuaBm&_(0l#~*9y^C_bjr zBu$JL^f@tCa3#ZZ+RoA$-fnSA{oqc&9J_K`Opt2pp9s(}+_wyknE z-`DVjr}|44ore;WTVCA0ZWBx}m-O3YW4>s-E_RmtfSKQyFIbBhfrSItj_5C?ZQr}s z;@RAlSHXmwhaG*@{iYLlL-3bGZVJ$svIoQC7iS*^As6%r$;z4mvd6-{kF_kEa6NRU zvwGcq6g@&LR_4@IWIUQ_p2T@i@{79PE^_||rNh%Y2f|1H=nOAVyq|M(rpv)*@jY|e z;k!W~e-80E)`=&^Z(3&fZDq;V`gGgZ9`7^m_zKIFpcKgll3Ah#V+~n_t5JXl<5mKk4ry_pPHX=*ed4B zpO&#sbn!U3zf(oySlMUJfVX14`F%+zC0&(Ml_V!_U92aK2B!A#mYkh6ON_GL_1&OV zA+@OPWw2_|M+e>Oi$|5xglAixq%$j}{6gGMjf2uHCu?%~O=oTw@4x%)!S#|)rB-q2 zavS7dBq+F1zx9^v`eyRFZT?P^TiUTD|LMx-0h0oYH@^o*zHC|SGZ?8~JfSp^eZ}=F zXLUTz2a3Z?U+F~~4dTFBp)S!OPwTMx9l>^UDN4Cz+4H$l99vb(>vR6}`1qovz=wb4 z`}mgr(bvrgE!edO7+jA>GPQo1kwyTZ2A?6ddN*z01W>{-vA1@4|A2W_(kF(V^9a#glW3dBdF>QTW6S1hEh90l$bDlZ+yfAX!WJXz(dqZTJ_p6#onckSHwEkD8QV-hs!Drujcbn0} zy<-OWi}#LHO+*c)H+eJ1$HoXkuYKQ$>Z=V72P|X|X5Ub*CkO>y&)rQeHaxA1s(S?;1yYYu2V)lxG~zRiy7(c*D^s ztCEWzXEk;`huL&|wxEC%Pdl~go=!Y7@s-in&Wa=5FG8WC=|;+~$~lj*ktMKL#ftm+ zG-fD+(n_Gp%eY2zVk^mFfXl!l7w2 zToOP@!L4A>B#l5}04P==2m_4>bSjgEBhaA|(U3;P8504>!)ta-vNFu0|pux z>H!Ev#T6sjt6EWIgn_Z-jDEtfm$^DC4U_)+EbDP)QWZ-lup9%b8=9HupAb7vAh{73 zL>!jwE_DJOMv)w0hy55qd{XQ+{z}0hk-#dCloZP& z|M-SbmeJAhxm-~(f~#Z31B14Ag@1o`_SSIFJZXP(Wh_fouxxJ_tgO zNT);oVP^@;i!ji91qO|hfl#58f_Aegs0r$W#vm5Nfq0Mr+Jg?DBS-{EAQ_~9RFFy` zfG(g5>rfyO>>0}=wj)3n$RSib=t5%BfAJ4U1L+{0=mFAQus8z90GXgW=mC0yUIZHT z2-_)8dr3e62v+oe-AkxbLs&c`A34`C$%6L(fyGj@w`0wAOWRy_nnV^qrHekaH?s`0TnntxnD- z?wOx(@=-x#oVq=x{qk;od`@nwoQ&V6R;9+_t~eQbPeT6GyMsiRnLX z7N0hYO^E7KOq)I;sl*gi((})LpZ~!^C{B|&)t=xlzwz~lB-ehAs6U21)B^cT6xFyK z3vx2CMC^%^uD%rOv|3QeHEJnNCVi=x>(nF1D>SRR1e>ex3nJ!EC((9$iZ=9Z4&5S) zBVMN+c~Czv{_tx4Z2Ik@9Rz!~#}X|=*J9HectxYT2gXA$!YZSDbrzzY2L!0lE69su z-lYXOI|xR1AE>9D6z->0PQ;WgO-0-mz4IVD)x$!IXrW2F zSliZY*1mX3B_nx9>ftxh+INjoP5OC{Uer#iO>@-N+h|xRx|LV0%*fS5l-EE!MY{ip zlYF<9=ZUtf*CS3yqHmg9u?v}Td!s4#^^aNUg@Gsjt^?%@#ym&O!6#ojd#`+PeG|x6 z4=W7fj?uOk8TbEgk88v<3Qy99k5IPdC7@LHjPZ=#?4c?4o^Pz>Lu``c#P0|W!srP3 zNQ?uI9xi>&*)sLWf!IB5v%V-Iw~Sd8p(EHSTJ_iVvL=hqR?V;O&3;Xi`ud2g1MX*X z(I?QM!%>i&uy(OSZfwu7fX13XJucstQk}(_ZSdW8M(7;pTb;r6Tp=Ynvb%->Q{TrY zz1wcSh?a^;9+8*Q=Iq==N8U+F=5vL2@2lbAct4I6G!;F3+3~9RUwf-tFWV-b5?ko3 z4Q zQ_%%J!Ed_v>}jJkdR^L#b?fAM$^{PtZb~;QI9Z)}(VKm6@K(?It^*8GZOl&c({@3$ za6^Sgjj2~)LaUhX{sXa1Ar$HLv4)JSd)jg^FZ)JY(-WM+ zXIlGxrMqk7<;&~0wwWIo-sf+%UWc+hb7rjfa8i-y0maIrkslKu#JtLST9Ddf_si#({!rL8UG@r zK^1tM^_e54wLy`bdvMtF3^w-mB@NH+J$88=qkGaH^O8$g<52rGMag^@QKjiV%1#UUe&5pW_2R>WkHhkgo@lp zX^ovrACTl^8a(J{CZ>+8t+YLu=wywOS zd0Kf)+=Bz(n=vIW(x6eN6cdj}W#y`#)AD}F(aT|7a3s=X+%k?MEg5%!VmBrmdFtcg z;g7buUGV#lu>yC+4%f9OKCDV9$R}VdPFFeX=(>{i;x(XmeA8wwb6-Anpul^o*zS^t z!=np}ZSN|F*7f3dU|x3Ho^C5rlOA~R{9Oyb@7YR;`7r*-^&x#hHHxFIZ5_4Tk%^rH z*rZ*po^x-{SC0jkzMF|ux33af6Wt*+l@bVgY@1kz6JDbeo$)SACCyRKxU=FScl)f% zE1Aqpvx2$K1~bm>4Spw4esaylIJua9sTXl~`R;z=*$>cp5FPPvOLoYr&czt$aw@hy z-8m#JTJp|xxY@)q>`BO_T%BFdox;j;z5H#+bc3~0r=GRwDaUJlatf^GJT!-oXz>Ov zY_HJXXIAC_A|Bo*Myb)h#(fwroC@{3d+sdcWf?^zojp!k)%VAHd{*ri z78r7Dq+?3k-9LP3jkWG^uJ4xTL^u-kXVc8rKFERzP5FuvtF_`T? z?kWwQ_4I2JMlnr6!{nZneS35L{fDv7PxAnKX6qTVj;|cZtzVA{X!VaemxJ!QhrK?T z)YPJ9?A>2gKVzn(J6#CjRq9Kzj!3=u?DV(Bj(6XBmIf0KP6aOmjrU%1^l)@Ge-Ek$d54{Nmr`w~Nk`EXy8ipaQZIZev5&cEOyA*fW z(C^D=J${BB(@8*)$f|lL+D!FdS$j=&fi-(6SFdlC`=C1!R=BQFo#g#MH?)gqo2vBm z(aUoiE1zuE-87wCYPTVAld3H6X&dT^(kI(KtAO>rT7GMrPKK!QoCC}^yA}go5&UwK zeSk)J;-=u_u5UcLpQa1{vQJEGJJ`|k>~NXIUw6taq;Jv#i#fnUPJq_ik8M$M*a6%trqd zQ+o4*GHg&~{o3*DC`C_h{Y#ssGtR|2bsWsX!GaFuN*EWqS!{eRqA}gK{>o6Z!OpC& z8N+o8-}nrly#zR~rACID_U+33X4GJi^c5z1Wuf@|Aup7T?8kf~-lBuUWg4STr-q^> zT0Ws9j*`Dr35Q^ad-w;Y6H_uqyu7vzjm9aTSmLlWTc69Sr~lq*vU{pu%iq;*>u0HE zuBW?Nry(SzFhA-vc_k01ICLg306T&Mk)j|nQdlAa5b+8kW@tUQo{Jj6k$BvTMlkl$ zH^F&1<7Dt6N{TRfB`nn962v{QF5>p=UnuARR0}H{R5Q}mJji13ko6$DkfEjz@F0^Y zbXgAt5w?gdG-i=O5rECYa8?j8*E0kdR4U1t$N-QMG7<=J1nL-IPlF0}cPh;pKuAc5 zK#(-Ny{r+`?=AyEPYNQA42Fv=2)etwOSq#Xs5A!*B+tcN&- zehAXXHiT&YLySU~VA~{tqmn_QIf#&egR6>Gn+GD50c0^Eh4U9tD$N8+1Vsl5(}hH30Fn}t zfD4v^b0iVm2qXZxtd%Xg!YL23qVtP${zZ3TUG((+Z-}{q(Vk{3xMAo*EC1EKJ3L+ljc!E8aNn(g7iXK^ZJc+2dJYY+JKT)6& zj+F~k+A@$a!F3f;(HZMVq+tI8fX%=H_#p<3@hi76ke$E7tR@L7Q~o!wzXAM1s<27W zp#o(M_~Xb@gaQB3>)!+Vc}_#8zk-N6>lFU&d*GM0ef3lk{ij3a2z2Mb3J&B})>ai| z?Q#PgbofFyNbC)cfUbw&2sFe8ods+bby*ex0Y_rsGH6Mpj2Lt@!QmpSNK~5WYB>IL z&q6FFtjrRH2GGTU69LEg!OIFAL{?!k93h0|yg2gX!q0<7u!pX$5NH_dj9q>KQfM>^ z4cG%KG$cj}y0~J!0Lm&2gOP$R+Wt<1?1pYC|AU4`|0WBER{1+0>Nh^5H1c;o8661XjKhqI0mjJsSZcLQE*L7 ewBrBIVa2);rZccK20LgN84Lm@B&1=W3Hu)+thnI- literal 0 HcmV?d00001 diff --git a/figures/sparse_full_explog.plot b/figures/sparse_full_explog.plot new file mode 100644 index 0000000..72242e8 --- /dev/null +++ b/figures/sparse_full_explog.plot @@ -0,0 +1,21 @@ +# Analysis description +set encoding iso_8859_1 +set terminal x11 +set size 1,0.5 +set term postscript enhanced portrait "Helvetica" 12 + +set ylabel "execution times (in s)" +set xlabel "Sparse and full polynomial's degrees" +set logscale x +set logscale y + +#set key on outside left bmargin +set style line 1 lc rgb '#0060ad' lt 1 lw 2 pt 1 ps 1.5 # --- blue +set style line 2 lc rgb '#dd181f' lt 1 lw 2 pt 5 ps 1.5 # --- red + + plot'log_exp_Sparse.txt' index 0 using 1:4 t "Sparse polynomial No log.exp" with linespoints ls 2,\ + 'log_exp_Sparse.txt' index 0 using 1:2 t "Sparse polynomial with log.exp" with linespoints ls 1,\ + 'log_exp_Sparse.txt' index 1 using 1:2 t "Sparse polynomial with log.exp" with linespoints ls 1,\ +'log_exp.txt' index 0 using 1:4 t "Full polynomial No log.exp" with linespoints ls 2,\ + 'log_exp.txt' index 0 using 1:2 t "Full polynomial with log.exp" with linespoints ls 1,\ + 'log_exp.txt'index 1 using 1:2 t "Full polynomail withlog.exp" with linespoints ls 1 \ No newline at end of file diff --git a/figures/sparse_full_explog.txt b/figures/sparse_full_explog.txt new file mode 100644 index 0000000..065de24 --- /dev/null +++ b/figures/sparse_full_explog.txt @@ -0,0 +1,59 @@ +#sparse polynomial +# First data block (index 0) +#EA With_log_exp No_log_exp +#Taille_Poly times nb iter times nb iter +5000 0.289431 17 0.256983 15 +10000 0.319229 14 0.317802 14 +15000 0.317802 14 0.393191 13 +25000 0.759156 11 0.849403 11 +30000 1.26306 16 2.08251 20 +40000 2.57116 19 2.58756 18 +50000 4.17865 18 4.80419 20 +60000 4.43633 16 4.92617 17 +100000 11.7038 15 12.4761 16 +150000 18.6746 11 16.3098 16 + +# Second index block (index 1) +#Taille_Poly times nb iter +150000 18.6746 11 +200000 67.6199 22 +300000 132.27 20 +350000 159.65 18 +400000 258.91 22 +450000 339.47 23 +500000 419.78 23 +550000 415.94 19 +600000 549.70 21 +650000 612.12 20 +700000 864.21 24 +750000 940.87 23 +800000 1247.16 26 +850000 1702.12 32 +900000 1803.17 30 +950000 2280.07 34 +1000000 2400.51 30 + +#Full polynomial +# First data block (index 2) +#EA With_log_exp No_log_exp +#Taille_Poly times nb iter times nb iter +500 0.224633 16 0.23799 17 +1000 0.348493 24 0.36104 24 +1500 0.337472 21 0.339825 20 +2000 0.36503 21 0.389243 21 +2500 0.389436 22 0.438976 27 +3000 0.404811 20 0.403387 27 +3500 0.487981 21 0.490296 22 +4000 0.506183 23 0.550917 20 + +# Second index block (index 3) +#EA With_log_exp +#Taille_Poly times nb iter +4000 0.506183 23 +#4500 0.946749 23 +5000 0.769945 33 +6000 1.38447 48 +10000 2.15026 32 +100000 306.117 141 + + diff --git a/paper.tex b/paper.tex index c12aeda..1ba7a17 100644 --- a/paper.tex +++ b/paper.tex @@ -662,7 +662,7 @@ The figure 2 show that, the best execution time for both sparse and full polynom In this experiment we report the performance of log.exp solution describe in ~\ref{sec2} to compute very high degrees polynomials. \begin{figure}[H] \centering - \includegraphics[width=0.8\textwidth]{figures/log_exp} + \includegraphics[width=0.8\textwidth]{figures/sparse_full_explog} \caption{The impact of exp-log solution to compute very high degrees of polynomial.} \label{fig:01} \end{figure} @@ -672,12 +672,12 @@ The figure 3, show a comparison between the execution time of the Ehrlich-Aberth in fact, when the modulus of the roots are up than \textit{R} given in ~\ref{R},this exceed the limited number in the mantissa of floating points representations and can not compute the iterative function given in ~\ref{eq:Aberth-H-GS} to obtain the root solution, who justify the divergence of the classical Ehrlich-Aberth algorithm. However, applying log.exp solution given in ~\ref{sec2} took into account the limit of floating using the iterative function in(Eq.~\ref{Log_H1},Eq.~\ref{Log_H2}and allows to solve a very large polynomials degrees . -\begin{figure}[H] -\centering - \includegraphics[width=0.8\textwidth]{figures/log_exp_Sparse} -\caption{The impact of exp-log solution to compute very high degrees of polynomial.} -\label{fig:01} -\end{figure} +%\begin{figure}[H] +\%centering + %\includegraphics[width=0.8\textwidth]{figures/log_exp_Sparse} +%\caption{The impact of exp-log solution to compute very high degrees of polynomial.} +%\label{fig:01} +%\end{figure} %we report the performances of the exp.log for the Ehrlich-Aberth algorithm for solving very high degree of polynomial. -- 2.39.5