Geodesic
Regularized Cholesky decomposition method for finite bit width computing
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 2, pp. A70-A81 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

This research focuses on the Cholesky decomposition of symmetric positive definite matrices. While the Cholesky decomposition is known for its computational efficiency and numerical robustness, it may encounter decomposition failures when applied to ill-conditioned matrices with large condition numbers. To address these computational challenges, this paper proposes an improved probabilistic rounding error analysis method. This method can more accurately estimate the rounding errors and thereby guide the selection of the optimal diagonal loading value. The main contribution of this research is the determination of a diagonal loading value applicable to all positive definite matrices, ensuring the successful completion of Cholesky decomposition. In addition, taking into account the binary representation of numbers in computers, the diagonal loading value is converted to exponential form, allowing multiplication to be replaced by the floating-point bitwise operations. This approach is both practical and efficient, effectively solving the challenges posed by ill-conditioned matrices and limited computational precision.
Keywords: cholesky decomposition, diagonal loading, regularization, numerical robustness, low bit-width computations, probabilistic rounding error analysis. 
@article{SEMR_2024_21_2_a66,
     author = {Z. Zhang and V. Lyashev},
     title = {Regularized {Cholesky} decomposition method for finite bit width computing},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {A70--A81},
     year = {2024},
     volume = {21},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a66/}
}
TY  - JOUR
AU  - Z. Zhang
AU  - V. Lyashev
TI  - Regularized Cholesky decomposition method for finite bit width computing
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2024
SP  - A70
EP  - A81
VL  - 21
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a66/
LA  - en
ID  - SEMR_2024_21_2_a66
ER  - 
%0 Journal Article
%A Z. Zhang
%A V. Lyashev
%T Regularized Cholesky decomposition method for finite bit width computing
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2024
%P A70-A81
%V 21
%N 2
%U http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a66/
%G en
%F SEMR_2024_21_2_a66
Z. Zhang; V. Lyashev. Regularized Cholesky decomposition method for finite bit width computing. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 2, pp. A70-A81. http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a66/

[1] Z. Bai et al., “On the equivalence of MMSE and IRC receiver in MU-MIMO systems”, IEEE Commun. Lett., 15:12 (2011), 1288–1290 | DOI

[2] V. Savaux, Y. Louët, “LMMSE channel estimation in OFDM context: a review”, IET Signal Processing, 11:2 (2017), 123–134 | DOI

[3] A. Osinsky, R. Bychkov, M. Trefilov, V. Lyashev, A. Ivanov, “Regularization for Cholesky decomposition in massive MIMO detection”, IEEE Wireless Communications Letters, 12:9 (2023), 1603–1607 | DOI

[4] S.H. Cheng, N.J. Higham, “A modified Cholesky algorithm based on a symmetric indefinite factorization”, SIAM J. Matrix Anal. Appl., 19:4 (1998), 1097–1110 | DOI | MR | Zbl

[5] N.J. Higham, Accuracy and stability of numerical algorithms, SIAM, Philadelphia, 2002 | MR | Zbl

[6] N.J. Higham, T. Mary, “A new approach to probabilistic rounding error analysis”, SIAM J. Sci. Comput., 41:5 (2019), A2815–A2835 | DOI | MR | Zbl

[7] I. Kolesnikov, V. Lyashev, M. Kirichenko, “Fast algorithm for estimating singular values of Hermitian matrix”, 31st Telecommunications Forum (TELFOR) (Belgrade, Serbia), 2023, 1–4

[8] G.H. Golub, C.F. Van Loan, Matrix computations, The Johns Hopkins University Press, Baltimore, 2013 | MR

[9] J.H. Wilkinson, “A priori error analysis of algebraic processes”, Tr. Mezhdunarod. Kongr. Mat. (Moskva), 1966, 629–639 | MR | Zbl

[10] Fukaya T, Kannan R, Nakatsukasa Y, Yamamoto Y, Yanagisawa Y., “Performance evaluation of the shifted Cholesky QR algorithm for ill-conditioned matrices”, SC18 Supercomputing, Proceedings, Poster No 69 https://sc18.supercomputing.org/proceedings/tech_poster/poster_files/post193s2-file3.pdf

[11] W. Hoeffding, “Probability inequalities for sums of bounded random variables”, J. Amer. Stat. Assoc., 58 (1963), 13–30 | DOI | MR | Zbl

[12] Z. Bai, J. Demmel, A. McKenney, On floating point errors in Cholesky, Technical Report CS-89-87, LAPACK Working Note 14, Department of Computer Science, University of Tennessee, Knoxville, TN, USA, October 1989