Abstract
We present a hybrid MPI/OpenMP parallel implementation for the eigenvalues of symmetric tridiagonal matrices on cluster of SMP’s environments. The algorithm is based on a divide-and-conquer method which uses the split-merge technique and Laguerre’s iteration. We study two different implementations of the algorithm: one based on MPI and the other based on a hybrid parallel paradigm with MPI/OpenMP. We take a coarse grain OpenMP approach to parallel implementation for solving the eigenvalues of symmetric tridiagonal submatrices within a SMP node. And dynamic work sharing is used in Laguerre’s iterations. This has two effects: first, the amount of synchronization has been reduced; secondly, this could have an effect on the load balance. In addition, we analyze the communication overhead on two different implementations. An experimental analysis on the DeepComp 6800 shows the hybrid algorithm performs good scalability.
This work is supported by the Chinese Hitech Program (863) “Supercomputing Grid Node Construction” (2002aa104540), and the Informatization Construction of Knowledge Innovation Project of the Chinese Academy of Sciences “Supercomputing Environment construction and Applications” (INF105-SCE).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Sameh, A., Kuck, D.: A parallel QR algorithm for symmetric tridiagonal matrices. IEEE tans. Comput. C-26, 81–91 (1977)
Arbenz, P., Gates, D., Sprenger, C.: A parallel implementation of the symmetric tridiagonal QR algorithm. In: Proc. Fourth Symp. On the Frontiers of Massively Parallel Computation. IEEE CS Press, Los Alamitos (1992)
Cuppen, J.J.M.: A divide and conquer method for symmetric tridiagonal eigenproblem. Numer. Mathematik 2(36), 177–195 (1981)
Wilkinson, J.H.: The Algebraic Eigenvalue Problem. Clarendon Press, Oxford (1965)
Li, T.Y., Zhang, H., Sun, X.H.: Parallel homotopy algorithm for the symmetric tridiagonal eigenvalue problem. SIAM J. Scientific and Statistical Comput. 12, 469–487 (1991)
Dongarra, J.J., Soorenson, D.C.: A Fully Parallel Algorithm for the symmetric Eigenvalue Problem. SIAM J.Sci.Stat. Comput. 8(2), s139–s154 (1987)
Dhillon, I.S., Fannm, G., Parlett, B.N.: Application of new algorithm for the symmetric eigenproblem to computational quantum chemistry. In: processings of the Eigen SIAM Conference on Parallel processing for Scientific Computing, Minneapolis, MN, March 1997. SIAM, Philadelphia (1997)
Dhillon, I.S., Parlett, B.N.: Multiple representations compute orthogonal eigenvertors of symmetric tridiagonal matrices. Lin. Alg. Appl. 387, 1–28 (2004)
Luong, P., Breshears, C.P., Ly, L.N.: Coastal ocean modeling of the U.S. west coast with multiblock grid and dual-level parallelism. In: Supercomputing 2001: High Performance Networking and Computing, SC 2001 (2001)
Pavani, R., De Ros, U.: Solving the tridiagonal symmetric eigenvalue problem on a transputer network. n. 146/p, Dipartimento di mathematica, Politecino di Milano (1994)
LI, T.Y., Zeng, Z.: Lagurre’s iteration in solving the symmetric tridiagonal eigenproblem. SIAM J. Scientific Comput. 15, 1145–1173 (1994)
Pavani, R., De Ros, U.: A Distributed divide-and-conquer approach to the parallel symmetric eigenvalue problem. In: Hertzberger, B., Serazzi, G. (eds.) HPCN-Europe 1995. LNCS, vol. 919. Springer, Heidelberg (1995)
Bova, S.W., Breshears, C., Cuicchi, C., Demirbilek, Z., Gabb, H.A.: Dual-level parallel analysis of harbor wave response using MPI and OpenMP. Int. J. High Perform Comput. Appl. 14, 49–64 (2000)
Trefftz, C., Huang, C.C., Li, T.Y., Zeng, Z.: A scalable eigenvalue solver for symmetric tridiagonal matrices. Parallel Computing 21, 1213–1240 (1995)
Cappello, F., Etiemble, D.: MPI versus MPI+OpenMP on the IBM SP for the NAS Benchmarks. In:Supercomputing 2000: High Performance Networking and Computing (SC 2000) (2000)
Loft, R.D., Thomas, S.J., Dennis, J.M.: Terascale spectral element dynamical core for atmospheric general circulation models. In: Supercomputing 2001: High Performance Networking and Computing, SC2001 (2001)
Crawford, C.H., Evangelinos, C., Newman, D., Karniadakis, G.E.: Parallel benchmarks of turbulence in complex geometries. Comput. Fluids 25, 677–698 (1996)
Henty, D.S.: Performance of hybrid message-passing and shared-memory parallelism for discrete element modeling. Supercomputing 2000: High Performance Networking and Computing, SC2000 (2000)
Dong, S.H., Em Karniadakis, G.: Dual-level parallelism for high-order CFD methods. Parallel Computing 30, 1–20 (2004)
Liu, W., Zheng, W.M., Zheng, X.W.: The concept of node-oriented speedup on SMP cluster. Computer engineering and design 21(5) (October 2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhao, Y., Chen, J., Chi, X. (2005). Solving the Symmetric Tridiagonal Eigenproblem Using MPI/OpenMP Hybrid Parallelization. In: Cao, J., Nejdl, W., Xu, M. (eds) Advanced Parallel Processing Technologies. APPT 2005. Lecture Notes in Computer Science, vol 3756. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11573937_19
Download citation
DOI: https://doi.org/10.1007/11573937_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29639-3
Online ISBN: 978-3-540-32107-1
eBook Packages: Computer ScienceComputer Science (R0)