Parallel Processing Model for Cholesky Decomposition Algorithm in AlgoWiki Project


  • Alexander S. Antonov Moscow State University, Moscow
  • Alexey V. Frolov Institute of Numerical Mathematics of the Russian Academy of Sciences, Moscow
  • Hiroaki Kobayashi Tohoku University, Sendai
  • Igor N. Konshin Institute of Numerical Mathematics of the Russian Academy of Sciences, Moscow
  • Alexey M. Teplov Moscow State University, Moscow
  • Vadim V. Voevodin Moscow State University, Moscow
  • Vladimir V. Voevodin Moscow State University, Moscow



The comprehensive analysis of algorithmic properties of well-known. Cholesky decomposition was performed on the basis of multifold AlgoWiki technologies. There was performed a detailed analysis of information graph, data structure, memory access profile, computation locality, scalability and other algorithm properties, that allow us to demonstrate a lot of unevident properties split up. into machine-independent and machine-dependent subsets. A comprehension of the parallel algorithm structure provide us with the possibility to efficiently implement the algorithm at hardware platform specified.


Voevodin, V., Antonov, A., Dongarra, J.: AlgoWiki: an Open Encyclopedia of Parallel Algorithmic Features. Supercomputing Frontiers and Innovations, Vol. 2, No. 1. Pp. 4-18 (2015).

Antonov, A., Voevodin, Vl., Voevodin, Vad., Teplov, A.: A Study of the Dynamic Characteristics of Software Implementation as an Essential Part for a Universal Description of Algorithm Properties. 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing Proceedings. Pp. 359-363 (2016).

AlgoWiki: an open encyclopedia of algorithms properties.

Cholesky, A.-L. Sur la resolution numerique des systemes d’equations lineaires La SABIX, Bulletins deja publies, Sommaire du bulletin n. 39. 81-95 (2005)

Banachiewicz, T.: Principles d'une nouvelle technique de la methode des moindres carres. Bull. Intern. Acad. Polon. Sci. A. 134--135 (1938).

Banachiewicz, T.: Methode de resoltution numerique des equations lineaires, du calcul des determinants et des inverses et de reduction des formes qua. Bull. Intern. Acad. Polon. Sci. A. 393-401 (1938).

Benoit, Commandant: Note sur une methode de resolution des equations normales provenant de l'application de la methode des moindres carres a un systeme. Bulletin Geodesique 2, 67-77 (1924).

Brezinski, C.: Andre-Louis Cholesky. Springer-Verlag GmbH, 311 p. (2014).

Faddeev, D.K., Faddeeva, V.N. : Computational Methods of Linear Algebra. Freeman (1963).

Golub, G.H., Van Loan, C.F.: Matrix computations, 3rd ed. Johns Hopkins Univ. Press, Baltimore, MD, USA (1996).

Kaporin, I.E.: High quality preconditioning of a general symmetric positive definite matrix based on its U^TU + U^TR + R^TU-decomposition. Numer. Lin. Algebra Appl. 5(6), 483-509 (1998).

Kaporin, I.E., Konshin, I.N.: A parallel block overlap preconditioning with inexact submatrix inversion for linear elasticity problems. Numer. Lin. Algebra Appl. 9(2), 141-162 (2002).

Voevodin, V.V.: Computational Foundations of Linear Algebra. Nauka, Moscow (1977) (in Russian).

Voevodin, V.V., Kuznetsov, Yu.A.: Matrices and Computations. Nauka, Moscow (1984) (in Russian).

Sadovnichy, V., Tikhonravov, A., Voevodin, Vl., Opanasenko, V.: "Lomonosov"': Supercomputing at Moscow State University. In Contemporary High Performance Computing: From Petascale toward Exascale (Chapman & Hall/CRC Computational Science), Boca Raton, USA, CRC Press. 283-307 (2013).




How to Cite

Antonov, A. S., Frolov, A. V., Kobayashi, H., Konshin, I. N., Teplov, A. M., Voevodin, V. V., & Voevodin, V. V. (2016). Parallel Processing Model for Cholesky Decomposition Algorithm in AlgoWiki Project. Supercomputing Frontiers and Innovations, 3(3), 61–70.

Most read articles by the same author(s)

1 2 > >>