Streamlining Square Root Matrix Function Computation with Restarted Heavy Ball Algorithm

Abstract

This research proposes a new efficient algorithm for calculating the square root function of the large-scale nonsingular sparse matrix by restarting the Heavy Ball Algorithm. The square root matrix function is critical in various applications, including signal processing, image processing, and machine learning. However, its computation is challenging due to existing methods' high computational complexity and numerical instability. The restarted Heavy Ball Algorithm provides a streamlined and efficient approach for computing the square root matrix function. The approach demonstrates its effectiveness through numerical experiments on various matrices, showing its superior performance compared to existing state-of-the-art methods. Numerical results show that the restarted Heavy Ball algorithm is feasible and effective for calculating the square root function.

Keywords

• Matrix functions
• heavy ball method
• square root matrix
• iterative methods

References

1. [1] Blinn, J., "Consider the lowly 2 x 2 matrix", IEEE Computer Graphics and Applications 16(2) (1996) : 82-88.
2. [2] Al-Mohy, A.H., Higham, N.J., "Computing the Fr´echet derivative of the matrix exponential with an application to condition number estimation", SIAM Journal on Matrix Analysis and Applications 30 (2009) : 1639–1657.
3. [3] Davies, P.I., Higham, N.J., "A Schur-Parlett algorithm for computing matrix functions", SIAM Journal on Matrix Analysis and Applications 25 (2003): 464-485.
4. [4] Higham, N. J., "Stable iterations for the matrix square root", Numerical Algorithms 16(2), (1997) : 227-242.
5. [5] Higham, N. J., "Computing real square roots of a real matrix", Linear Algebra and its applications 88 (1987) : 405-430.
6. [6] Meini, B., "The matrix square root from a new functional perspective: theoretical results and computational issues", SIAM journal on matrix analysis and applications 26(2), (2004) : 362-376.
7. [7] Karaduman, G., Yang, M., "An alternative method for SPP with full rank (2,1)-block matrix and nonzero right-hand side vector", Turkish Journal of Mathematics, 46(4), (2022) .
8. [8] Karaduman, G., Yang, M., Li, RC., "A least squares approach for saddle point problems", Japan Journal of Industrial and Applied Mathematics 40 (2023) : 95-107.

9. [9] Björck, A., Hammarling, S., "A Schur method for the square root of a matrix", Linear Algebra and Its Applications, 52-53, (1983): 127–140.
10. [10] Nichols, J., "A new algorithm for computing the square root of a matrix”, Thesis, Rochester Institute of Technology, (2023). Accessed from https://scholarworks.rit.edu/theses/9265
11. [11] Higham, N. J., "Computing the polar decomposition with applications", SIAM Journal on Scientific Computing 7(4) (1986) : 1160-1174.
12. [12] Laasonen, P., "On the iterative solution of the matrix equation 𝐴𝑋2 − 𝐼=0", Mathematical Tables and Other Aids to Computation 12 (1958) : 109-116.
13. [13] Ortega, J. M., Numerical Analysis, Academic Press, New York, NY, USA, 2nd edition, 1972.
14. [14] Meini, B., "The matrix square root from a new functional perspective: theoretical results and computational issues", SIAM Journal on Matrix Analysis and Applications 26(2) (2004) : 362-376.
15. [15] Zavriev, S.K., Kostyuk, F.V., "Heavy-ball method in nonconvex optimization problems", Computational Mathematics and Modeling 4 (1993): 336-341.
16. [16] Teng, Z., Wang, X., "Heavy Ball Restarted CMRH Methods for Linear Systems", Mathematical and Computational Applications 23(1) 2018.
17. [17] Hadamard, J. "Mémoire sur le problème d'analyse relatif à l'équilibre des plaques élastiques encastrées", Mémoire des savants étrangers 33 (1907) : 515-629.
18. [18] Golub, G.H. and Van Loan, C.F. Matrix Computations, 3rd ed., Baltimore MD: Johns Hopkins (1996) pp. 55.