The Parallel Solution Method of Sparse Triangular System Based on Correlation Decomposition

Abstract

We propose a parallel solution algorithm based on correlation decomposition. By decomposing the right-hand-side of the linear system and analyzing the dependencies of the variable solution to form multiple independent variable calculation paths. First, the partial value of the variable is calculated in parallel, and then the final result of the variable is calculated by adding the partial value of the variable. Since the variables are calculated without waiting for all the precursor variable to complete the calculation, which greatly improves the parallelism and calculation speed, and communication between multiple parallel tasks only once, which reduces synchronization overhead.