Using Random Butterfly Transformations in Parallel Schur Complement-Based Preconditioning

• Autorzy: Marc Baboulin , Aygul Jamal , Masha Sosonkina
• Języki publikacji: EN

Abstrakty

EN

We propose to use a randomization technique based on Random Butterfly Transformations (RBT) in the Algebraic Recursive Multilevel Solver (ARMS) to improve the preconditioning phase in the iterative solution of sparse linear systems. We integrated the RBT technique into the parallel version of ARMS (pARMS). The preliminary experimental results on some matrices from the Davis' collection show an improvement of the convergence and accuracy of the results when compared with existing implementations of the pARMS preconditioner. (original abstract)

Słowa kluczowe

EN

Random Matrix Theory (RMT)

PL

Teoria macierzy przypadkowych

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2015
• Tom: 5
• Strony: 649--654

Twórcy

autor

Marc Baboulin

• Université Paris-Sud

autor

Aygul Jamal

• Université Paris-Sud

autor

Masha Sosonkina

• Old Dominion University Norfolk, United States

Bibliografia

• A. Buttari, J. Langou, J. Kurzak, J. Dongarra, A class of parallel tiled linear algebra algorithms for multicore architectures, Parallel Comput. 35 (1) (2009) 38-53.
• S. Tomov, J. Dongarra, M. Baboulin, Towards dense linear algebra for hybrid GPU accelerated manycore systems, Parallel Computing 36 (5&6) (2010) 232-240.
• T. A. Davis, Direct Methods for Sparse Linear Systems (Fundamentals of Algorithms 2), Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2006.
• Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd Edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2003.
• N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd Edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2002.
• M. Baboulin, J. Dongarra, J. Herrmann, S. Tomov, Accelerating linear system solutions using randomization techniques, ACM Trans. Math. Softw. 39 (2) (2013) 8:1-8:13.
• D. S. Parker, Random butterfly transformations with applications in computational linear algebra, Tech. Rep. CSD-950023, University of California Los Angeles, CA USA (1995).
• M. Baboulin, D. Becker, G. Bosilca, A. Danalis, J. Dongarra, An efficient distributed randomized algorithm for solving large dense symmetric indefinite linear systems, Parallel Computing 40 (7) (2014) 213- 223.
• M. Arioli, J. Demmel, I. Duff, Solving sparse linear systems with sparse backward error, SIAM Journal on Matrix Analysis and Applications 10 (2) (1989) 165-190.
• B. N. Bond, L. Daniel, Guaranteed stable projection-based model reduction for indefinite and unstable linear systems, in: Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, ICCAD '08, IEEE Press, Piscataway, NJ, USA, 2008, pp. 728- 735.
• S. Donfack, J. Dongarra, M. Faverge, M. Gates, J. Kurzak, P. Luszczek, I. Yamazaki, A Survey of Recent Developments in Parallel Implementations of Gaussian Elimination, Concurrency and Computation: Practice and Experience (2014) 18.
• Y. Saad, B. Suchomel, ARMS: an algebraic recursive multilevel solver for general sparse linear systems, Numerical Linear Algebra with Applications 9 (5) (2002) 359-378.
• Y. Bai, W. N. Gansterer, R. C. Ward, Block tridiagonalization of "effectively" sparse symmetric matrices, ACM Trans. Math. Softw. 30 (3) (2004) 326-352.
• Z.-H. Cao, Constraint schur complement preconditioners for nonsymmetric saddle point problems, Appl. Numer. Math. 59 (1) (2009) 151- 169.
• Z. Li, Y. Saad, M. Sosonkina, pARMS: a parallel version of the algebraic recursive multilevel solver, Numerical Linear Algebra with Applications 10 (5-6) (2003) 485-509.
• Y. Saad, M. Sosonkina, Non-standard parallel solution strategies for distributed sparse linear systems, in: P. Z. et al. (Ed.), Parallel Computation: 4th International ACPC Conference, Vol. 1557 of Lecture Notes in Computer Science, Springer-Verlag, 1999, pp. 13-27.
• B. F. Smith, P. E. Bjørstad, W. D. Gropp, Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press, New York, NY, USA, 1996.
• Y. Saad, M. Sosonkina, Distributed Schur Complement techniques for general sparse linear systems, SIAM J. Scientific Computing 21 (1999) 1337-1356.
• X.-C. Cai, M. Sarkis, A restricted additive schwarz preconditioner for general sparse linear systems, SIAM J. Sci. Comput. 21 (2) (1999) 792- 797.
• Z. Li, Y. Saad, Schurras: A restricted version of the overlapping schur complement preconditioner, SIAM J. Sci. Comput. 27 (5) (2005) 1787- 1801.
• M. Baboulin, X. S. Li, F.-H. Rouet, Using random butterfly transformations to avoid pivoting in sparse direct methods, in: Proceedings of VECPAR 2014, 2014.
• M. Baboulin, S. Donfack, J. Dongarra, L. Grigori, A. Rémy, S. Tomov, A class of communication-avoiding algorithms for solving general dense linear systems on cpu/gpu parallel machines, in: International Conference on Computational Science (ICCS 2012), Vol. 9 of Procedia Computer Science, Elsevier, 2012, pp. 17-26.
• E. Andersen, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, A. Greenbaum, S. Hammarling, A. McKenney, S. Ostrouchev, D. Sorensen, LAPACK user's guide, 3rd. Ed. 1999 SIAM, Philadelphia (1999).
• T. A. Davis, Y. Hu, The University of Florida Sparse Matrix Collection, ACM Trans. Math. Softw. 38 (1) (2011) 1-25.
• X. S. Li, An overview of SuperLU: Algorithms, implementation, and user interface, ACM Transactions on Mathematical Software 31 (3) (2005) 302-325.

Identyfikatory

DOI

10.15439/2015F177