Concurrent Cholesky factorization of positive definite banded Hermitian‐matrices
Senol Utku, M. Salama, ROBERT J. MELOSH · International Journal for Numerical Methods in Engineering · 1986
Abstract First the Cholesky factorization is extended to cover uniformly partitioned banded positive definite matrices of rank n which may be real symmetric or Hermitian. Then two stratagems are given for the use of the algorithm in concurrent machines where the number of processing elements is less than required to factor the matrix in as few serial steps as possible, and where uniformly high efficiency is expected from all processing elements. Expressions are given for the efficiency factor e appearing in the speed‐up expression g = eN, and these are specialized for the N node hypercube machine as a function of partition size s, the number N of processing elements of the hypercube machine, and the cost μ of interelement transmission relative to computation. It is shown that efficiency factor e is inversely proportional to μ/s, and that e is almost independent of N when N is large and μ/s = 0. The task is completed in n/s serial steps with no limit on n. The half bandwidth b of the matrix is 2Ns.