Abstract
Support graph preconditioning is a relatively new technique that has gained attention in recent years. Unlike incomplete factorization-based preconditioning, this is a robust technique whose performance is not affected significantly by domain characteristics such as anisotropy and inhomogeneity. A major limitation of this technique is that it is applicable to symmetric diagonally dominant M-matrices only. In this paper, we outline an extension of the technique to symmetric positive definite matrices arising from finite element discretization of elliptic problems. An added advantage of our approach is the inherent parallelism that can be exploited to develop efficient parallel preconditioners. Our method allows trade-off between the preconditioner’s parallelism and the rate of convergence of the iterative solver. In contrast, efforts to parallelize incomplete factorization-based preconditioners often result in much slower convergence. Numerical results show that our preconditioner achieves good parallel speedup on distributed memory multiprocessors such as Beowulf workstation clusters.
This research has been supported by NSF grants CCR 9984400, CCR 0431068, CCR 0427014, and DMS 0216275.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Boman, E.G., Hendrickson, B.: Support theory for preconditioning. SIAM J. Matrix Anal. Appl. 25(3), 694–717 (2004)
Boman, E.G., Chen, D., Hendrickson, B., Toledo, S.: Maximum-weight-basis preconditioners. Lin. Alg. Appl. 11, 695–721 (2004)
Boman, E.G., Hendrickson, B., Vavasis, S.: Solving elliptic finite element systems in near-linear time with support preconditioners (submitted, 2004)
Chen, D., Toledo, S.: Vaidya’s preconditioners: Implementation and experimental study. Electronic Transactions on Numerical Analysis 16, 30–49 (2003)
Chen, D.: Analysis, Implemetation and Evaluation of Vaidya’s Preconditioners. Master’s thesis, School of Computer Science, Tel-Aviv University, Israel (February 2001)
Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorihtms, 2nd edn. McGraw-Hill, New York (2001)
George, A., Liu, J.W.-H.: Computer solution of large sparse positive definite systems. Prentice-Hall, Englewood Cliffs (1981)
Gremban, K.D., Miller, G.L., Zagha, M.: Performance evaluation of a parallel preconditioner. In: 9th International Parallel Processing Symposium, Santa Barbara, April 1995, pp. 65–69. IEEE, Los Alamitos (1995)
Gremban, K.D.: Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems. PhD thesis, School of Computer Science, Carnegie Mellon University (October 1996)
Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003)
Vaidya, P.: Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. In: A talk based on the manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation (October 1991) (unpublished manuscript)
Wu, X., Downes, M.S., Goktekin, T., Tendick, F.: Adaptive nonlinear finite elements for deformable body simulation using dynamic progressive meshes. In: Chalmers, A., Rhyne, T.-M. (eds.) EG 2001 Proceedings, vol. 20(3), pp. 349–358. Blackwell Publishing, Malden (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, M., Sarin, V. (2006). Parallel Support Graph Preconditioners. In: Robert, Y., Parashar, M., Badrinath, R., Prasanna, V.K. (eds) High Performance Computing - HiPC 2006. HiPC 2006. Lecture Notes in Computer Science, vol 4297. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11945918_39
Download citation
DOI: https://doi.org/10.1007/11945918_39
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68039-0
Online ISBN: 978-3-540-68040-6
eBook Packages: Computer ScienceComputer Science (R0)