×

Locating and computing in parallel all the simple roots of special functions using PVM. (English) Zbl 0988.65024

Summary: An algorithm is proposed for locating and computing in parallel and with certainty all the simple roots of any twice continuously differentiable function in any specific interval. To compute with certainty all the roots, the proposed method is heavily based on the knowledge of the total number of roots within the given interval. To obtain this information we use results from topological degree theory and, in particular, the Kronecker-Picard approach. This theory gives a formula for the computation of the total number of roots of a system of equations within a given region, which can be computed in parallel.
With this tool in hand, we construct a parallel procedure for the localization and isolation of all the roots by dividing the given region successively and applying the above formula to these subregions until the final domains contain at the most one root. The subregions with no roots are discarded, while for the rest a modification of the well-known bisection method is employed for the computation of the contained root. The new aspect of the present contribution is that the computation of the total number of zeros using the Kronecker-Picard integral as well as the localization and computation of all the roots is performed in parallel use of the parallel virtual machine (PVM). PVM is an integrated set of software tools and libraries that emulates a general-purpose, flexible, heterogeneous concurrent computing framework on interconnected computers of varied architectures.
The proposed algorithm has large granularity and low synchronization, and is robust. It has been implemented and tested and our experience is that it can massively compute with certainty all the roots in a certain interval. Performance information from massive computations related to a recently proposed conjecture due to A. Elbert [ibid. 133, No. 1-2, 65-83 (2001; Zbl 0989.33004)] is reported.

MSC:

65D20 Computation of special functions and constants, construction of tables
33C10 Bessel and Airy functions, cylinder functions, \({}_0F_1\)
47H11 Degree theory for nonlinear operators
55M25 Degree, winding number
65H05 Numerical computation of solutions to single equations
65Y05 Parallel numerical computation
65Y20 Complexity and performance of numerical algorithms

Citations:

Zbl 0989.33004

Software:

GNOME; ZEAL; PVM; ELF; ZEBEC; RFSFNS; CHABIS
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] P. Alexandroff, H. Hopf, Topologie, Springer, Berlin, 1935 (reprinted: Chelsea, Bronx, New York, 1965).
[2] Elbert, Á., Some recent results on the zeros of Bessel functions and orthogonal polynomials, this issue, J. comput. appl. math., 133, 65-83, (2001) · Zbl 0989.33004
[3] Geist, A.; Beguelin, A.; Dongarra, J.; Jiang, W.; Manchek, R.; Sunderam, V., PVM: parallel virtual machine. A User’s guide and tutorial for networked parallel computing, (1994), MIT Press Cambridge · Zbl 0849.68032
[4] I. Joó, Exact controllability and oscillation properties of circular membranes, Dissertation for the title doctor of science, Budapest, 1992.
[5] Joó, I., On the control of a circular membrane I, Acta math. hungar., 61, 303-325, (1993) · Zbl 0790.93079
[6] Kravanja, P.; Ragos, O.; Vrahatis, M.N.; Zafiropoulos, F.A., ZEBEC: a mathematical software package for computing simple zeros of Bessel functions of real order and complex argument, Comput. phys. commun., 113, 220-238, (1998) · Zbl 0999.33003
[7] Kravanja, P.; Van Barel, M.; Ragos, O.; Vrahatis, M.N.; Zafiropoulos, F.A., ZEAL: a mathematical software package for computing zeros of analytic functions, Comput. phys. commun., 124, 212-232, (2000) · Zbl 0955.65033
[8] Lozier, D.W., Software needs in special functions, J. comput. appl. math., 66, 345-358, (1996) · Zbl 0855.65009
[9] Lozier, D.W.; Olver, F.W.J., Airy and Bessel functions by parallel integration of odes, (), 531-538 · Zbl 0815.65030
[10] Lozier, D.W.; Olver, F.W.J., Numerical evaluation of special functions, (), 79-125 · Zbl 0815.65030
[11] Ortega, J.M.; Rheinbolt, W.C., Iterative solution of nonlinear equations in several variables, (1970), Academic Press New York · Zbl 0241.65046
[12] Picard, E., Sur le nombre des racines communes à plusieurs équations simultanées, J. math. pure appl. (4 Sér.), 8, 5-24, (1892) · JFM 24.0090.01
[13] E. Picard, Traité d’analyse, 3rd Edition, Gauthier-Villars, Paris, 1922 (Chapter 4.7).
[14] Segura, J.; Gil, A., ELF and GNOME: two tiny codes to evaluate the real zeros of the Bessel functions of the first kind for real orders, Comput. phys. commun., 117, 250-262, (1999) · Zbl 1001.65022
[15] Sikorski, K., Bisection is optimal, Numer. math., 40, 111-117, (1982) · Zbl 0492.65027
[16] Sterling, T.L.; Salmon, J.; Becker, D.J.; Savarese, D.F., How to build a beowulf: A guide to implementation and application of PC clusters, (1999), MIT Press Cambridge
[17] Vrahatis, M.N., Solving systems of nonlinear equations using the nonzero value of the topological degree, ACM trans. math. software, 14, 312-329, (1988) · Zbl 0665.65052
[18] Vrahatis, M.N., CHABIS: A mathematical software package for locating and evaluating roots of systems of nonlinear equations, ACM trans. math. software, 14, 330-336, (1988) · Zbl 0709.65518
[19] Vrahatis, M.N., A short proof and a generalization of Miranda’s existence theorem, Proc. amer. math. soc., 107, 701-703, (1989) · Zbl 0695.55001
[20] Vrahatis, M.N.; Grapsa, T.N.; Ragos, O.; Zafiropoulos, F.A., On the localization and computation of zeros of Bessel functions, Z. angew. math. mech., 77, 467-475, (1997) · Zbl 0915.33001
[21] Vrahatis, M.N.; Ragos, O.; Skiniotis, T.; Zafiropoulos, F.A.; Grapsa, T.N., RFSFNS: a portable package for the numerical determination of the number and the calculation of roots of Bessel functions, Comput. phys. commun., 92, 252-266, (1995) · Zbl 0908.65010
[22] Vrahatis, M.N.; Ragos, O.; Skiniotis, T.; Zafiropoulos, F.A.; Grapsa, T.N., The topological degree theory for the localization and computation of complex zeros of Bessel functions, Numer. funct. anal. optim., 18, 227-234, (1997) · Zbl 0892.33002
[23] Vrahatis, M.N.; Ragos, O.; Zafiropoulos, F.A.; Grapsa, T.N., Locating and computing zeros of Airy functions, Z. angew. math. mech., 76, 419-422, (1996) · Zbl 0878.33001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.