Premium
Concurrent Cholesky factorization of positive definite banded Hermitian‐matrices
Author(s) -
Utku S.,
Salama M.,
Melosh R. J.
Publication year - 1986
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/nme.1620231111
Subject(s) - cholesky decomposition , hermitian matrix , positive definite matrix , hypercube , mathematics , factorization , matrix (chemical analysis) , incomplete cholesky factorization , minimum degree algorithm , combinatorics , rank (graph theory) , computation , parallel computing , discrete mathematics , computer science , algorithm , eigenvalues and eigenvectors , pure mathematics , physics , materials science , quantum mechanics , composite material
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 2 Ns .