Parallel robust solution of triangular equations

Abstract

Triangular linear systems are central to the solution of general linear systems, the calculations of eigenvectors, and the solution of Sylvester matrix equations. In the absence of floating-point exceptions, simple substitution runs to completion and solves a system which is a small perturbation of the original system. If the matrix is well-conditioned, then the normwise relative error is small. However, there are well-conditioned triangular linear systems for which substitution fails due to overflow. The robust solvers xLATRS from LAPACK extend the set of linear systems which can be solved by dynamically scaling the solution and the right-hand side to avoid overflow [1]. These solvers are sequential and apply to systems with a single right hand-side. The LAPACK solvers for computing eigenvectors of matrices and matrix pencils in Schur form and solving triangular Sylvester equations are all derived from xLATRS. Previous efforts to create algorithms which are blocked, parallel and robust have meet with limited success [2]. In particular, the current ScaLAPACK solvers for computing eigenvectors from Schur forms are vulnerable to floating-point overflow. Recent advances have eliminated all of these problems [3, 4, 5, 6]. In this talk we explain the fundamental principles for solving triangular equations in parallel without suffering from floating point overflow and without significant performance degradation. Moreover, we exhibit well-conditioned linear systems, eigenvalue problems and triangular Sylvester matrix equations for which the computed solution exceeds the representational range unless the right-hand side and the solution are scaled dynamically. A small set of examples illustrate the dangers of underflow and the inherent limitations of dynamically scaling the right Research Seminars- BSC 2021-2022 62 hand side. The work has been done in collaboration with Mirko Myllykoski, Angelika Schwarz and Mirko Myllykoski. The techniques presented in this talk have been integrated into StarNEig, a new task-parallel library for solving standard and generalized eigenvalue problems which are dense and nonsymmetric [7, 8, 9]. [1] E. Anderson. Robust Triangular Solvers for Use in Condition Estimation. LAWN-36 1991. [2] M.R. Fahey. Parallel Eigenvalue and Eigenvector Routines. LAWN-153, 2001. [3] C.C.K. Mikkelsen, L. Karlsson. Blocked algorithms for robust solution of triangular linear systems. LNCS, Vol. 10777, 2018, pp. 66-78. [4] C.C.K. Mikkelsen, A.B. Schwarz, L. Karlsson. Parallel robust solution of triangular linear systems. Concurrency and Computation: Practice and Experience, Volume 31, 2019. [5] C.C.K. Mikkelsen, M. Myllykoski. Parallel Robust Computation of Generalized Eigenvectors of Matrix Pencils, Proc. PPAM 2019, LNCS, Vol. 12043, 2020, pp. 58-69. [6] A.B. Schwarz, C.C.K.Mikkelsen. Robust Task-Parallel Solution of the Triangular Sylvester Equation. Proc. PPAM 2019, LNCS, Vol. 12043, 2020, pp. 82-92. [7] StarNEig is freely available from https://nlafet.github.io/StarNEig/. [8] M. Myllykoski, C.C.K. Mikkelsen. Introduction to StarNEig – A Task-based Library for Solving Non-symmetric Eigenvalue Problems. Proc. PPAM 2019, LNCS, Vol. 12043, 2020, pp. 70-81. [9] M. Myllykoski, C.C.K. Mikkelsen. Task-based, GPU-accelerated and Robust Library for Solving Dense Nonsymmetric Eigenvalue Problems Concurrency and Computation: Practice and Experience, 33(11), 2021.