Study of structural properties of Cholesky decomposition: from well?known facts to new conclusions

Abstract

 As a part of Open Encyclopedia of Algorithms’ Properties (AlgoWiki) development the properties of parallel  algorithm of Cholesky decomposition for symmetric positive definite matrices has been studied. Based on  algorithm graph analysis a description of this algorithm parallel  properties is given as well  as locality  properties of memory  access are analyzed. Resulted from numerical experiments  on Lomonosov  supercomputer research data of a scalability for Cholesky decomposition straightforward implementations  allows to give several suggestions as regards dimension ratio of tasks and resources required for their  solution. Theoretical studies give an opportunity both to explain relatively low performance of this method  pointwise  implementation and to reassess some approaches accepted by the scientific society more than  half a  century ago as  well as to re?evaluate them from the contemporary computer facilities point of view.