Abstract
The mathematical foundation of an algorithm for fast and accurate evaluation of singular integral transforms was given by Daripa [9,10,12]. By construction, the algorithm offers good parallelization opportunities and a lower computational complexity when compared with methods based on quadrature rules. In this paper we develop a parallel version of the fast algorithm by redefining the inherently sequential recurrences present in the original sequential formulation. The parallel version only utilizes a linear neighbor-to-neighbor communication path, which makes the algorithm very suitable for any distributed memory architecture. Numerical results and theoretical estimates show good parallel scalability of the algorithm.
Similar content being viewed by others
References
F. Argü ello, M. Amor and E. Zapata, FFTs on mesh connected computers, Parallel Comput. 22 (1996) 19-38.
L. Bers, Mathematical Aspects of Subcritical and Transonic Gas Dynamics (Wiley, New York, 1958).
L. Bers and L. Nirenberg, On a representation theorem for linear elliptic systems with discontinuous coefficients and its applications, in: Convegno Internazionale Suelle Equaziono Cremeonese, Roma (1955) pp. 111-140.
L. Bers and L. Nirenberg, On linear and nonlinear elliptic boundary value problems in the plane, in: Convegno Internazionale Suelle Equaziono Cremeonese, Roma (1955) pp. 141-167.
W. Briggs, L. Hart, R. Sweet and A. O'Gallagher, Multiprocessor FFT methods, SIAM J. Sci. Statist. Comput. 8 (1987) 27-42.
C. Calvin, Implementation of parallel FFT algorithms on distributed memory machines with a minimum overhead of communication, Parallel Comput. 22 (1996) 1255-1279.
R. Courant and D. Hilbert, Methods of Mathematical Physics, Vol. II (Wiley, New York, 1961).
P. Daripa, On applications of a complex variable method in compressible flows, J. Comput. Phys. 88 (1990) 337-361.
P. Daripa, A fast algorithm to solve nonhomogeneous Cauchy-Riemann equations in the complex plane, SIAM J. Sci. Statist. Comput. 6 (1992) 1418-1432.
P. Daripa, A fast algorithm to solve the Beltrami equation with applications to quasiconformal mappings, J. Comput. Phys. 106 (1993) 355-365.
P. Daripa and D. Mashat, An efficient and novel numerical method for quasiconformal mappings of doubly connected domains, Numer. Algorithms 18 (1998) 159-175.
P. Daripa and D. Mashat, Singular integral transforms and fast numerical algorithms, Numer. Algorithms 18 (1998) 133-157.
R. Hockney and C. Jesshope, Parallel Computers: Architecture, Programming and Algorithms (Adam Hilger, Bristol, 1981).
K. Hwang, Advanced Computer Architecture: Parallelism, Scalability, Programmability (McGraw-Hill, New York, 1993).
V. Kumar, A. Grama, A. Gupta and G. Karypis, Introduction to Parallel Computing (Benjamin/Cummings, Redwood City, CA, 1994).
J. Lawrynowicz, Quasiconformal mappings in the plane, in: Lecture Notes in Mathematics, Vol. 978 (Springer, New York, 1983).
C. Morrey, On the solutions of quasi-linear elliptic differential equations, Trans. Amer. Math. Soc. 43 (1938) 126-166.
A. Mshimba and W. Tutschke, Functional Analytic Methods in Complex Analysis and Applications to Partial Differential Equations (World Scientific, Singapore, 1990).
L. Nirenberg, On nonlinear elliptic differential equations and Holder continuity, Comm. Pure Appl. Math. 6 (1953) 103-156.
P. Pacheco, Parallel Programming with MPI (Morgan Kaufmann, San Francisco, CA, 1997).
D. Patterson and J. Hennessy, Computer Organization and Design: The Hardware/Software Interface (Morgan Kaufmann, San Francisco, CA, 1994).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Borges, L., Daripa, P. A parallel version of a fast algorithm for singular integral transforms. Numerical Algorithms 23, 71–96 (2000). https://doi.org/10.1023/A:1019143832124
Issue Date:
DOI: https://doi.org/10.1023/A:1019143832124