2016/12/06 by Tobias Wicky, Wicky, Tobias, Edgar Solomonik +3
Computer Science · #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #G.4 #Matrix Theory and Algorithms #Parallel #Parallel Computing and Optimization Techniques #Polynomial and algebraic computation #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1612.01855
openalex publication_date 2016/12/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a new parallel algorithm for solving triangular systems with\nmultiple right hand sides (TRSM). TRSM is used extensively in numerical linear\nalgebra computations, both to solve triangular linear systems of equations as\nwell as to compute factorizations with triangular matrices, such as Cholesky,\nLU, and QR. Our algorithm achieves better theoretical scalability than known\nalternatives, while maintaining numerical stability, via selective use of\ntriangular matrix inversion. We leverage the fact that triangular inversion and\nmatrix multiplication are more parallelizable than the standard TRSM algorithm.\nBy only inverting triangular blocks along the diagonal of the initial matrix,\nwe generalize the usual way of TRSM computation and the full matrix inversion\napproach. This flexibility leads to an efficient algorithm for any ratio of the\nnumber of right hand sides to the triangular matrix dimension. We provide a\ndetailed communication cost analysis for our algorithm as well as for the\nrecursive triangular matrix inversion. This cost analysis makes it possible to\ndetermine optimal block sizes and processor grids a priori. Relative to the\nbest known algorithms for TRSM, our approach can require asymptotically fewer\nmessages, while performing optimal amounts of computation and communication in\nterms of words sent.\n