The k-means clustering-based CD method for solving large-scale matrix equation $ AX=B $

Lifang Dai; Maolin Liang; Qun Li; Ruijuan Zhao; Yong-hong Shen; Lifang Dai; Maolin Liang; Qun Li; Ruijuan Zhao; Yong-hong Shen

doi:10.3934/math.2026365

AIMS Mathematics

2026, Volume 11, Issue 4: 8859-8878. doi: 10.3934/math.2026365

Previous Article Next Article

Research article Special Issues

The k-means clustering-based CD method for solving large-scale matrix equation $ AX=B $

1.
School of Mathematics and Statistics, Tianshui Normal University, Tianshui, 741000, China
2.
School of Data Sciences, Zhejiang University of Finance and Economics, Hangzhou, 310018, China
3.
School of Information Engineering, Lanzhou University of Finance and Economics, Lanzhou, 730101, China
4.
School of Mathematics and Computer Science, Northwest Minzu University, Lanzhou, 730000, China

Received: 06 January 2026 Revised: 07 March 2026 Accepted: 13 March 2026 Published: 01 April 2026
MSC : 15A24, 65F10

In this paper, the coordinate descent (CD) method integrated with k-means clustering is proposed to address the least-squares problem of the large-scale matrix equation $ AX=B $, where the coefficient matrix $ A $ is assumed to be of full column rank. Rigorous theoretical analysis shows that the iteration sequence generated by this method converges to the unique least-norm least-squares solution of the problem. The performed numerical results demonstrate that the method developed here is feasible and efficient.
- matrix equation,
- least-squares,
- k-means clustering,
- coordinate descent method
Citation: Lifang Dai, Maolin Liang, Qun Li, Ruijuan Zhao, Yong-hong Shen. The k-means clustering-based CD method for solving large-scale matrix equation $ AX=B $[J]. AIMS Mathematics, 2026, 11(4): 8859-8878. doi: 10.3934/math.2026365

Related Papers:

Abstract

In this paper, the coordinate descent (CD) method integrated with k-means clustering is proposed to address the least-squares problem of the large-scale matrix equation $ AX=B $, where the coefficient matrix $ A $ is assumed to be of full column rank. Rigorous theoretical analysis shows that the iteration sequence generated by this method converges to the unique least-norm least-squares solution of the problem. The performed numerical results demonstrate that the method developed here is feasible and efficient.

References

