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)
 # 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)
 
 
 # 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}
 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}
 
 \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}
 \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}
 \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.
 
 \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}
 %%\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} 
 \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
 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
 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}
 
 
 \subsection{Comparative study}


@@ -678,7 +672,12 @@ We initially carried out the convergence of Aberth algorithm with various sizes
 \label{fig:01}
 \end{figure}
 
 \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]
 
 \subsubsection{A comparative study between Aberth and Durand-kerner algorithm}
 \begin{table}[htbp]