Parallel Algorithm for Symmetric Positive Definite Banded Linear Systems: A Divide and Conquer Approach

摘要

The WZ factorization for the solution of symmetric positive definite banded linear systems when combined with a partitioned scheme, renders a divide and conquer algorithm. The WZ factorization of the coefficient matrix in each block has the properties: the vector [a_1,...,a_β,0,...,0,a_(n-β+1),...,a_n]~T is invariant under the transformation W where β is the semibandwidth of the coefficient matrix and the solution process with the coefficient matrix Z proceeds from the first and the last unknowns to the middle. These properties of WZ factorization help us to decouple the partitioned system for the parallel execution once the 'reduced system' is solved.