[1]	M. J. Corless, A. E. Frazho, Linear systems and control: an operator perspective, New York: CRC Press, 2003. https://doi.org/10.1201/9780203911372
[2]	B. N. Datta, Linear and numerical linear algebra in control theory: some research problems, Linear Algebra Appl., 197–198 (1994), 755–790. https://doi.org/10.1016/0024-3795(94)90512-6 doi: 10.1016/0024-3795(94)90512-6
[3]	V. Simoncini, Computational methods for linear matrix equations, SIAM Rev., 58 (2016), 377–441. https://doi.org/10.1137/130912839 doi: 10.1137/130912839
[4]	F. Uhlig, On the matrix equation AX=B with applications to the generators of controllability matrix, Linear Algebra Appl., 85 (1987), 203–209. https://doi.org/10.1016/0024-3795(87)90217-5 doi: 10.1016/0024-3795(87)90217-5
[5]	T. Sakurai, H. Tadano, Y. Kuramashi, Application of block Krylov subspace algorithms to the Wilson-Dirac equation with multiple right-hand sides in lattice QCD, Comput. Phys. Commun., 181 (2010), 113–117. https://doi.org/10.1016/j.cpc.2009.09.006 doi: 10.1016/j.cpc.2009.09.006
[6]	A. Ben-Israel, T. Greville, Generalized inverses: theory and applications, New York: Springer, 2003. https://doi.org/10.1007/b97366
[7]	A. L. Andrew, Solution of equations involving centrosymmetric matrices, Technometrics, 15 (1973), 365–378. https://doi.org/10.1080/00401706.1973.10489049 doi: 10.1080/00401706.1973.10489049
[8]	K. E. Chu, Symmetric solutions of linear matrix equations by matrix decompositions, Linear Algebra Appl., 119 (1989), 35–50. https://doi.org/10.1016/0024-3795(89)90067-0 doi: 10.1016/0024-3795(89)90067-0
[9]	Z. Y. Peng, X. Y. Hu, The reflexive and anti-reflexive solutions of the matrix equation $AX=B$, Linear Algebra Appl., 375 (2003), 147–155. https://doi.org/10.1016/S0024-3795(03)00607-4 doi: 10.1016/S0024-3795(03)00607-4
[10]	W. F. Trench, Hermitian, Hermitian $R$-symmetric, and Hermitian $R$-skew symmetric Procrustes problems, Linear Algebra Appl., 387 (2004), 83–98. https://doi.org/10.1016/j.laa.2004.01.018 doi: 10.1016/j.laa.2004.01.018
[11]	Q. F. Xiao, X. Y. Hu, L. Zhang, The symmetric minimal rank solution of the matrix equation $AX=B$ and the optimal approximation, Electron. J. Linear Al., 18 (2009), 264–273. https://doi.org/10.13001/1081-3810.1311 doi: 10.13001/1081-3810.1311
[12]	M. L. Arias, M. C. Gonzalez, Proper splittings and reduced solutions of matrix equations, J. Math. Anal. Appl., 505 (2022), 125588. https://doi.org/10.1016/j.jmaa.2021.125588 doi: 10.1016/j.jmaa.2021.125588
[13]	S. F. Yuan, Q. W. Wang, X. F. Duan, On solutions of the quaternion matrix equation AX=B and their applications in color image restoration, Appl. Math. Comput., 221 (2013), 10–20. https://doi.org/10.1016/j.amc.2013.05.069 doi: 10.1016/j.amc.2013.05.069
[14]	Y. Li, F. X. Zhang, W. B. Guo, J. L. Zhao, On solutions of the quaternion matrix equation AX=B and their applications in color image restoration, Comput. Math. Appl., 62 (2011), 1389–1397. https://doi.org/10.1016/j.camwa.2011.04.004 doi: 10.1016/j.camwa.2011.04.004
[15]	Z. S. Yang, B. Zheng, Block minimum perturbation algorithm based on block Arnoldi process for nonsymmetric linear systems with multiple right-hand sides, Appl. Math. Comput., 347 (2019), 741–766. https://doi.org/10.1016/j.amc.2018.11.024 doi: 10.1016/j.amc.2018.11.024
[16]	W. Ding, Y. Li, D. Wang, Special least squares solutions of the reduced biquaternion matrix equation $AX=B$ with applications, Comput. Appl. Math., 40 (2021), 279. https://doi.org/10.1007/s40314-021-01641-0 doi: 10.1007/s40314-021-01641-0
[17]	D. P. O'Leary, The block conjugate gradient algorithm and related methods, Linear Algebra Appl., 29 (1980), 293–322. https://doi.org/10.1016/0024-3795(80)90247-5 doi: 10.1016/0024-3795(80)90247-5
[18]	M. Gutknecht, Block Krylov space methods for linear systems with multiple right-hand sides: an introduction, In: Modern mathematical models, methods and algorithms for real world systems, 2007.
[19]	B. Krasnopolsky, Revisiting performance of BiCGStab methods for solving systems with multiple right-hand sides, Comput. Math. Appl., 79 (2020), 2574–2597. https://doi.org/10.1016/j.camwa.2019.11.025 doi: 10.1016/j.camwa.2019.11.025
[20]	V. Simoncini, E. Gallopoulos, An iterative method for nonsymmetric systems with multiple right-hand sides, SIAM J. Sci. Comput., 16 (1995), 917–933. https://doi.org/10.1137/0916053 doi: 10.1137/0916053
[21]	H. X. Zhong, G. Wu, G. L. Chen, A flexible and adaptive simpler block GMRES with deflated restarting for linear systems with multiple right-hand sides, J. Comput. Appl. Math., 282 (2015), 139–156. https://doi.org/10.1016/j.cam.2014.12.040 doi: 10.1016/j.cam.2014.12.040
[22]	M. Hached, K. Jbilou, Numerical methods for differential linear matrix equations via Krylov subspace methods, J. Comput. Appl. Math., 370 (2020), 112674. https://doi.org/10.1016/j.cam.2019.112674 doi: 10.1016/j.cam.2019.112674
[23]	C. Jelich, M. Karimi, N. Kessissoglou, S. Marburg, Efficient solution of block Toeplitz systems with multiple right-hand sides arising from a periodic boundary element formulation, Eng. Anal. Bound. Elem., 130 (2021), 135–144. https://doi.org/10.1016/j.enganabound.2021.05.003 doi: 10.1016/j.enganabound.2021.05.003
[24]	V. Kalantzis, A. C. I. Malossi, C. Bekas, A. Curioni, E. Gallopoulos, A scalable iterative dense linear system solver for multiple right-hand sides in data analytics, Parallel Comput., 74 (2018), 136–153. https://doi.org/10.1016/j.parco.2017.12.005 doi: 10.1016/j.parco.2017.12.005
[25]	L. J. Zhao, X. Y. Hu, L. Zhang, Least squares solutions to $AX=B$ for bisymmetric matrices under a central principal submatrix constraint and the optimal approximation, Linear Algebra Appl., 428 (2008), 871–880. https://doi.org/10.1016/j.laa.2007.08.019 doi: 10.1016/j.laa.2007.08.019
[26]	L. Xu, X. Q. Liu, J. Liang, J. Wang, M. Li, S. Shen, Quantum algorithm for solving matrix equations of the form $AX=B$, Laser Phys. Lett., 19 (2022), 055202. https://doi.org/10.1088/1612-202X/ac5b5a doi: 10.1088/1612-202X/ac5b5a
[27]	Q. W. Wang, L. M. Xie, Z. H. Gao, A survey on solving the matrix equation $AXB=C$ with applications, Mathematics, 13 (2025), 450. https://doi.org/10.3390/math13030450 doi: 10.3390/math13030450
[28]	S. Hadjiantoni, G. Loizou, Numerical strategies for recursive least squares solutions to the matrix equation $AX=B$, Int. J. Comput. Math., 100 (2023), 497–510. https://doi.org/10.1080/00207160.2022.2123220 doi: 10.1080/00207160.2022.2123220
[29]	T. Strohmer, R. Vershynin, A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15 (2009), 262–278. https://doi.org/10.1007/s00041-008-9030-4 doi: 10.1007/s00041-008-9030-4
[30]	A. Zouzias, N. M. Freris, Randomized extended Kaczmarz for solving least-squares, SIAM J. Matrix Anal. Appl., 34 (2013), 773–793. https://doi.org/10.1137/120889897 doi: 10.1137/120889897
[31]	Z. Z. Bai, W. T. Wu, On greedy randomized Kaczmarz method for solving large sparse linear systems, SIAM J. Sci. Comput., 40 (2018), A592–A606. https://doi.org/10.1137/17M1137747 doi: 10.1137/17M1137747
[32]	A. Ma, D. Needell, A. Ramdas, Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods, SIAM J. Matrix Anal. Appl., 36 (2015), 1590–1604. https://doi.org/10.1137/15M1014425 doi: 10.1137/15M1014425
[33]	Y. Q. Niu, B. Zheng, A greedy block Kaczmarz algorithm for solving large-scale linear systems, Appl. Math. Lett., 104 (2020), 106294. https://doi.org/10.1016/j.aml.2020.106294 doi: 10.1016/j.aml.2020.106294
[34]	A. K. Jain, Data clustering: 50 years beyond K-means, Pattern Recogn. Lett., 31 (2010), 651–666. https://doi.org/10.1016/j.patrec.2009.09.011 doi: 10.1016/j.patrec.2009.09.011
[35]	X. L. Jiang, K. Zhang, J. F. Yin, Randomized block Kaczmarz methods with K-means clustering for solving large linear systems, J. Comput. Appl. Math., 403 (2022), 113828. https://doi.org/10.1016/j.cam.2021.113828 doi: 10.1016/j.cam.2021.113828
[36]	Y. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim., 22 (2012), 341–362. https://doi.org/10.1137/100802001 doi: 10.1137/100802001
[37]	J. H. Zhang, J. H. Guo, On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems, Appl. Numer. Math., 157 (2020), 372–384. https://doi.org/10.1016/j.apnum.2020.06.014 doi: 10.1016/j.apnum.2020.06.014
[38]	R. R. Li, H. Liu, Y. Y. Ding, Block Kaczmarz algorithm for solving large overdetermined systems of linear algebraic equations, J. Comput. Math. Higher Educ. I., 43 (2021), 150–160.
[39]	H. L. Chen, A. L. Yang, R. Liu, Y. Cao, K-means clustering based maximal residual (block) Kaczmarz methods for solving consistent system of linear equations, Comp. Appl. Math., 44 (2025), 307. https://doi.org/10.1007/s40314-025-03265-0 doi: 10.1007/s40314-025-03265-0
[40]	L. Rui. Y. Ai-Li, M. Yang, Maximal residual coordinate descent method with K-means clustering for solving large linear least-squares problems, Numer. Algor., 101 (2026), 1157–1173. https://doi.org/10.1007/s11075-025-02036-6 doi: 10.1007/s11075-025-02036-6
[41]	D. A. Désopo, A convex programming procedure, Nav. Res. Log. Quart., 6 (1959), 33–42. https://doi.org/10.1002/nav.3800060105 doi: 10.1002/nav.3800060105
[42]	H. J. Shi, S. Y. Tu, Y. Y. Xu, W. Yin, A primer on coordinate descent algorithms, 2016. https://doi.org/10.48550/arXiv.1610.00040
[43]	S. J. Wright, Coordinate descent algorithms, Math. Program., 151 (2015), 3–34. https://doi.org/10.1007/s10107-015-0892-3 doi: 10.1007/s10107-015-0892-3
[44]	K. H. Guo, X. Y. Hu, L. Zhang, A new iteration method for the matrix equation, Appl. Math. Comput., 187 (2007), 1434–1441. https://doi.org/10.1016/j.amc.2006.09.059 doi: 10.1016/j.amc.2006.09.059
[45]	G. X. Huang, F. Yin, K. Guo, An iterative method for the skew-symmetric solution and the optimal approximate solution of the matrix equation $AXB=C$, J. Comput. Appl. Math., 212 (2008), 231–244. https://doi.org/10.1016/j.cam.2006.12.005 doi: 10.1016/j.cam.2006.12.005
[46]	S. G. Shafiei, M. Hajarian, Developing Kaczmarz method for solving Sylvester matrix equations, J. Franklin I., 359 (2022), 8991–9005. https://doi.org/10.1016/j.jfranklin.2022.09.028 doi: 10.1016/j.jfranklin.2022.09.028

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)