Parallel Processing Model for Cholesky Decomposition Algorithm in AlgoWiki Project

Alexander S. Antonov; Alexey V. Frolov; Hiroaki Kobayashi; Igor N. Konshin; Alexey M. Teplov; Vadim V. Voevodin; Vladimir V. Voevodin

doi:10.14529/jsfi160307

Authors

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

DOI:

https://doi.org/10.14529/jsfi160307

Abstract

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.

References

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. http://algowiki-project.org.

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) https://sabix.revues.org/529.

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).