Iterative methods to solve the constrained Sylvester equation

Siting Yu; Jingjing Peng; Zengao Tang; Zhenyun Peng; Siting Yu; Jingjing Peng; Zengao Tang; Zhenyun Peng

doi:10.3934/math.20231097

AIMS Mathematics

2023, Volume 8, Issue 9: 21531-21553. doi: 10.3934/math.20231097

Previous Article Next Article

Research article Special Issues

Iterative methods to solve the constrained Sylvester equation

College of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin 541004, China

Received: 01 May 2023 Revised: 16 June 2023 Accepted: 24 June 2023 Published: 06 July 2023
MSC : 15A24, 65F30

In this paper, the multiple constraint least squares solution of the Sylvester equation $ AX+XB = C $ is discussed. The necessary and sufficient conditions for the existence of solutions to the considered matrix equation are given. Noting that the alternating direction method of multipliers (ADMM) is a one-step iterative method, a multi-step alternating direction method of multipliers (MSADMM) to solve the considered matrix equation is proposed and some convergence results of the proposed algorithm are proved. Problems that should be studied in the near future are listed. Numerical comparisons between MSADMM, ADMM and ADMM with Anderson acceleration (ACADMM) are included.
- nonlinear matrix equation,
- fixed point iteration algorithm,
- Anderson acceleration algorithm,
- Thompson distance
Citation: Siting Yu, Jingjing Peng, Zengao Tang, Zhenyun Peng. Iterative methods to solve the constrained Sylvester equation[J]. AIMS Mathematics, 2023, 8(9): 21531-21553. doi: 10.3934/math.20231097

Related Papers:

Abstract

In this paper, the multiple constraint least squares solution of the Sylvester equation $ AX+XB = C $ is discussed. The necessary and sufficient conditions for the existence of solutions to the considered matrix equation are given. Noting that the alternating direction method of multipliers (ADMM) is a one-step iterative method, a multi-step alternating direction method of multipliers (MSADMM) to solve the considered matrix equation is proposed and some convergence results of the proposed algorithm are proved. Problems that should be studied in the near future are listed. Numerical comparisons between MSADMM, ADMM and ADMM with Anderson acceleration (ACADMM) are included.

References

