Abstract
To solve large systems of linear equations with sparse matrices in parallel, there are three factors that contribute to the com- puting time: the numerical efficiency, the floating point performance, and the scalability. In this paper, we mainly consider the floating point performance. For large linear systems, multi-level techniques, like the cascadic conjugate gradient method (CCG), require significantly less operations than single-level methods. On the other hand, they are considered less efficient with regard to performance and limited in parallelization. Therefore, to achieve an efficient, massively parallel multi-level solver, we used the fastest available communication and revised the whole computation. The performance improvements led to a parallel solver which is able to solve a linear system with more than 16 million unknowns in 0.77 seconds on 256 PEs of Cray T3E. This corresponds to an overall performance of 10.34 GFLOPS.
Part of the work was done while the author was a research associate at ZHR in 1999.
Chapter PDF
Keywords
References
Manfred Alef. Implementation of a multigrid algorithm on suprenum and other systems. Parallel Computing, 20:1547–1557, 1994.
Peter Deuflhard. Cascadic conjugate gradient methods for elliptic partial differential equations, algorithm and numerical results. In D. Keyes and J. Xu, editors, Proc. of the 7th Int. Conf. on Domain Decomp. Methods 1993, pages 29–42, 1994.
Jack J. Dongarra, Iain S. Duff, Danny C. Sorensen, and Henk A. van der Vorst. Numerical Linear Algebra for High-Performance Computers. SIAM, Philadelphia, 1998.
Kevin Dowd and Charles R. Severance. High Performance Computing. O’Reilly, Sebastopol, second edition, 1998.
Peter Gottschling. Efficient parallel computation of the discretized ground-water flow equation with algebraic multigrid methods (in german). Phd thesis, TU Dresden, in preparation.
Uwe Lehmann. Festigkeitsuntersuchung von Eisenbahnfahrwegen auf Parallelrechnern. Diplom, TU Dresden, 1999.
W.E. Nagel and A. Arnold. Performance visualization of environment. Technical report, Forschungszentrum Jülich, 1995. http://www.fz-juelich.de/zam/PT/ReDec/SoftTools/PARtools/PARvis.html.
Wolfgang E. Nagel. The new massively parallel computer cray t3e in spring 1996: Experience with virginity (in german). In Hans-Werner Meuer, editor, Supercomputer 1996, pages 92–107. K. G. Saur, 1996.
Stephan Seidl. Code crumpling: A straight technique to improve loop performance on cache based systems. In Proc. 5th Eur. SGI/Cray MPP Workshop, 1999.
J. Stiller, K. Boryczko, and W.E. Nagel. A new approach for parallel multigrid adaption. In Proc. 9th SI AM Conf. on Par. Proc. for Sci. Comp., 1999.
Todd Veldhuizen et al. Blitz++. http://www://oonumerics.org/blitz/.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gottschling, P., Nagel, W.E. (2000). An Efficient Parallel Linear Solver with a Cascadic Conjugate Gradient Method: Experience with Reality. In: Bode, A., Ludwig, T., Karl, W., Wismüller, R. (eds) Euro-Par 2000 Parallel Processing. Euro-Par 2000. Lecture Notes in Computer Science, vol 1900. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44520-X_109
Download citation
DOI: https://doi.org/10.1007/3-540-44520-X_109
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67956-1
Online ISBN: 978-3-540-44520-3
eBook Packages: Springer Book Archive