From 6f76482b569516829ba1ec3f0358dec6c479c001 Mon Sep 17 00:00:00 2001 From: Kahina Date: Thu, 22 Oct 2015 18:04:54 +0200 Subject: [PATCH] MAJ des figures --- figures/Compar_EA_algorithm_CPU_GPU.txt | 16 +- figures/log_exp.pdf | Bin 0 -> 7246 bytes figures/log_exp.plot | 18 + figures/log_exp.txt | 21 + mybibfile.bib | 816 ++++++++++++------------ paper.tex | 27 +- 6 files changed, 468 insertions(+), 430 deletions(-) create mode 100644 figures/log_exp.pdf create mode 100644 figures/log_exp.plot create mode 100644 figures/log_exp.txt diff --git a/figures/Compar_EA_algorithm_CPU_GPU.txt b/figures/Compar_EA_algorithm_CPU_GPU.txt index 1d6d23b..b2bf4a3 100644 --- a/figures/Compar_EA_algorithm_CPU_GPU.txt +++ b/figures/Compar_EA_algorithm_CPU_GPU.txt @@ -1,12 +1,12 @@ -# Polynome +# Polynome with 256 threads per block en GPU # First data block (index 0) -#Polynomial's degrees times_CPU nb iter times_GPU nb iter -100000 621.59 11 12.45 16 -150000 1405.87 11 28.67 17 -250000 5671.29 16 93.76 20 -300000 5635 11 138.94 21 -350000 8366.34 12 159.654 18 -400000 15458.3 16 258.94 22 +#Polynomial's degrees times_CPU nb iter times_GPU nb iter Speed up +100000 621.59 11 12.45 16 49.20 +150000 1405.87 11 28.67 17 49.03 +250000 5671.29 16 93.76 20 60.48 +300000 5635 11 138.94 21 40.55 +350000 8366.34 12 159.654 18 52.40 +400000 15458.3 16 258.94 22 59.91 # Second index block (index 1) diff --git a/figures/log_exp.pdf b/figures/log_exp.pdf new file mode 100644 index 0000000000000000000000000000000000000000..2ccdbf64daaa02dafa56ce8fb28be75e4526a33d GIT binary patch literal 7246 zcmb_>c_5Ts^ncr%nqFx`S@M*G7|$%m7%{T%$u4Wtc#L5-GmmVcwCHWIW~UM@k~WmB zRNA$QkWjrXL?NjZ^}ElY)cgLv-|rvqEapDvp7Xiqo^$TK=N>9+OwI8`Ep432^`3-- zI0{67`0E34`ueaf!egNUkPe_Y!scuaiU=XtoWnp7Q-sO)L+Esz2o)j>E-ox5HN%Fl zK%KL-_p8P$nXid6I}(C6T{$vshnt1(6i?R$0r=K4jMp7;-i>xAG?$!)E_!+nm%p%W zN>qqxe)5j08uMl73;MYWX*=<5c01R1b}+w{FLCa??%wBTo9j2|HO$H5%`Pm|S9EOr zm|Yv(=N2dRe(L)pN+<1G@5%msuJu*zhW?KipAC1GG^N$cJluD7*TZL-wl9aScEtH= z&5l{u@O)t50aWTxe!Xp(M98+|E$ZslR#{LNuEo*8ac{D=QN8pTiIW9tD(u*TS!e!G zjw8)mZdGm^A)9|N@zya(_o(_ZyNDZBwXSmXfZn19OZObM%c6HFlolkW+`Y8(*th;F zjVyDs$cu!?bymHy4cB#G-vUYNY^MS#y|3XzqwJl}Q^o}!sT#Z}U}#7xeYllwI4i@@ zCc}5`z@4>1XcRZoGDgNKCe5nGxXZIHg%|z+4_CG@pG68>{gTWd`X_Z6=G|a?y2P-= zpRRKIn-F-AytRSYc0=$;Bi6M79aL3 zmiVK=U6M}ks+aZta&Xs6)#IG)CE`!&oi)N7G=A6J;0LtTm6T%QivrIQxuWkQl=yIa zwq{peL6qxIHYwDQzsXWQO-I#A>1$lwhN%!&B2UsI>V7nxmuUWVu)I)8Z(8KCvB@kd z50k+@dE{1HL*|dRr2AAORMB^AIap?ySzBFWN2Mpua?_>|5~ST zEyCMok>ZGte`aq}W_I<_y>CV;`jR6z)@RV(5|@P^<2D)E%bX?8o|$>7_TkF|#~kbp z-vpLg9(uOI&Q5QTGuEm!tqL2ZRUWq5<)%Whp53@#7)R8)OS!SS@?Dq%7j;vTsAOhi>hqIIoH zRu&qxp$bafUZhRw?5u8^WLb||6)k^jLh%@dSB$+Q@5nBcG9RK!D&mx(=7g=>naCg;JKWnUFBWMLdUL3S4JaCUWuJ_ zeBk_^So!+--TJR;WPL9b57g!^-D4Kq^FldX3GUZZi-CQQe*XL&jw3xzARSL&+Pwc8 znm4pOcxdqb;A{J)bG>Knn~u~~y=^S%4sC5KdQI9^vA^PsYKsJ#Rug@pqNTl~eR$yA zM|9-%9jVaP?7E_a^z_h9=i&BilaU_t$PTS`g?%H@Rc%jvxaqzf_qv6V@?S-AQ+rOV zYzj>xx{eEZN;yK#4wQcyZ>k7~gNTEIQ8X*I$nkA+FEH?-z>RtU(l7jAo9Nu8w- zMv)DE6&vZJRMQoe)0z>Ayt9q2_Gk|5P4U!--4fHVmi8pd;8BBv`tbW;vlRoH&PAnr zZ-4K*ggDD|XsvMR4%(d3z4y_+L)+Y<8oF0Ma=WmnJ2wg+uNZYbO9fwTXVHGtBkSW; zu14_3##6U)6^dIVc6W#CU(0P&*#CikPW!9J-ry@r{8brqX9YJn>SmKK3{qIL^n9Gn zPqk3Ha}I4N_Ita_I(}Q@mp9D&Nm)s((o+o(QG% zpriFZ4u9Tx>yRQ}B4fKHhjsPZO6kMf1vZhj4cgrnHdT90_9h1nJ8Q_!jq7(RDvuf% zvTU)E&`_w^?ov@Uqkr=~&0PAx^~mpkeOb4qTCV6uP07_&-3ZTb?34j5>}0~uBkY%` zL(;{K(X@Y_TF&7D1YW~nA+R0d$7UGw!yr!r=%x^~A+ip^8wWat2oHtG*tv#-9T5>f zM94%$;KW-aLD(1maC^``K9jE@wFK!}D zM?AlY6e@`X5q{yB*gMt+{iCB$2&1jBr?JsV7zTJ_zq&xrF|EYf5yV&8}G~%&12yh7Ogd$v5 zu<8JW9a|&<_7O)1W))?wgX6v5i&%? z96oW`V9#R~98H}kX3k(X6Mbqjo@$c_6bhaGBdK6ppc$cik_sHkx*I&h%MGV2zoohlEtJ7AWPSmt+$g190?BTZHfV5^_^M8b#<`2x4W}fmaFRpnzDIrYHt36%8E$M!S}9f8sq};(l%F} zc+OK&Ema)43+JrJw9YdwB-~2zurphewIoIla;QnwEp;Q zPV}sm(Cn2LiabgW;-?;Fzr1$F(`8V_@@;bR`_{xgZ}L@b{9518kF`ea8$doX^<9!cnZ7<$Y_vO^bYK6YOX`WKy-i4jtCiN(} z4`m4Mq}$3S^iPl3nCfyRZpiF#S$k^#@tVfm!78Qip~fLffqYKP#cikJ(`@~o+6-#P zaP>4_N?umkUF1UB?}n2l@LUhYYU(dq;~{xD{r1A%p_E3afXI{7o+Z7Fs)6K74#~YL z-=y9qD>g>n=UwSK`-pPm+3b~a(b6`tE>{<|oVh$KRo2*DZuIK@c|)rF+)w3rc&*Rv zgFVT&ZsdjqB18M0aEX6pNvh?{Pgk#M8g6KFi22(l^Rr|9rR|sHOXBnMDSP5{tLI!+ zQRB1BjOG#_z9`_^WlA67b#>}@d>B6ZWaEpH5jzXo<;Tku%BLM!HU}p$6VkjK>^?2n zSY>LF03UxX;+e*DFG#vT*X8r$Ym`TWp6$zBGK_EuvhJy2%Z=XEuF5E*H^q4RuXWK8 z4k;cxrrvR{*e{`1_rmLCfu?uj>=y^=I)uJ=mv>&Pz#2Y+cv#lFxSZj4uk0<$CcEUZ z%bg_!>{k)%S1QC#wOBxq%Gs~K{anz?y3AuQv+IrLzRv7hczE-N?fquGS3e{^zS(6( z=v$#Yt;!Wys$}(?>g}{3k717S}w<_g)6;>5TZ$ediPH=kRAXKJ3T}&s@7M)9U#b4~s=b zWWyC+pUs0_-TAY39c5OG-|`oemPTAWY2R=ws5py3(%y*Yq#QV+q>zd^4}fw_VZH>w8-t z(s(q2UnWU-G#Fb_ys0I^p=9Pa(!wXI(uU8@&rrE^{PUn2yE|LipCQY?{pgVo0)J!8bH)$}8FIVoq$E79lc8*Ms9YlL4B{>+u zh4u1pFW#H?xVb#v5nk!y;JJxZVWmzf(vz(|ce-sET<=fSNT4ND5W48L+;=k7cC ztsp+}8MTJfn^U)=lsiQ0sk_p>n88*Fa`MYMQR?)}^qWsyUISj<<%x3g1DRa{FO-k| zZFVr{(~Xo9Zp~4rU4~k!Xq3pW7hB-_PQ2Y2lAg(fA8J`snpbn4oO0flKj)))^J}g6 zFN2Xfy2)`4i! zyrkFtcaOOLY3<%%Uw&-L+Wt`acQ;8VPjGjx@;cB~RJZHql_Q6>`rRv^@e`+6rTd=G zf*vN@*3K=N6yHag7qq7(S)neF;O+4j%T2H%w({!fqx-0xOFT{z~_1PbGFcp|+p168qz9%y4^SQQeppg{(z?sjV+l+Wh` zu~CSmMbjeUiDXU4UkLKaP`)q-B5LWV0!X2szn&wwhK&M(Cj-?06cy;faA;_#Rw!AE zFJ!?)8jS`MNHB?n2OM}&I1gon;dvruFrHWuw)+n;o=8iqlNOWDh1u>fQHubN4>X?J zviUp+8LMULWx2 z*@4T3f4C{Q;L@D~LLj_76OTg9B$6IP)T8QYQ}y&nkUsnyCvZ6sH38LMP!0Y+h)&>~ zAj%gygFv9Ocp(A~ABD8Fv>^clWd?AN4G0G!jgBf79plu8G4D(;&VOhwhQQA5e>NDG zi^Vay0A-TjXcS#gxciMp(EcYMf%;DxjQ~9Qo2<6(Klnf)a{?bKWPk#M z5d6Omf}PkAph!u9U`IaKO~v&|2)5$+^C2u$K;hEL6!O$3n3$Up$mZrWs)-KG)Rbam qN;0OAbc{@mfw#@6=Jfxa!y7A9icp3S6+2CbN+aV`RLtznasLmPIX=<= literal 0 HcmV?d00001 diff --git a/figures/log_exp.plot b/figures/log_exp.plot new file mode 100644 index 0000000..a1ba5d8 --- /dev/null +++ b/figures/log_exp.plot @@ -0,0 +1,18 @@ +# 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 "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.txt' index 0 using 1:4 t "No log exp" with linespoints ls 2,\ + 'log_exp.txt' index 0 using 1:2 t "with log exp" with linespoints ls 1,\ + 'log_exp.txt'index 1 using 1:2 t "with_log_exp" with linespoints ls 1 diff --git a/figures/log_exp.txt b/figures/log_exp.txt new file mode 100644 index 0000000..6cb1f8c --- /dev/null +++ b/figures/log_exp.txt @@ -0,0 +1,21 @@ +# First data block (index 0) +#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 1) +#EA With_log_exp +#Taille_Poly times nb iter +4500 0.946749 23 +5000 0.769945 33 +6000 1.38447 48 +10000 2.15026 32 +100000 306.117 141 + diff --git a/mybibfile.bib b/mybibfile.bib index b87ff2b..cbaa902 100644 --- a/mybibfile.bib +++ b/mybibfile.bib @@ -1,408 +1,408 @@ -@article{Dirac1953888, - title = "The lorentz transformation and absolute time", - journal = "Physica ", - volume = "19", - number = "1-–12", - pages = "888--896", - year = "1953", - doi = "10.1016/S0031-8914(53)80099-6", - author = "P.A.M. Dirac" -} - -@article{Feynman1963118, - title = "The theory of a general quantum system interacting with a linear dissipative system", - journal = "Annals of Physics ", - volume = "24", - pages = "118--173", - year = "1963", - doi = "10.1016/0003-4916(63)90068-X", - author = "R.P Feynman AND F.L {Vernon Jr.}" -} - -@Article{Aberth73, - title = "Iteration Methods for Finding all Zeros of a Polynomial Simultaneously", - journal = "Mathematics of Computation", - volume = "27", - number = "122", - pages = "339--344", - year = "1973", - doi = "10.1016/0003-4916(63)90068-X", - author = "O. Aberth", - -}x - - -@Article{Ilie50, - title = "On the approximations of Newton", - journal = "Annual Sofia Univ", - volume = "", - number = "46", - pages = "167--171", - year = "1950", - doi = "10.1016/0003-4916(63)90068-X", - author = "L. Ilieff", - -}x -@Article{Docev62, - title = "An alternative method of Newton for simultaneous calculation of all the roots of a given algebraic equation", - journal = "Phys. Math. J", - volume = "", - number = "5", - pages = "136-139", - year = "1962", - author = "K. Docev", -}x - -@Article{Durand60, - title = "Solution Numerique des Equations Algebriques, Vol. 1, Equations du Type F(x)=0, Racines d'une Polynome", - journal = "", - volume = "Vol.1", - number = "", - pages = "", - year = "1960", - author = "E. Durand", -}x - -@Article{Kerner66, - title = "Ein Gesamtschritteverfahren zur Berechnung der Nullstellen von Polynomen", - journal = " ", - volume = "", - number = "8", - pages = "290-294", - year = "1966", - author = "I. Kerner", -}x - -@Article{Borch-Supan63, - title = "A posteriori error for the zeros of polynomials", - journal = " ", - volume = "", - number = "5", - pages = "380-398", - year = "1963", - author = "W. Borch-Supan", -}x - -@Article{Ehrlich67, - title = "A modified Newton method for polynomials", - journal = " Comm. Ass. Comput. Mach.", - volume = "", - number = "10", - pages = "107-108", - year = "1967", - author = "L.W. Ehrlich", -}x - -@Article{Loizon83, - title = "Higher-order iteration functions for simultaneously approximating polynomial zeros", - journal = " Intern. J. Computer Math", - volume = "", - number = "14", - pages = "45-58", - year = "1983", - author = "G. Loizon", -}x - -@Article{Freeman89, - title = " Calculating polynomial zeros on a local memory parallel computer", - journal = " Parallel Computing", - volume = "", - number = "12", - pages = "351-358", - year = "1989", - author = "T.L. Freeman", -}x - -@Article{Freemanall90, - title = " Asynchronous polynomial zero-finding algorithms", - journal = " Parallel Computing", - volume = "", - number = "17", - pages = "673-681", - year = "1990", - author = "T.L. Freeman AND R.K. Brankin", -}x - -@Article{Raphaelall01, - title = " Extraction de racines dans des polynômes creux de degrées élevés.RSRCP (Réseaux et Systèmes Répartis, Calculateurs Parallèles)", - journal = " Algorithmes itératifs paralléles et distribués", - volume = "1", - number = "13", - pages = "67-81", - year = "1990", - author = "R. Couturier AND F. Spetiri", -}x - -@Article{Ostrowski41, - title = " On a Theorem by J.L. Walsh Concerning the Moduli of Roots of Algebraic Equations,Bull. A.M.S.", - journal = " Algorithmes itératifs paralléles et distribués", - volume = "1", - number = "47", - pages = "742-746", - year = "1941", - author = "A. Ostrowski", -}x - - -@Manual{CUDA10, -title = {Compute Unified Device Architecture Programming Guide Version 3.0}, -OPTkey = {NVIDIA CUDA}, -OPTauthor = {•}, -OPTorganization = {NVIDIA CUDA}, -OPTaddress = {•}, -OPTedition = {•}, -OPTmonth = {March}, -OPTyear = {2010}, -OPTnote = {http://www.nvidia.com/object/cuda_develop.html}, -OPTannote = {•} -} - -@Article{Kahinall14, - title = " parallel implementation of the Durand-Kerner algorithm for polynomial root-finding on GPU", - journal = " IEEE. Conf. on advanced Networking, Distributed Systems and Applications", - volume = "", - number = "", - pages = "53-57", - year = "2014", - author = "K. Ghidouche AND R. Couturie AND A. Sider", -}x - -@Article{Karimall98, - - title = " Perfectionnements de la méthode asynchrone de Durand-Kerner pour les polynômes complexes", - journal = " Calculateurs Parallèles", - volume = "10", - number = "4", - pages = "449-458", - year = "1998", - author = "K. Rhofir AND F. Spies AND Jean-Claude Miellou", -}x - -@Article{Bini96, - - title = " Numerical computation of polynomial zeros by means of Aberth s method", - journal = " Numerical Algorithms", - volume = "13", - number = "4", - pages = "179-200", - year = "1996", - author = "D. Bini", -}x - -@Article{Mirankar68, - title = " Parallel methods for approximating the roots of a function", - journal = " IBM Res Dev", - volume = "30", - number = "", - pages = "297-301", - year = "1968", - author = "WL. Mirankar", -}x - -@Article{Mirankar71, - title = " A survey of parallelism in numerical analysis", - journal = " SIAM Rev", - volume = "", - number = "", - pages = "524-547", - year = "1971", - author = "WL. Mirankar", -}x - -@Article{Schedler72, - title = " Parallel iteration methods in complexity of computer communications", - journal = " Commun ACM ", - volume = "", - number = "", - pages = "286-290", - year = "1967", - author = "GS. Schedler", -}x - -@Article{Winogard72, - title = " Parallel iteration methods in complexity of computer communications", - journal = " Plenum, New York", - volume = "", - number = "", - pages = "", - year = "1972", - author = "S. Winogard", -}x - -@Article{Benall68, - title = " A fast parallel algorithm for determining all roots of a polynomial with real roots", - journal = " Int: Proc of ACM", - volume = "", - number = "", - pages = "340-349", - year = "1968", - author = "M. Ben-Or AND E. Feig AND D. Kozzen AND P. Tiwary", -}x - -@Article{Riceall06, - title = " A highly parallel algorithm for root extraction", - journal = " IEEE Trans Comp", - volume = "38", - number = "3", - pages = "443-449", - year = "2006", - author = "TA. Rice AND LH. Jamieson", -}x - -@Article{Cosnard90, - title = " Finding the roots of a polynomial on an MIMD multicomputer", - journal = " Parallel Comput", - volume = "15", - number = "3", - pages = "75-85", - year = "1990", - author = "M. Cosnard AND P. Fraigniaud", -}x - -@Article{Janall99, - title = " Efficient parallel algorithms for finding polynomial zeroes", - journal = "Proc of the 6th int conference on advance computing, CDAC, Pune University Campus,India", - volume = "15", - number = "3", - pages = "189-196", - year = "1999", - author = "PK. Jana AND BP. Sinha AND R. Datta Gupta", -}x - -@Article{Jana06, - title = " Polynomial interpolation and polynomial root finding on OTIS-Mesh", - journal = " Parallel Comput", - volume = "32", - number = "3", - pages = "301-312", - year = "2006", - author = "PK. Jana", -}x -@Article{Kalantari08, - title = " Polynomial root finding and polynomiography.", - journal = " World Scientifict,New Jersey", - volume = "", - number = "", - pages = "", - year = "", - author = "B. Kalantari", -}x - -@Article{Gemignani07, - title = " Structured matrix methods for polynomial root finding.", - journal = " n: Proc of the 2007 Intl symposium on symbolic and algebraic computation", - volume = "", - number = "", - pages = "175-180", - year = "2007", - author = "L. Gemignani", -}x - - - -@Article{Skachek08, - title = " Structured matrix methods for polynomial root finding.", - journal = " n: Proc of the 2007 Intl symposium on symbolic and algebraic computation", - volume = "", - number = "", - pages = "175-180", - year = "2008", - author = "V. Skachek", -}x - -@BOOK{Skachek008, - AUTHOR = {V. Skachek}, - editor = {}, - TITLE = {Probabilistic algorithm for finding roots of linearized polynomials}, - PUBLISHER = {codes and cryptography. Kluwer}, - YEAR = {2008}, - volume = {}, - number = {}, - series = {}, - address = {}, - edition = {Design}, - month = {}, - note = {}, - abstract = {}, - isbn = {}, - price = {}, - keywords = {}, - source = {}, -}x - -@Article{Zhancall08, - title = " A constrained learning algorithm for finding multiple real roots of polynomial", - journal = " In: Proc of the 2008 intl symposium on computational intelligence and design", - volume = "", - number = "", - pages = "38-41", - year = "2008", - author = "X. Zhanc AND M. Wan,Z.Yi", -}x - - -@Article{Zhuall08, - title = " an adaptive algorithm finding multiple roots of polynomials", - journal = " Lect Notes Comput Sci ", - volume = "", - number = "5262", - pages = "674-681", - year = "2008", - author = "W. Zhu AND w. Zeng AND D. Lin", -}x -@Article{Azad07, - title = " The performance of synchronous parallel polynomial root extraction on a ring multicomputer", - journal = " Clust Comput ", - volume = "2", - number = "10", - pages = "167-174", - year = "2007", - author = "HS. Azad", -}x - - - - -@Article{Bini04, - title = " Inverse power and Durand Kerner iterations for univariate polynomial root finding", - journal = " Comput Math Appl ", - volume = "", - number = "47", - pages = "447-459", - year = "2004", - author = "DA. Bini AND L. Gemignani", -}x - -@Article{Jana99, - title = " Finding polynomial zeroes on a Multi-mesh of trees (MMT)", - journal = " In: Proc of the 2nd int conference on information technology", - volume = "", - number = "", - pages = "202-206", - year = "1999", - author = "PK. Jana", -}x - -@Article{Weierstrass03, - title = " Neuer Beweis des Satzes, dass jede ganze rationale function einer veranderlichen dagestellt werden kann als ein product aus linearen functionen derselben veranderlichen", - journal = " Ges. Werke", - volume = "3", - number = "", - pages = "251-269", - year = "1903", - author = "K. Weierstrass", -}x - - - -@BOOK{NVIDIA10, - AUTHOR = {NVIDIA}, - editor = {Design Guide}, - TITLE = {NVIDIA CUDA C Programming Guide}, - PUBLISHER = {PG}, - YEAR = {2015}, - volume = {7}, - number = {02829}, - series = {001}, - month = {march}, -}x +@article{Dirac1953888, + title = "The lorentz transformation and absolute time", + journal = "Physica ", + volume = "19", + number = "1-–12", + pages = "888--896", + year = "1953", + doi = "10.1016/S0031-8914(53)80099-6", + author = "P.A.M. Dirac" +} + +@article{Feynman1963118, + title = "The theory of a general quantum system interacting with a linear dissipative system", + journal = "Annals of Physics ", + volume = "24", + pages = "118--173", + year = "1963", + doi = "10.1016/0003-4916(63)90068-X", + author = "R.P Feynman AND F.L {Vernon Jr.}" +} + +@Article{Aberth73, + title = "Iteration Methods for Finding all Zeros of a Polynomial Simultaneously", + journal = "Mathematics of Computation", + volume = "27", + number = "122", + pages = "339--344", + year = "1973", + doi = "10.1016/0003-4916(63)90068-X", + author = "O. Aberth", + +}x + + +@Article{Ilie50, + title = "On the approximations of Newton", + journal = "Annual Sofia Univ", + volume = "", + number = "46", + pages = "167--171", + year = "1950", + doi = "10.1016/0003-4916(63)90068-X", + author = "L. Ilieff", + +}x +@Article{Docev62, + title = "An alternative method of Newton for simultaneous calculation of all the roots of a given algebraic equation", + journal = "Phys. Math. J", + volume = "", + number = "5", + pages = "136-139", + year = "1962", + author = "K. Docev", +}x + +@Article{Durand60, + title = "Solution Numerique des Equations Algebriques, Vol. 1, Equations du Type F(x)=0, Racines d'une Polynome", + journal = "", + volume = "Vol.1", + number = "", + pages = "", + year = "1960", + author = "E. Durand", +}x + +@Article{Kerner66, + title = "Ein Gesamtschritteverfahren zur Berechnung der Nullstellen von Polynomen", + journal = " ", + volume = "", + number = "8", + pages = "290-294", + year = "1966", + author = "I. Kerner", +}x + +@Article{Borch-Supan63, + title = "A posteriori error for the zeros of polynomials", + journal = " ", + volume = "", + number = "5", + pages = "380-398", + year = "1963", + author = "W. Borch-Supan", +}x + +@Article{Ehrlich67, + title = "A modified Newton method for polynomials", + journal = " Comm. Ass. Comput. Mach.", + volume = "", + number = "10", + pages = "107-108", + year = "1967", + author = "L.W. Ehrlich", +}x + +@Article{Loizon83, + title = "Higher-order iteration functions for simultaneously approximating polynomial zeros", + journal = " Intern. J. Computer Math", + volume = "", + number = "14", + pages = "45-58", + year = "1983", + author = "G. Loizon", +}x + +@Article{Freeman89, + title = " Calculating polynomial zeros on a local memory parallel computer", + journal = " Parallel Computing", + volume = "", + number = "12", + pages = "351-358", + year = "1989", + author = "T.L. Freeman", +}x + +@Article{Freemanall90, + title = " Asynchronous polynomial zero-finding algorithms", + journal = " Parallel Computing", + volume = "", + number = "17", + pages = "673-681", + year = "1990", + author = "T.L. Freeman AND R.K. Brankin", +}x + +@Article{Raphaelall01, + title = " Extraction de racines dans des polynômes creux de degrées élevés.RSRCP (Réseaux et Systèmes Répartis, Calculateurs Parallèles)", + journal = " Algorithmes itératifs paralléles et distribués", + volume = "1", + number = "13", + pages = "67-81", + year = "1990", + author = "R. Couturier AND F. Spiteri", +}x + +@Article{Ostrowski41, + title = " On a Theorem by J.L. Walsh Concerning the Moduli of Roots of Algebraic Equations,Bull. A.M.S.", + journal = " Algorithmes itératifs paralléles et distribués", + volume = "1", + number = "47", + pages = "742-746", + year = "1941", + author = "A. Ostrowski", +}x + + +@Manual{CUDA10, +title = {Compute Unified Device Architecture Programming Guide Version 3.0}, +OPTkey = {NVIDIA CUDA}, +OPTauthor = {•}, +OPTorganization = {NVIDIA CUDA}, +OPTaddress = {•}, +OPTedition = {•}, +OPTmonth = {March}, +OPTyear = {2010}, +OPTnote = {http://www.nvidia.com/object/cuda_develop.html}, +OPTannote = {•} +} + +@Article{Kahinall14, + title = " parallel implementation of the Durand-Kerner algorithm for polynomial root-finding on GPU", + journal = " IEEE. Conf. on advanced Networking, Distributed Systems and Applications", + volume = "", + number = "", + pages = "53-57", + year = "2014", + author = "K. Ghidouche AND R. Couturier AND A. Sider", +}x + +@Article{Karimall98, + + title = " Perfectionnements de la méthode asynchrone de Durand-Kerner pour les polynômes complexes", + journal = " Calculateurs Parallèles", + volume = "10", + number = "4", + pages = "449-458", + year = "1998", + author = "K. Rhofir AND F. Spies AND Jean-Claude Miellou", +}x + +@Article{Bini96, + + title = " Numerical computation of polynomial zeros by means of Aberth s method", + journal = " Numerical Algorithms", + volume = "13", + number = "4", + pages = "179-200", + year = "1996", + author = "D. Bini", +}x + +@Article{Mirankar68, + title = " Parallel methods for approximating the roots of a function", + journal = " IBM Res Dev", + volume = "30", + number = "", + pages = "297-301", + year = "1968", + author = "WL. Mirankar", +}x + +@Article{Mirankar71, + title = " A survey of parallelism in numerical analysis", + journal = " SIAM Rev", + volume = "", + number = "", + pages = "524-547", + year = "1971", + author = "WL. Mirankar", +}x + +@Article{Schedler72, + title = " Parallel iteration methods in complexity of computer communications", + journal = " Commun ACM ", + volume = "", + number = "", + pages = "286-290", + year = "1967", + author = "GS. Schedler", +}x + +@Article{Winogard72, + title = " Parallel iteration methods in complexity of computer communications", + journal = " Plenum, New York", + volume = "", + number = "", + pages = "", + year = "1972", + author = "S. Winogard", +}x + +@Article{Benall68, + title = " A fast parallel algorithm for determining all roots of a polynomial with real roots", + journal = " Int: Proc of ACM", + volume = "", + number = "", + pages = "340-349", + year = "1968", + author = "M. Ben-Or AND E. Feig AND D. Kozzen AND P. Tiwary", +}x + +@Article{Riceall06, + title = " A highly parallel algorithm for root extraction", + journal = " IEEE Trans Comp", + volume = "38", + number = "3", + pages = "443-449", + year = "2006", + author = "TA. Rice AND LH. Jamieson", +}x + +@Article{Cosnard90, + title = " Finding the roots of a polynomial on an MIMD multicomputer", + journal = " Parallel Comput", + volume = "15", + number = "3", + pages = "75-85", + year = "1990", + author = "M. Cosnard AND P. Fraigniaud", +}x + +@Article{Janall99, + title = " Efficient parallel algorithms for finding polynomial zeroes", + journal = "Proc of the 6th int conference on advance computing, CDAC, Pune University Campus,India", + volume = "15", + number = "3", + pages = "189-196", + year = "1999", + author = "PK. Jana AND BP. Sinha AND R. Datta Gupta", +}x + +@Article{Jana06, + title = " Polynomial interpolation and polynomial root finding on OTIS-Mesh", + journal = " Parallel Comput", + volume = "32", + number = "3", + pages = "301-312", + year = "2006", + author = "PK. Jana", +}x +@Article{Kalantari08, + title = " Polynomial root finding and polynomiography.", + journal = " World Scientifict,New Jersey", + volume = "", + number = "", + pages = "", + year = "", + author = "B. Kalantari", +}x + +@Article{Gemignani07, + title = " Structured matrix methods for polynomial root finding.", + journal = " n: Proc of the 2007 Intl symposium on symbolic and algebraic computation", + volume = "", + number = "", + pages = "175-180", + year = "2007", + author = "L. Gemignani", +}x + + + +@Article{Skachek08, + title = " Structured matrix methods for polynomial root finding.", + journal = " n: Proc of the 2007 Intl symposium on symbolic and algebraic computation", + volume = "", + number = "", + pages = "175-180", + year = "2008", + author = "V. Skachek", +}x + +@BOOK{Skachek008, + AUTHOR = {V. Skachek}, + editor = {}, + TITLE = {Probabilistic algorithm for finding roots of linearized polynomials}, + PUBLISHER = {codes and cryptography. Kluwer}, + YEAR = {2008}, + volume = {}, + number = {}, + series = {}, + address = {}, + edition = {Design}, + month = {}, + note = {}, + abstract = {}, + isbn = {}, + price = {}, + keywords = {}, + source = {}, +}x + +@Article{Zhancall08, + title = " A constrained learning algorithm for finding multiple real roots of polynomial", + journal = " In: Proc of the 2008 intl symposium on computational intelligence and design", + volume = "", + number = "", + pages = "38-41", + year = "2008", + author = "X. Zhanc AND M. Wan,Z.Yi", +}x + + +@Article{Zhuall08, + title = " an adaptive algorithm finding multiple roots of polynomials", + journal = " Lect Notes Comput Sci ", + volume = "", + number = "5262", + pages = "674-681", + year = "2008", + author = "W. Zhu AND w. Zeng AND D. Lin", +}x +@Article{Azad07, + title = " The performance of synchronous parallel polynomial root extraction on a ring multicomputer", + journal = " Clust Comput ", + volume = "2", + number = "10", + pages = "167-174", + year = "2007", + author = "HS. Azad", +}x + + + + +@Article{Bini04, + title = " Inverse power and Durand Kerner iterations for univariate polynomial root finding", + journal = " Comput Math Appl ", + volume = "", + number = "47", + pages = "447-459", + year = "2004", + author = "DA. Bini AND L. Gemignani", +}x + +@Article{Jana99, + title = " Finding polynomial zeroes on a Multi-mesh of trees (MMT)", + journal = " In: Proc of the 2nd int conference on information technology", + volume = "", + number = "", + pages = "202-206", + year = "1999", + author = "PK. Jana", +}x + +@Article{Weierstrass03, + title = " Neuer Beweis des Satzes, dass jede ganze rationale function einer veranderlichen dagestellt werden kann als ein product aus linearen functionen derselben veranderlichen", + journal = " Ges. Werke", + volume = "3", + number = "", + pages = "251-269", + year = "1903", + author = "K. Weierstrass", +}x + + + +@BOOK{NVIDIA10, + AUTHOR = {NVIDIA}, + editor = {Design Guide}, + TITLE = {NVIDIA CUDA C Programming Guide}, + PUBLISHER = {PG}, + YEAR = {2015}, + volume = {7}, + number = {02829}, + series = {001}, + month = {march}, +}x diff --git a/paper.tex b/paper.tex index c8a6698..9897244 100644 --- a/paper.tex +++ b/paper.tex @@ -96,7 +96,7 @@ root finding of polynomials, high degree, iterative methods, Durant-Kerner, GPU, Polynomials are algebraic structures used in mathematics that capture physical phenomenons and that express the outcome in the form of a function of some unknown variable. Formally speaking, a polynomial $p(x)$ of degree \textit{n} having $n$ coefficients in the complex plane \textit{C} and zeros $\alpha_{i},\textit{i=1,...,n}$ %%\begin{center} \begin{equation} - {\Large p(x)=\sum{a_{i}x^{i}}=a_{n}\prod(x-\alpha_{i}),a_{0} a_{n}\neq 0}. + {\Large p(x)=\sum_{i=0}^{n}{a_{i}x^{i}}=a_{n}\prod_{i=1}^{n}(x-\alpha_{i}), a_{0} a_{n}\neq 0}. \end{equation} %%\end{center} @@ -583,33 +583,27 @@ or from GPU memory to CPU memory \verb=(cudaMemcpyDeviceToHost))=. \section{Experimental study} \subsection{Definition of the polynomial used} -We use two forms of polynomials: -\paragraph{sparse polynomial}: -in this following form, the roots are distributed on 2 distinct circles: +We study two forms of polynomials the sparse polynomials and the full polynomials: +\paragraph{Sparse polynomial}: in this following form, the roots are distributed on 2 distinct circles: \begin{equation} - \forall \alpha_{1} \alpha_{2} \in C,\forall n_{1},n_{2} \in N^{*}; P(z)= (z^{n^{1}}-\alpha_{1})(z^{n^{2}}-\alpha_{2}) + \forall \alpha_{1} \alpha_{2} \in C,\forall n_{1},n_{2} \in N^{*}; P(z)= (z^{n_{1}}-\alpha_{1})(z^{n_{2}}-\alpha_{2}) \end{equation} This form makes it possible to associate roots having two different modules and thus to work on a polynomial constitute of four non zero terms. -\paragraph{Full polynomial}: - the second form used to obtain a full polynomial is: +\paragraph{Full polynomial}: the second form used to obtain a full polynomial is: %%\begin{equation} %%\forall \alpha_{i} \in C,\forall n_{i}\in N^{*}; P(z)= \sum^{n}_{i=1}(z^{n^{i}}.a_{i}) %%\end{equation} \begin{equation} - {\Large \forall a_{i} \in C, i\in N; p(x)=\sum^{n-1}_{i=1} a_{i}.x^{i}} + {\Large \forall a_{i} \in C, i\in N; p(x)=\sum^{n}_{i=0} a_{i}.x^{i}} \end{equation} with this form, we can have until \textit{n} non zero terms. \subsection{The study condition} -In order to have representative average values, for each -point of our curves we measured the roots finding of 10 -different polynomials. - The our experiences results concern two parameters which are the polynomial degree and the execution time of our program to converge on the solution. The polynomial degree allows us @@ -617,7 +611,7 @@ to validate that our algorithm is powerful with high degree polynomials. The execution time remains the element-key which justifies our work of parallelization. For our tests we used a CPU Intel(R) Xeon(R) CPU -E5620@2.40GHz and a GPU K40 (with 6 Go of ram) +E5620@2.40GHz and a GPU K40 (with 6 Go of ram). \subsection{Comparative study} @@ -678,7 +672,12 @@ We initially carried out the convergence of Aberth algorithm with various sizes \label{fig:01} \end{figure} - +\begin{figure}[htbp] +\centering + \includegraphics[width=0.8\textwidth]{figures/log_exp} +\caption{The impact of exp-log solution to compute very high degrees of polynomial.} +\label{fig:01} +\end{figure} \subsubsection{A comparative study between Aberth and Durand-kerner algorithm} \begin{table}[htbp] -- 2.39.5