Abstract
Practical applicability of many statistical algorithms is limited by large sizes of corresponding covariance matrices. These limitations can be significantly weakened due to effective use of the structure of covariance matrices, properties of the autocorrelation function, and advantages of the architecture of modern GPUs. This paper presents GPU implementations of the algorithms for inversion of a covariance matrix and solution of a system of linear equations whose coefficient matrix is a covariance matrix. Inversion of close to sparse covariance matrices is also considered in the work. For all the cases considered, significant accelerations were obtained in comparison with Octave mathematical software and ViennaCL computational library. For example, implemented algorithm of solution of a linear system was 6 times faster as compared with the implementation of Octave on the CPU and 3 times faster as compared with the ViennaCL implementation on the GPU for general matrices. The performance of inversion of a covariance matrix was 14 times faster than inversion algorithm of Octave on the CPU and 6 times faster than ViennaCL inversion algorithm on GPU.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. W. Robbins and T. J. Fisher, “Cross-correlation matrices for tests of independence and causality between two multivariate time series,” J. Business Econ. Statist. 33, 459–473 (2015).
S. Efromovich and E. Smirnova, “Statistical analysis of large cross-covariance and cross-correlation matrices produced by fMRI images,” J. Biometr. Biostatist. 5 (2), 1 (2014).
M. Jun, “Non-stationary cross-covariance models for multivariate processes on a globe,” Scand. J. Statist. 38, 726–747 (2011).
D. E. Demidov, E. V. Mokshin, and E. V. Birialtsev, “Determination of moment tensor and location of microseismic events under conditions of highly correlated noise based on the maximum likelihood method,” Geophys. Prospect. 33, 437–449 (2017).
N. Levinson, “The Wiener RMS error criterion in filter design and prediction,” J. Math. Phys. 25, 261–278 (1947).
E. H. Bareiss, “Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices,” Numer. Math. 13, 404–424 (1969).
H. Krishna and Y. Wang, “The Split Levinson algorithm is weakly stable,” SIAM J. Numer. Anal. 30, 1498–1508 (1993).
A. W. Bojanczyk, R. P. Brent, F. R. de Hoog, and D. R. Sweet, “On the stability of the Bareiss and related Toeplitz factorization algorithms,” SIAM J. Matrix Anal. Appl. 16, 40–57 (1995).
S. Chandrasekeran, M. Gu, X. Sun, J. Xia, and J. Zhu, “A superfast algorithm for Toeplitz systems of linear equations,” SIAM J. Matrix Anal. Appl. 29, 1247–1266 (2007).
G. Heinig and K. Rost, “Fast algorithms for Toeplitz and Hankel matrices,” Linear Algebra Appl. 435, 1–59 (2011).
W. F. Trench, “An algorithm for the inversion of finite Toeplitz matrices,” SIAM J. Appl. Math. 12, 525–522 (1964).
G. S. Ammar, “Classical foundations of algorithms for solving positive definite Toeplitz equation,” Calcolo 33, 99–113 (1996).
S. Zohar, “Toeplitz matrix inversion: the algorithm of W. F. Trench,” J. ACM 16, 592–601 (1969).
V. Y. Pan, Z. Q, Chen, and A. Zheng, “The complexity of the matrix eigenproblem,” in Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 507–516.
D. Demidov, K. Ahnert, K. Rupp, and P. Gottschling, “Programming CUDA and OpenCL: a case study using modern C++ libraries,” SIAM J. Sci. Comput. 35, 453–472 (2013).
D. Demidov, K. Ahnert, and M. Mulansky, “Solving ordinary differential equations on GPUs,” in Numerical Computations with GPUs (Springer, Cham, 2010).
K. Rupp, Ph. Tillet, F. Rudolf, J. Weinbub, A. Morhammer, T. Grasser, A. Jangel, and S. Selberherr, “ViennaCL—linear algebra library for multi— and many-core architectures,” SIAM J. Sci. Comput. 38, 412–439 (2016).
Author information
Authors and Affiliations
Corresponding authors
Additional information
(Submitted by A. M. Elizarov)
Rights and permissions
About this article
Cite this article
Erofeev, K.Y., Khramchenkov, E.M. & Biryal’tsev, E.V. High-performance Processing of Covariance Matrices Using GPU Computations. Lobachevskii J Math 40, 547–554 (2019). https://doi.org/10.1134/S1995080219050068
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1995080219050068