Parallel algorithms for finding polynomial Roots on OTIS-torus
Tóm tắt
We present two parallel algorithms for finding all the roots of an N-degree polynomial equation on an efficient model of Optoelectronic Transpose Interconnection System (OTIS), called OTIS-2D torus. The parallel algorithms are based on the iterative schemes of Durand–Kerner and Ehrlich methods. We show that the algorithm for the Durand–Kerner method requires (N
0.75+0.5N
0.25−1) electronic moves + 2(N
0.5−1) OTIS moves using N processors. The parallel algorithm for Ehrlich method is shown to run in (N
0.75+0.5N
0.25−1) electronic moves + 2(N
0.5−1) OTIS moves with the same number of processors. The algorithms have lower AT cost than the algorithms presented in Jana (Parallel Comput 32:301–312, 2006). The scalability of the algorithms is also discussed.
Tài liệu tham khảo
Aberth O (1973) Iteration method for finding zeros of a polynomial simultaneously. Math Comput 27:339–344
Akl SG (1985) Parallel sorting algorithm. Academic Press, Orlando
Anderson E, Brooks J, Gassl C, Scott S (1997) Performance of the Cray T3E. In: Proc of supercomputing conference, San Jose, California, USA
Arabnia HR (1993) In: Atkins S, Wagner AS (eds) A transputer-based reconfigurable parallel system, transputer research and applications (NATUG 6). IOS Press, Vancouver, pp 153–169
Arif Wani M, Arabnia HR (2003) Parallel edge-region-based segmentation algorithm targeted at reconfigurable multi-ring network. J Supercomput 25(1):43–63
Azad HS (2007) The performance of synchronous parallel polynomial root extraction on a ring multicomputer. Clust Comput 10(2):167–174
Ben-Or M, Feig E, Kozzen D, Tiwary P (1968) A fast parallel algorithm for determining all roots of a polynomial with real roots. In: Proc of ACM, pp 340–349
Bhandarkar SM, Arabnia HR (1995) The REFINE multiprocessor theoretical properties and algorithms. Parallel Comput 21(11):1783–1806
Bini DA, Gemignani L (2004) Inverse power and Durand–Kerner iterations for univariate polynomial root-finding. Comput Math Appl 47:447–459
Bose B, Broeg B, Kwon Y, Ashir Y (1995) Lee distance and topological properties of k- ary n-cubes. IEEE Trans Comput 44:1021–1030
Cosnard M, Fraigniaud P (1990) Finding the roots of a polynomial on an MIMD multicomputer. Parallel Comput 15:75–85
Day K (2002) Topological properties of OTIS-Networks. IEEE Trans Parallel Distr Syst 13:359–366
Durand E (1960) Solutions numeriques des equations algebriques, vol I. Mason, Paris
Ehrlich LW (1967) A modified Newton method for polynomials. Commun ACM 10:107–108
Freeman TL (1989) Calculating polynomial zeros on local memory parallel computer. Parallel Comput 12:351–358
Freeman TL, Bane MK (1991) Asynchronous polynomial zero-finding algorithms. Parallel Comput 17:673–681
Gemignani L (2007) Structured matrix methods for polynomial root finding. In: Proc of the 2007 Intl symposium on symbolic and algebraic computation, pp 175–180
Guggenheimer H (1986) Initial approximation in Durand–Kerner’s root finding method. BIT 26:537–539
Hildebrand FB (1956) Introduction to numerical analysis. McGraw-Hill, New York
Jana PK (2006) Polynomial interpolation and polynomial root finding on OTIS-Mesh. Parallel Comput 32:301–312
Jana PK (1999) Finding polynomial zeroes on a Multi-mesh of trees (MMT). In: Proc of the 2nd int conference on information technology, Bhubaneswar, December 20–22, pp 202–206
Jana PK, Sinha BP (2006) An improved parallel prefix algorithm on OTIS-Mesh. Parallel Proc Lett 16:429–440
Jana PK, Sinha BP (1998) Fast parallel algorithm for Graeffe’s root squaring technique. Comput Math Appl 35:71–80
Jana PK, Sinha BP, Datta Gupta R (1999) Efficient parallel algorithms for finding polynomial zeroes. In: Proc of the 6th int conference on advance computing, CDAC, Pune University Campus, India, December 14–16, pp 189–196
Kalantari B (2008) Polynomial root finding and polynomiography. World Scientific, New Jersey
Kerner IO (1966) Ein Gesamtschrittverfahren Zur Berechnung der Nullstetten on polynomen. Numer Math 8:290–294
Kessler RE, Schwarzmeier JL (1993) CRAY T3D: A new dimension for Cray research. CompCon, Houston, pp 176-182
Marsden G, Marchand P, Harvey P, Esener S (1993) Optical transpose interconnection system architectures. Optic Lett 18(13):1083–1085
Mirankar WL (1968) Parallel methods for approximating the roots of a function. IBM Res Dev 297–301
Mirankar WL (1971) A survey of parallelism in numerical analysis. SIAM Rev 524–547
Noakes M et al (1993) The J-machine multicomputer: an architectural evaluation. In: Proc of the 20th int symposium on computer architecture
Rajasekaran S, Sahni S (1998) Randomized routing, selection and sorting on the OTIS-Mesh. IEEE Trans Parallel Distr Syst 9:833–840
Rice TA, Jamieson LH (1989) A highly parallel algorithm for root extraction. IEEE Trans Comp 38(3):443–449
Sahni S (2001) Models and algorithms for optical and optoelectronic parallel computers. Int J Found Comput Sci 12(13):249–264
Sahni S, Wang CF (1998) BPC permutations on the OTIS hypercube optoelctronic computer. Informatica 263–269
Schedler GS (1967) Parallel numerical methods for the solution of equations. Commun ACM 286–290
Skachek V, Roth RM (2008) Probabilistic algorithm for finding roots of linearized polynomials. Design, codes and cryptography. Kluwer, Norwell
Wang CF, Sahni S (2001) Matrix Multiplication on the OTIS-Mesh optoelectronic computer. IEEE Trans Comput 50(7):635–646
Winogard S (1972) Parallel iteration methods in complexity of computer communications. Plenum, New York
Zane F, Marchand P, Paturi R, Esener S (2000) Scalable network architectures using the optical transpose interconnection system (OTIS). J Parallel Distr Comput 60:521–538
Zhanc X, Wan M, Yi Z (2008) A constrained learning algorithm for finding multiple real roots of polynomial. In: Proc of the 2008 intl symposium on computational intelligence and design, pp 38–41
Zhu W, Zeng Z, Lin D (2008) An adaptive algorithm finding multiple roots of polynomials. Lect Notes Comput Sci 5262:674–681