[1]	R. Bhatia, P. Rosenthal, How and why to solve the operator equation $AX-XB = Y$, Bull. London Math. Soc., 29 (1997), 1–21. https://doi.org/10.1112/S0024609396001828 doi: 10.1112/S0024609396001828
[2]	G. H. Golub, C. F. Van Loan, Matrix computations, 3 Eds., Johns Hopkins University Press, Baltimore, Maryland, 1996.
[3]	V. Sima, Algorithms for linear quadratic optimization, Pure and Applied Mathematics, New York: Marcel Dekker, Inc., 1996.
[4]	B. Datta, Numerical methods for linear control systems, Design and Analysis, Academic Press, 2004. https://doi.org/10.1016/B978-0-12-203590-6.X5000-9
[5]	A. Locatelli, Optimal control: an introduction, Birkhäuser Basel, 2001.
[6]	R. W. Aldhaheri, Model order reduction via real Schur-form decomposition, Int. J. Control, 53 (1991), 709–716. https://doi.org/10.1080/00207179108953642 doi: 10.1080/00207179108953642
[7]	A. C. Antoulas, Approximation of large scale dynamical systems, Society for Industrial and Applied Mathematics, Philadelphia, 2005.
[8]	U. Baur, P. Benner, Cross-gramian based model reduction for data-sparse systems, Electron. Trans. Numer. Anal., 31 (2008), 256–270.
[9]	D. C. Sorensen, A. C. Antoulas, The Sylvester equation and approximate balanced reduction, Linear Algebra Appl., 351-352 (2002), 671–700. https://doi.org/10.1016/S0024-3795(02)00283-5 doi: 10.1016/S0024-3795(02)00283-5
[10]	Y. Sun, C. Wu, S. Zhao, Applications of the Sylvester equation for the lattice BKP system, Theor. Math. Phys., 214 (2023), 354–368. https://doi.org/10.1134/S0040577923030042 doi: 10.1134/S0040577923030042
[11]	A. Altavilla, C. de Fabritiis, Equivalence of slice semi-regular functions via Sylvester operators, Linear Algebra Appl., 607 (2020), 151–189. https://doi.org/10.1016/j.laa.2020.08.009 doi: 10.1016/j.laa.2020.08.009
[12]	C. H. Choi, A. J. Laub, Efficient matrix-valued algorithm for solving stiff Riccati differential equations, IEEE Trans. Autom. Control, 35 (1989), 770–776. https://doi.org/10.1109/9.57015 doi: 10.1109/9.57015
[13]	L. Dieci, Numerical integration of the differential Riccati equation and some related issues, SIAM J. Numer. Anal., 29 (1992), 781–815. https://doi.org/10.1137/0729049 doi: 10.1137/0729049
[14]	W. H. Enright, Improving the efficiency of matrix operations in the numerical solution of stiff ordinary differential equations, ACM Trans. Math. Software, 4 (1978), 127–136. https://doi.org/10.1145/355780.355784 doi: 10.1145/355780.355784
[15]	R. H. Bartels, G. W. Stewart, Algorithm 432: the solution of the matrix equation $AX-BX = C$, Commun. ACM, 15 (1972), 820–826. https://doi.org/10.1145/361573.361582 doi: 10.1145/361573.361582
[16]	G. Golub, S. Nash, C. F. Van Loan, A Hessenberg-Schur method for the matrix equation $AX+XB = C$, IEEE Trans. Automat. Control, 24 (1979), 909–913. https://doi.org/10.1109/TAC.1979.1102170 doi: 10.1109/TAC.1979.1102170
[17]	J. D. Roberts, Linear model reduction and solution of the algebraic Riccati equation by use of the sign function, Int. J. Control, 32 (1980), 677–687. https://doi.org/10.1080/00207178008922881 doi: 10.1080/00207178008922881
[18]	R. A. Smith, Matrix equation $XA+BX = C$, SIAM J. Appl. Math., 16 (1968), 198–201. https://doi.org/10.1137/0116017 doi: 10.1137/0116017
[19]	D. Calvetti, L. Reichel, Application of ADI iterative methods to the restoration of noisy images, SIAM J. Matrix Anal. Appl., 17 (1996), 165–186. https://doi.org/10.1137/S0895479894273687 doi: 10.1137/S0895479894273687
[20]	N. Truhar, R. C. Li, On ADI method for Sylvester equations, Technical Report 2008-02, Department of Mathematics, University of Texas at Arlington, 2008.
[21]	E. L. Wachspress, Trail to a Lyapunov equation solver, Comput. Math. Appl., 55 (2008), 1653–1659. https://doi.org/10.1016/j.camwa.2007.04.048 doi: 10.1016/j.camwa.2007.04.048
[22]	E. Wachspress, Adi iteration parameters for solving Lyapunov and Sylvester equations, Technical Report, March, 2009.
[23]	P. Benner, Factorized solution of Sylvester equations with applications in control, Processing of the 16th International Symposium on Mathematical Theory of Network and Systems (MTNS 2004), Leuven, Belgium, 2004.
[24]	U. Baur, Low rank solution of data sparse Sylvester equations, Numer. Linear Algebra Appl., 15 (2008), 837–851. https://doi.org/10.1002/nla.605 doi: 10.1002/nla.605
[25]	M. Konstantinov, D. W. Gu, V. Mehrmann, P. Petkov, Perturbation theory for matrix equations, Elsevier, 2003.
[26]	N. J. Higham, Accuracy and stability of numerical algorithms, SIAM, Philadelphia, 1996.
[27]	G. W. Stewart, J. G. Sun, Matrix perturbation theory, Academic Press, Harcourt Brace Jovanovich, 1990.
[28]	G. B. Dantzig, Deriving a utility function for the economy, Technical Report SOL 85-6R, Department of Operations Research, Stanford University, Stanford, CA 1985.
[29]	H. Hu, I. Olkin, A numerical procedure for finding the positive definite matrix closest to a patterned matrix, Stat. Probab. Lett., 12 (1991), 511–515. https://doi.org/10.1016/0167-7152(91)90006-D doi: 10.1016/0167-7152(91)90006-D
[30]	M. Monsalve, J. Moreno, R. Escalante, M. Raydan, Selective alternating projections to find the nearest SDD$^+$ matrix, Appl. Math. Comput., 145 (2003), 205–220. https://doi.org/10.1016/S0096-3003(02)00478-2 doi: 10.1016/S0096-3003(02)00478-2
[31]	S. Q. Ma, Alternating proximal gradient method for convex minimization, J. Sci. Comput., 68 (2016), 546–572. https://doi.org/10.1007/s10915-015-0150-0 doi: 10.1007/s10915-015-0150-0
[32]	D. P. Bertsekas, J. N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., 1989.
[33]	J. Eckstein, D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), 293–318. https://doi.org/10.1007/BF01581204 doi: 10.1007/BF01581204
[34]	Z. Y. Peng, A matrix LSQR iterative method to solve matrix equation $AXB = C$, Int. J. Comput. Math., 87 (2010), 1820–1830. https://doi.org/10.1080/00207160802516875 doi: 10.1080/00207160802516875
[35]	D. G. Anderson, Iterative procedures for nonlinear integral equations, J. ACM, 12 (1965), 547–560. https://doi.org/10.1145/321296.321305 doi: 10.1145/321296.321305
[36]	H. Fang, Y. Saad, Two classes of multisecant methods for nonlinear acceleration, Numer. Linear Algebra Appl., 16 (2009), 197–221. https://doi.org/10.1002/nla.617 doi: 10.1002/nla.617
[37]	H. F. Walker, P. Ni, Anderson acceleration for fixed-point iterations, SIAM J. Numer. Anal., 49 (2011), 1715–1735. https://doi.org/10.1137/10078356X doi: 10.1137/10078356X
[38]	N. J. Higham, N. Strabic, Anderson acceleration of the alternating projections method for computing the nearest correlation matrix, Numer. Algor., 72 (2016), 1021–1042. https://doi.org/10.1007/s11075-015-0078-3 doi: 10.1007/s11075-015-0078-3

Reader Comments

Your name:*

Email:*
© 2023 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)