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.
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 |
Keywords:
Elbert’s conjecture; special functions; Bessel functions; computation of special functions; construction of tables of special functions; parallel and distributed algorithms; parallel virtual machine; zero isolation; Kronecker-Picard theory; topological degree theory; computing simple roots; bisection methods; roots of a system of equationsCitations:
Zbl 0989.33004References:
| [1] | P. Alexandroff, H. Hopf, Topologie, Springer, Berlin, 1935 (reprinted: Chelsea, Bronx, New York, 1965).; 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: 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.; 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, (Sincovec, R. F.; Keyes, D. E.; Leuze, M. R.; Petzold, L. R.; Reed, D. A., Proceedings of 6th SIAM Conference on Parallel Processing for Scientific Computing, Vol. 2 (1993), SIAM: SIAM Philadelphia), 531-538 · Zbl 0815.65030 |
| [10] | Lozier, D. W.; Olver, F. W.J., Numerical evaluation of special functions, (Gautschi, W., Mathematics of Computation 1943-1993: a half-century of computational mathematics. Mathematics of Computation 1943-1993: a half-century of computational mathematics, Proceedings of Symposia in Applied Mathematics, Vol. 48 (1994), AMS: AMS Providence, RI), 79-125 · Zbl 0815.65030 |
| [11] | Ortega, J. M.; Rheinbolt, W. C., Iterative Solution of Nonlinear Equations in Several Variables (1970), Academic Press: 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).; E. Picard, Traité d’analyse, 3rd Edition, Gauthier-Villars, Paris, 1922 (Chapter 4.7). · JFM 54.0450.09 |
| [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: 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
