Parallel Processing Model for Cholesky Decomposition Algorithm in AlgoWiki Project
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).
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).
Published
2016-09-06
Issue
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
