CONCURRENT CHOLESKY FACTORIZATION OF POSITIVE DEFINITE BANDED HERMITIAN MATRICES

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 equals 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 mu of interelement transmission relative to computation. It is shown that efficiency factor e is inversely proportional to mu /s, and that e is almost independent of N when N is large and mu /s equals 0. The task is completed in n/s serial steps with no limit on n. The half bandwidth b of the matrix is 2Ns.