کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431434 688540 2015 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Mixing LU and QR factorization algorithms to design high-performance dense linear algebra solvers
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Mixing LU and QR factorization algorithms to design high-performance dense linear algebra solvers
چکیده انگلیسی


• New hybrid algorithm combining stability of QR and efficiency of LU factorizations.
• Flexible threshold criteria to select LU and QR steps.
• Comprehensive experimental bi-criteria study of stability and performance.

This paper introduces hybrid LU–QR algorithms for solving dense linear systems of the form Ax=bAx=b. Throughout a matrix factorization, these algorithms dynamically alternate LU with local pivoting and QR elimination steps based upon some robustness criterion. LU elimination steps can be very efficiently parallelized, and are twice as cheap in terms of floating-point operations, as QR steps. However, LU steps are not necessarily stable, while QR steps are always stable. The hybrid algorithms execute a QR step when a robustness criterion detects some risk for instability, and they execute an LU step otherwise. The choice between LU and QR steps must have a small computational overhead and must provide a satisfactory level of stability with as few QR steps as possible. In this paper, we introduce several robustness criteria and we establish upper bounds on the growth factor of the norm of the updated matrix incurred by each of these criteria. In addition, we describe the implementation of the hybrid algorithms through an extension of the PaRSEC software to allow for dynamic choices during execution. Finally, we analyze both stability and performance results compared to state-of-the-art linear solvers on parallel distributed multicore platforms. A comprehensive set of experiments shows that hybrid LU–QR algorithms provide a continuous range of trade-offs between stability and performances.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 85, November 2015, Pages 32–46
نویسندگان
, , , , , ,