MAJ des figures

diff --git a/figures/Compar_EA_algorithm_CPU_GPU.txt b/figures/Compar_EA_algorithm_CPU_GPU.txt
index 1d6d23bccc92160876d5a8edeff0ac31e539929b..b2bf4a3ab71900e9c7fc136be28a6c70889e390b 100644 (file)
--- 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 (file)
index 0000000..2ccdbf6
Binary files /dev/null and b/figures/log_exp.pdf differ

diff --git a/figures/log_exp.plot b/figures/log_exp.plot
new file mode 100644 (file)
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 (file)
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 b87ff2bcfc32d308a9a42b0938f123b44320edf9..cbaa9020754dbc2ef1765c61413161ae5cd989d5 100644 (file)
--- a/mybibfile.bib
+++ b/mybibfile.bib
@@ -1,408 +1,408 @@
-@article{Dirac1953888,\r
-  title   = "The lorentz transformation and absolute time",\r
-  journal = "Physica ",\r
-  volume  = "19",\r
-  number  = "1-–12",\r
-  pages   = "888--896",\r
-  year    = "1953",\r
-  doi     = "10.1016/S0031-8914(53)80099-6",\r
-  author  = "P.A.M. Dirac"\r
-}\r
-\r
-@article{Feynman1963118,\r
-  title   = "The theory of a general quantum system interacting with a linear dissipative system",\r
-  journal = "Annals of Physics ",\r
-  volume  = "24",\r
-  pages   = "118--173",\r
-  year    = "1963",\r
-  doi     = "10.1016/0003-4916(63)90068-X",\r
-  author  = "R.P Feynman AND F.L {Vernon Jr.}"\r
-}\r
-\r
-@Article{Aberth73,\r
-   title =   "Iteration Methods for Finding all Zeros of a Polynomial Simultaneously",\r
-  journal = "Mathematics of Computation",\r
-  volume =  "27",\r
-  number =  "122",\r
-  pages =   "339--344",\r
-  year =    "1973",\r
-       doi     = "10.1016/0003-4916(63)90068-X",\r
-  author =  "O. Aberth",\r
-       \r
-}x\r
-\r
-\r
-@Article{Ilie50,\r
-  title =   "On the approximations of Newton",\r
-  journal = "Annual Sofia Univ",\r
-  volume =  "",\r
-  number =  "46",\r
-  pages =   "167--171",\r
-  year =    "1950",\r
-  doi     = "10.1016/0003-4916(63)90068-X",\r
-       author =  "L. Ilieff",\r
-       \r
-}x\r
-@Article{Docev62,\r
-  title =   "An alternative method of Newton for simultaneous calculation of all the roots of a given algebraic equation",\r
-  journal = "Phys. Math. J",\r
-  volume =  "",\r
-  number =  "5",\r
-  pages =   "136-139",\r
-  year =    "1962",\r
-  author =  "K. Docev",\r
-}x\r
-\r
-@Article{Durand60,\r
-  title =   "Solution Numerique des Equations Algebriques, Vol. 1, Equations du Type F(x)=0, Racines d'une Polynome",\r
-  journal = "",\r
-  volume =  "Vol.1",\r
-  number =  "",\r
-  pages =   "",\r
-  year =    "1960",\r
-  author =  "E. Durand",\r
-}x\r
-\r
-@Article{Kerner66,\r
-  title =   "Ein Gesamtschritteverfahren zur Berechnung der Nullstellen von Polynomen",\r
-  journal = " ",\r
-  volume =  "",\r
-  number =  "8",\r
-  pages =   "290-294",\r
-  year =    "1966",\r
-  author =  "I. Kerner",\r
-}x\r
-\r
-@Article{Borch-Supan63,\r
-  title =   "A posteriori error for the zeros of polynomials",\r
-  journal = " ",\r
-  volume =  "",\r
-  number =  "5",\r
-  pages =   "380-398",\r
-  year =    "1963",\r
-  author =  "W. Borch-Supan",\r
-}x\r
-\r
-@Article{Ehrlich67,\r
-  title =   "A modified Newton method for polynomials",\r
-  journal = " Comm. Ass. Comput. Mach.",\r
-  volume =  "",\r
-  number =  "10",\r
-  pages =   "107-108",\r
-  year =    "1967",\r
-  author =  "L.W. Ehrlich",\r
-}x\r
-\r
-@Article{Loizon83,\r
-  title =   "Higher-order iteration functions for simultaneously approximating polynomial zeros",\r
-  journal = " Intern. J. Computer Math",\r
-  volume =  "",\r
-  number =  "14",\r
-  pages =   "45-58",\r
-  year =    "1983",\r
-  author =  "G. Loizon",\r
-}x\r
-\r
-@Article{Freeman89,\r
-  title =   " Calculating polynomial zeros on a local memory parallel computer",\r
-  journal = "  Parallel Computing",\r
-  volume =  "",\r
-  number =  "12",\r
-  pages =   "351-358",\r
-  year =    "1989",\r
-  author =  "T.L. Freeman",\r
-}x\r
-\r
-@Article{Freemanall90,\r
-  title =   " Asynchronous polynomial zero-finding algorithms",\r
-  journal = "  Parallel Computing",\r
-  volume =  "",\r
-  number =  "17",\r
-  pages =   "673-681",\r
-  year =    "1990",\r
-  author =  "T.L. Freeman AND R.K. Brankin",\r
-}x\r
-\r
-@Article{Raphaelall01,\r
-  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)",\r
-  journal = "  Algorithmes itératifs paralléles et distribués",\r
-  volume =  "1",\r
-  number =  "13",\r
-  pages =   "67-81",\r
-  year =    "1990",\r
-  author =  "R. Couturier AND F. Spetiri",\r
-}x\r
-\r
-@Article{Ostrowski41,\r
-  title =   "  On a Theorem by J.L. Walsh Concerning the Moduli of Roots of Algebraic Equations,Bull. A.M.S.",\r
-  journal = "  Algorithmes itératifs paralléles et distribués",\r
-  volume =  "1",\r
-  number =  "47",\r
-  pages =   "742-746",\r
-  year =    "1941",\r
-  author =  "A. Ostrowski",\r
-}x\r
-\r
-\r
-@Manual{CUDA10,\r
-title = {Compute Unified Device Architecture Programming Guide Version 3.0},\r
-OPTkey = {NVIDIA CUDA},\r
-OPTauthor = {•},\r
-OPTorganization = {NVIDIA CUDA},\r
-OPTaddress = {•},\r
-OPTedition = {•},\r
-OPTmonth = {March},\r
-OPTyear = {2010},\r
-OPTnote = {http://www.nvidia.com/object/cuda_develop.html},\r
-OPTannote = {•}\r
-}\r
-\r
-@Article{Kahinall14,\r
-  title =   "  parallel implementation of the Durand-Kerner algorithm for polynomial root-finding on GPU",\r
-  journal = "  IEEE. Conf. on advanced Networking, Distributed Systems and Applications",\r
-  volume =  "",\r
-  number =  "",\r
-  pages =   "53-57",\r
-  year =    "2014",\r
-  author =  "K. Ghidouche AND R. Couturie AND A. Sider",\r
-}x\r
-\r
-@Article{Karimall98,\r
-  \r
-  title =   "  Perfectionnements de la méthode asynchrone de Durand-Kerner pour les polynômes complexes",\r
-  journal = "  Calculateurs Parallèles",\r
-  volume =  "10",\r
-  number =  "4",\r
-  pages =   "449-458",\r
-  year =    "1998",\r
-  author =  "K. Rhofir         AND F. Spies AND Jean-Claude Miellou",\r
-}x\r
-\r
-@Article{Bini96,\r
- \r
-  title =   "  Numerical computation of polynomial zeros by means of Aberth s method",\r
-  journal = " Numerical Algorithms",\r
-  volume =  "13",\r
-  number =  "4",\r
-  pages =   "179-200",\r
-  year =    "1996",\r
-  author =  "D. Bini",\r
-}x\r
-\r
-@Article{Mirankar68,\r
-  title =   "  Parallel methods for approximating the roots of a function",\r
-  journal = " IBM Res Dev",\r
-  volume =  "30",\r
-  number =  "",\r
-  pages =   "297-301",\r
-  year =    "1968",\r
-  author =  "WL. Mirankar",\r
-}x\r
-\r
-@Article{Mirankar71,\r
-  title =   "  A survey of parallelism in numerical analysis",\r
-  journal = " SIAM Rev",\r
-  volume =  "",\r
-  number =  "",\r
-  pages =   "524-547",\r
-  year =    "1971",\r
-  author =  "WL. Mirankar",\r
-}x\r
-\r
-@Article{Schedler72,\r
-  title =   "  Parallel iteration methods in complexity of computer communications",\r
-  journal = " Commun ACM ",\r
-  volume =  "",\r
-  number =  "",\r
-  pages =   "286-290",\r
-  year =    "1967",\r
-  author =  "GS. Schedler",\r
-}x\r
-\r
-@Article{Winogard72,\r
-  title =   "  Parallel iteration methods in complexity of computer communications",\r
-  journal = " Plenum, New York",\r
-  volume =  "",\r
-  number =  "",\r
-  pages =   "",\r
-  year =    "1972",\r
-  author =  "S. Winogard",\r
-}x\r
-\r
-@Article{Benall68,\r
-  title =   " A fast parallel algorithm for determining all roots of a polynomial with real roots",\r
-  journal = " Int: Proc of ACM",\r
-  volume =  "",\r
-  number =  "",\r
-  pages =   "340-349",\r
-  year =    "1968",\r
-  author =  "M. Ben-Or AND E. Feig AND D. Kozzen AND P. Tiwary",\r
-}x\r
-\r
-@Article{Riceall06,\r
-  title =   "  A highly parallel algorithm for root extraction",\r
-  journal = " IEEE Trans Comp",\r
-  volume =  "38",\r
-  number =  "3",\r
-  pages =   "443-449",\r
-  year =    "2006",\r
-  author =  "TA. Rice AND LH. Jamieson",\r
-}x\r
-\r
-@Article{Cosnard90,\r
-  title =   " Finding the roots of a polynomial on an MIMD multicomputer",\r
-  journal = " Parallel Comput",\r
-  volume =  "15",\r
-  number =  "3",\r
-  pages =   "75-85",\r
-  year =    "1990",\r
-  author =  "M. Cosnard AND P. Fraigniaud",\r
-}x\r
-\r
-@Article{Janall99,\r
-  title =   " Efficient parallel algorithms for finding polynomial zeroes",\r
-  journal = "Proc of the 6th int conference on advance computing, CDAC, Pune University Campus,India",\r
-  volume =  "15",\r
-  number =  "3",\r
-  pages =   "189-196",\r
-  year =    "1999",\r
-  author =  "PK. Jana AND BP. Sinha AND R. Datta Gupta",\r
-}x\r
-\r
-@Article{Jana06,\r
-  title =   " Polynomial interpolation and polynomial root finding on OTIS-Mesh",\r
-  journal = " Parallel Comput",\r
-  volume =  "32",\r
-  number =  "3",\r
-  pages =   "301-312",\r
-  year =    "2006",\r
-  author =  "PK. Jana",\r
-}x\r
-@Article{Kalantari08,\r
-  title =   " Polynomial root finding and polynomiography.",\r
-  journal = " World Scientifict,New Jersey",\r
-  volume =  "",\r
-  number =  "",\r
-  pages =   "",\r
-  year =    "",\r
-  author =  "B. Kalantari",\r
-}x\r
-\r
-@Article{Gemignani07,\r
-  title =   " Structured matrix methods for polynomial root finding.",\r
-  journal = " n: Proc of the 2007 Intl symposium on symbolic and algebraic computation",\r
-  volume =  "",\r
-  number =  "",\r
-  pages =   "175-180",\r
-  year =    "2007",\r
-  author =  "L. Gemignani",\r
-}x\r
-\r
-\r
-\r
-@Article{Skachek08,\r
-  title =   " Structured matrix methods for polynomial root finding.",\r
-  journal = " n: Proc of the 2007 Intl symposium on symbolic and algebraic computation",\r
-  volume =  "",\r
-  number =  "",\r
-  pages =   "175-180",\r
-  year =    "2008",\r
-  author =  "V. Skachek",\r
-}x\r
-\r
-@BOOK{Skachek008,\r
-  AUTHOR =       {V. Skachek},\r
-  editor =       {\7f},\r
-  TITLE =        {Probabilistic algorithm for finding roots of linearized polynomials},\r
-  PUBLISHER =    {codes and cryptography. Kluwer},\r
-  YEAR =         {2008},\r
-  volume =       {\7f},\r
-  number =       {\7f},\r
-  series =       {\7f},\r
-  address =      {\7f},\r
-  edition =      {Design},\r
-  month =        {\7f},\r
-  note =         {\7f},\r
-  abstract =     {\7f},\r
-  isbn =         {\7f},\r
-  price =        {\7f},\r
-  keywords =     {\7f},\r
-  source =       {\7f},\r
-}x\r
-\r
-@Article{Zhancall08,\r
-  title =   " A constrained learning algorithm for finding multiple real roots of polynomial",\r
-  journal = " In: Proc of the 2008 intl symposium on computational intelligence and design",\r
-  volume =  "",\r
-  number =  "",\r
-  pages =   "38-41",\r
-  year =    "2008",\r
-  author =  "X. Zhanc AND M. Wan,Z.Yi",\r
-}x\r
-\r
-\r
-@Article{Zhuall08,\r
-  title =   " an adaptive algorithm finding multiple roots of polynomials",\r
-  journal = " Lect Notes Comput Sci ",\r
-  volume =  "",\r
-  number =  "5262",\r
-  pages =   "674-681",\r
-  year =    "2008",\r
-  author =  "W. Zhu AND w. Zeng AND D. Lin",\r
-}x\r
-@Article{Azad07,\r
-  title =   " The performance of synchronous parallel polynomial root extraction on a ring multicomputer",\r
-  journal = " Clust Comput ",\r
-  volume =  "2",\r
-  number =  "10",\r
-  pages =   "167-174",\r
-  year =    "2007",\r
-    author =  "HS. Azad",\r
-}x\r
-\r
-\r
-\r
-\r
-@Article{Bini04,\r
-  title =   " Inverse power and Durand Kerner iterations for univariate polynomial root finding",\r
-  journal = " Comput Math Appl ",\r
-  volume =  "",\r
-  number =  "47",\r
-  pages =   "447-459",\r
-  year =    "2004",\r
-  author =  "DA. Bini AND L. Gemignani",\r
-}x\r
-\r
-@Article{Jana99,\r
-  title =   " Finding polynomial zeroes on a Multi-mesh of trees (MMT)",\r
-  journal = " In: Proc of the 2nd int conference on information technology",\r
-  volume =  "",\r
-  number =  "",\r
-  pages =   "202-206",\r
-  year =    "1999",\r
-  author =  "PK. Jana",\r
-}x\r
-\r
-@Article{Weierstrass03,\r
-  title =   " Neuer Beweis des Satzes, dass jede ganze rationale function einer veranderlichen dagestellt werden kann als ein product aus linearen functionen derselben veranderlichen",\r
-  journal = " Ges. Werke",\r
-  volume =  "3",\r
-  number =  "",\r
-  pages =   "251-269",\r
-  year =    "1903",\r
-  author =  "K. Weierstrass",\r
-}x\r
-\r
-\r
-\r
-@BOOK{NVIDIA10,\r
-  AUTHOR =       {NVIDIA},\r
-  editor =       {Design Guide},\r
-  TITLE =        {NVIDIA CUDA C Programming Guide},\r
-  PUBLISHER =    {PG},\r
-  YEAR =         {2015},\r
-  volume =       {7},\r
-  number =       {02829},\r
-  series =       {001},\r
-  month =        {march},\r
-}x\r
+@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 =       {\7f},
+  TITLE =        {Probabilistic algorithm for finding roots of linearized polynomials},
+  PUBLISHER =    {codes and cryptography. Kluwer},
+  YEAR =         {2008},
+  volume =       {\7f},
+  number =       {\7f},
+  series =       {\7f},
+  address =      {\7f},
+  edition =      {Design},
+  month =        {\7f},
+  note =         {\7f},
+  abstract =     {\7f},
+  isbn =         {\7f},
+  price =        {\7f},
+  keywords =     {\7f},
+  source =       {\7f},
+}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 c8a669875ef7f21354062b4e62411a0c98328977..9897244a20b19a6506dc8eeb096f446bec2fbf4d 100644 (file)
--- 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]