Computational Technology Resources - CCC

H. Liu^1,2, F. Magoules^3,4 and Q. Zou^1,2

¹School of Science, Beijing University of Posts and Telecommunications, Beijing, China
²Key Laboratory of Mathematics and Information Networks (Beijing University of Posts and Telecommunications), Ministry of Education, China
³Universite Paris-Saclay, CentraleSupelec, MICS, Gif-sur-Yvette, France
⁴Faculty of Engineering and Information Technology, University of Pecs, Pecs, Hungary

doi:10.4203/ccc.4.3.3

H. Liu, F. Magoules, Q. Zou, "Avoiding Communication in Two-Sided Krylov Subspace Methods", in P. Iványi, F. Magoulès, B.H.V. Topping, (Editors), "Proceedings of the Seventh International Conference on Parallel, Distributed, GPU and Cloud Computing for Engineering", Civil-Comp Press, Edinburgh, UK, Online volume: CCC 4, Paper 3.3, 2023, doi:10.4203/ccc.4.3.3

Keywords: quasi-minimal residual algorithm, communication-avoiding strategy, iterative methods, parallel algorithms.

Abstract

Krylov subspace methods play an important role in solving large, sparse linear systems in varieties of scientific fields. Specifically, their parallel variants are widely used in engineering. Classical Krylov subspace methods in parallel scenarios usually require many data communication between different processors per iteration which increases runtime of the algorithms and create a performance bottleneck. Besides, the cost of communication is much more expensive than the cost of computation on modern computer architecture. Therefore, we present two communication-avoiding Krylov subspace methods, namely communication-avoiding quasi-minimal residual algorithm (CA-QMR) and communication-avoiding transpose free quasi-minimal residual algorithm (CA-TFQMR). In practical applications, we reduce the communication demand to one data movement every O(s) iterations in the classical two-sided iterated algorithms. Moreover, we have incorporated restart strategy into our algorithms which significantly reduces storage requirements. Experimental results are presented to show that our algorithms reduce communication consumption and the data storage within the allowable range of convergence accuracy.

download the full-text of this paper (PDF, 10 pages, 249 Kb)

go to the previous paper
go to the next paper
return to the table of contents
return to the volume description

	Computational & Technology Resources an online resource for computational, engineering & technology publications
	not logged in - login
Front Page Browse CCC CCP CSETS CTR IJRT Other Authors Search Purchase Guide FAQ Contact us	Civil-Comp Conferences ISSN 2753-3239 CCC: 4 PROCEEDINGS OF THE SEVENTH INTERNATIONAL CONFERENCE ON PARALLEL, DISTRIBUTED, GPU AND CLOUD COMPUTING FOR ENGINEERING Edited by: P. Iványi, F. Magoulès and B.H.V. Topping Paper 3.3 Avoiding Communication in Two-Sided Krylov Subspace Methods H. Liu^1,2, F. Magoules^3,4 and Q. Zou^1,2 ¹School of Science, Beijing University of Posts and Telecommunications, Beijing, China ²Key Laboratory of Mathematics and Information Networks (Beijing University of Posts and Telecommunications), Ministry of Education, China ³Universite Paris-Saclay, CentraleSupelec, MICS, Gif-sur-Yvette, France ⁴Faculty of Engineering and Information Technology, University of Pecs, Pecs, Hungary doi:10.4203/ccc.4.3.3 Full Bibliographic Reference for this paper H. Liu, F. Magoules, Q. Zou, "Avoiding Communication in Two-Sided Krylov Subspace Methods", in P. Iványi, F. Magoulès, B.H.V. Topping, (Editors), "Proceedings of the Seventh International Conference on Parallel, Distributed, GPU and Cloud Computing for Engineering", Civil-Comp Press, Edinburgh, UK, Online volume: CCC 4, Paper 3.3, 2023, doi:10.4203/ccc.4.3.3 Keywords: quasi-minimal residual algorithm, communication-avoiding strategy, iterative methods, parallel algorithms. Abstract Krylov subspace methods play an important role in solving large, sparse linear systems in varieties of scientific fields. Specifically, their parallel variants are widely used in engineering. Classical Krylov subspace methods in parallel scenarios usually require many data communication between different processors per iteration which increases runtime of the algorithms and create a performance bottleneck. Besides, the cost of communication is much more expensive than the cost of computation on modern computer architecture. Therefore, we present two communication-avoiding Krylov subspace methods, namely communication-avoiding quasi-minimal residual algorithm (CA-QMR) and communication-avoiding transpose free quasi-minimal residual algorithm (CA-TFQMR). In practical applications, we reduce the communication demand to one data movement every O(s) iterations in the classical two-sided iterated algorithms. Moreover, we have incorporated restart strategy into our algorithms which significantly reduces storage requirements. Experimental results are presented to show that our algorithms reduce communication consumption and the data storage within the allowable range of convergence accuracy. download the full-text of this paper (PDF, 10 pages, 249 Kb) go to the previous paper go to the next paper return to the table of contents return to the volume description
Back to top	©Civil-Comp Limited 2023 - terms & conditions