
-
Previous Article
An efficient D-N alternating algorithm for solving an inverse problem for Helmholtz equation
- DCDS-S Home
- This Issue
-
Next Article
A new coupled complex boundary method (CCBM) for an inverse obstacle problem
Extended Krylov subspace methods for solving Sylvester and Stein tensor equations
1. | Laboratory LAMAI, University Cadi Ayyad, Marrakesh, Morocco |
2. | Laboratory LabSIPE, ENSA d'El Jadida, University Chouaib Doukkali, El Jadida, Morocco |
This paper deals with Sylvester and Stein tensor equations with low rank right hand sides. It proposes extended Krylov-like methods for solving Sylvester and Stein tensor equations. The expressions of residual norms are presented. To show the performance of the proposed approaches, some numerical experiments are given.
References:
[1] |
J. Ballani and L. Grasedyck, A projection method to solve linear systems in tensor format, Numerical Linear Algebra with Applications, 20 (2013), 27–43.
doi: 10.1002/nla.1818. |
[2] |
F. P. A. Beik, F. S. Movahed and S. Ahmadi-Asl, On the Krylov subspace methods based on tensor format for positive definite Sylvester tensor equations, Numerical Linear Algebra with Applications, 23 (2016), 444–466.
doi: 10.1002/nla.2033. |
[3] |
A. H. Bentbib, K. Jbilou and El M. Sadek, On some extended block Krylov based methods for large scale nonsymmetric Stein matrix equations, Mathematics, 5 (2017), 21.
doi: 10.3390/math5020021. |
[4] |
A. H. Bentbib, S. El-Halouy and El M. Sadek, Krylov subspace projection method for Sylvester tensor equation with low rank right-hand side, Numerical Algorithms, (2020), 1–20.
doi: 10.1007/s11075-020-00874-0. |
[5] |
M. Chen and D. Kressner, Recursive blocked algorithms for linear systems with Kronecker product structure, Numerical Algorithms, (2019), 1–18.
doi: 10.1007/s11075-019-00797-5. |
[6] |
D. Calvetti and L. Reichel, Application of ADI iterative methods to the restoration of noisy images, SIAM Journal on Matrix Analysis and Applications, 17 (1996), 165–186.
doi: 10.1137/S0895479894273687. |
[7] |
Z. Chen and L. Lu,
A projection method and Kronecker product pre-conditioner for solving Sylvester tensor equations, Science China Mathematics, 55 (2012), 1281-1292.
doi: 10.1007/s11425-012-4363-5. |
[8] |
Z. Chen and L. Lu, A gradient based iterative solutions for Sylvester tensor equations, Mathematical Problems in Engineering, (2013).
doi: 10.1155/2013/819479. |
[9] |
F. Ding and T. Chen, Gradient based iterative algorithms for solving a class of matrix equations, IEEE Transactions on Automatic Control, 50 (2005), 1216–1221.
doi: 10.1109/TAC.2005.852558. |
[10] |
M. Heyouni and K. Jbilou, An extended block Arnoldi algorithm for large-scale solutions of the continuous-time algebraic Riccati equation, Electronic Transactions on Numerical Analysis, 33 (2009), 53–62. |
[11] |
M. Heyouni, Extended Arnoldi methods for large low-rank Sylvester matrix equations, Applied Numerical Mathematics, 60 (2010), 1171–1182.
doi: 10.1016/j.apnum.2010.07.005. |
[12] |
T. G. Kolda and B. W. Bader, Tensor decompositions and applications, SIAM Review, 51 (2009), 455–500.
doi: 10.1137/07070111X. |
[13] |
D. Kressner and C. Tobler, Krylov subspace methods for linear systems with tensor product structure, SIAM Journal on Matrix Analysis and Applications, 31 (2010), 1688–1714.
doi: 10.1137/090756843. |
[14] |
A. N. Langville and W. J. Stewart, A Kronecker product approximate preconditioner for SANs, Numerical Linear Algebra with Applications, 11 (2004), 723–752.
doi: 10.1002/nla.344. |
[15] |
N. Lee and A. Cichocki, Fundamental tensor operations for large-scale data analysis using tensor network formats, Multidimensional Systems and Signal Processing, 29 (2018), 921–960.
doi: 10.1007/s11045-017-0481-0. |
[16] |
T. Li, Q. W. Wang and X. F. Duan, Numerical algorithms for solving discrete Lyapunov tensor equation, Journal of Computational and Applied Mathematics, 370 (2020), 112676.
doi: 10.1016/j.cam.2019.112676. |
[17] |
T. Penzl, et al., A Matlab toolbox for large Lyapunov and Riccati equations, model reduction problems, and linear quadratic optimal control problems, https://www.tu-chemnitz.de/sfb393/lyapack/, (2000). |
[18] |
T. Stykel and V. Simoncini,
Krylov subspace methods for projected Lyapunov equations, Applied Numerical Mathematics, 62 (2012), 35-50.
doi: 10.1016/j.apnum.2011.09.007. |
[19] |
X. Xu and W. Q. Wang, Extending BiCG and BiCR methods to solve the Stein tensor equation, Computers & Mathematics with Applications, 77 (2019), 3117–3127.
doi: 10.1016/j.camwa.2019.01.024. |
show all references
References:
[1] |
J. Ballani and L. Grasedyck, A projection method to solve linear systems in tensor format, Numerical Linear Algebra with Applications, 20 (2013), 27–43.
doi: 10.1002/nla.1818. |
[2] |
F. P. A. Beik, F. S. Movahed and S. Ahmadi-Asl, On the Krylov subspace methods based on tensor format for positive definite Sylvester tensor equations, Numerical Linear Algebra with Applications, 23 (2016), 444–466.
doi: 10.1002/nla.2033. |
[3] |
A. H. Bentbib, K. Jbilou and El M. Sadek, On some extended block Krylov based methods for large scale nonsymmetric Stein matrix equations, Mathematics, 5 (2017), 21.
doi: 10.3390/math5020021. |
[4] |
A. H. Bentbib, S. El-Halouy and El M. Sadek, Krylov subspace projection method for Sylvester tensor equation with low rank right-hand side, Numerical Algorithms, (2020), 1–20.
doi: 10.1007/s11075-020-00874-0. |
[5] |
M. Chen and D. Kressner, Recursive blocked algorithms for linear systems with Kronecker product structure, Numerical Algorithms, (2019), 1–18.
doi: 10.1007/s11075-019-00797-5. |
[6] |
D. Calvetti and L. Reichel, Application of ADI iterative methods to the restoration of noisy images, SIAM Journal on Matrix Analysis and Applications, 17 (1996), 165–186.
doi: 10.1137/S0895479894273687. |
[7] |
Z. Chen and L. Lu,
A projection method and Kronecker product pre-conditioner for solving Sylvester tensor equations, Science China Mathematics, 55 (2012), 1281-1292.
doi: 10.1007/s11425-012-4363-5. |
[8] |
Z. Chen and L. Lu, A gradient based iterative solutions for Sylvester tensor equations, Mathematical Problems in Engineering, (2013).
doi: 10.1155/2013/819479. |
[9] |
F. Ding and T. Chen, Gradient based iterative algorithms for solving a class of matrix equations, IEEE Transactions on Automatic Control, 50 (2005), 1216–1221.
doi: 10.1109/TAC.2005.852558. |
[10] |
M. Heyouni and K. Jbilou, An extended block Arnoldi algorithm for large-scale solutions of the continuous-time algebraic Riccati equation, Electronic Transactions on Numerical Analysis, 33 (2009), 53–62. |
[11] |
M. Heyouni, Extended Arnoldi methods for large low-rank Sylvester matrix equations, Applied Numerical Mathematics, 60 (2010), 1171–1182.
doi: 10.1016/j.apnum.2010.07.005. |
[12] |
T. G. Kolda and B. W. Bader, Tensor decompositions and applications, SIAM Review, 51 (2009), 455–500.
doi: 10.1137/07070111X. |
[13] |
D. Kressner and C. Tobler, Krylov subspace methods for linear systems with tensor product structure, SIAM Journal on Matrix Analysis and Applications, 31 (2010), 1688–1714.
doi: 10.1137/090756843. |
[14] |
A. N. Langville and W. J. Stewart, A Kronecker product approximate preconditioner for SANs, Numerical Linear Algebra with Applications, 11 (2004), 723–752.
doi: 10.1002/nla.344. |
[15] |
N. Lee and A. Cichocki, Fundamental tensor operations for large-scale data analysis using tensor network formats, Multidimensional Systems and Signal Processing, 29 (2018), 921–960.
doi: 10.1007/s11045-017-0481-0. |
[16] |
T. Li, Q. W. Wang and X. F. Duan, Numerical algorithms for solving discrete Lyapunov tensor equation, Journal of Computational and Applied Mathematics, 370 (2020), 112676.
doi: 10.1016/j.cam.2019.112676. |
[17] |
T. Penzl, et al., A Matlab toolbox for large Lyapunov and Riccati equations, model reduction problems, and linear quadratic optimal control problems, https://www.tu-chemnitz.de/sfb393/lyapack/, (2000). |
[18] |
T. Stykel and V. Simoncini,
Krylov subspace methods for projected Lyapunov equations, Applied Numerical Mathematics, 62 (2012), 35-50.
doi: 10.1016/j.apnum.2011.09.007. |
[19] |
X. Xu and W. Q. Wang, Extending BiCG and BiCR methods to solve the Stein tensor equation, Computers & Mathematics with Applications, 77 (2019), 3117–3127.
doi: 10.1016/j.camwa.2019.01.024. |



Algorithm 1 Extended Block Arnoldi (EBA) |
1: Input: 2: Compute the QR decomposition of 3: Set 4: 5: Orthogonalize 6: for 7: Compute the QR decomposition of |
Algorithm 1 Extended Block Arnoldi (EBA) |
1: Input: 2: Compute the QR decomposition of 3: Set 4: 5: Orthogonalize 6: for 7: Compute the QR decomposition of |
Algorithm 2 Extended Global Arnoldi (EGA) |
1: Input: 2: Compute the global QR decomposition of 3: Set 4: 5: Orthogonalize 6: for 7: Compute the QR decomposition of |
Algorithm 2 Extended Global Arnoldi (EGA) |
1: Input: 2: Compute the global QR decomposition of 3: Set 4: 5: Orthogonalize 6: for 7: Compute the QR decomposition of |
Algorithm 3 Sylvester Stein EBA Process |
1: Coefficient matrices 2: Output: Approximate solutions, 3: Choose a tolerance 4: For For 5: Compute 6: Compute the residual norms 7: If 8: The approximate solutions are given by |
Algorithm 3 Sylvester Stein EBA Process |
1: Coefficient matrices 2: Output: Approximate solutions, 3: Choose a tolerance 4: For For 5: Compute 6: Compute the residual norms 7: If 8: The approximate solutions are given by |
Algorithm 4 Sylvester / Stein EGA Process |
1: Input: Coefficient matrices 2: Output: Approximate solutions, 3: Choose a tolerance 4: For For 5: Compute 6: Compute the upper bound for the residual norms 7: If 8: The approximate solutions are given by |
Algorithm 4 Sylvester / Stein EGA Process |
1: Input: Coefficient matrices 2: Output: Approximate solutions, 3: Choose a tolerance 4: For For 5: Compute 6: Compute the upper bound for the residual norms 7: If 8: The approximate solutions are given by |
Algorithm | Cycles | CPU Times (Second) | |||
Algorithm 3 | |||||
Algorithm 4 | |||||
Algorithm | Cycles | CPU Times (Second) | |||
Algorithm 3 | |||||
Algorithm 4 | |||||
Algorithm | Cycles | CPU Times (Second) | |||||
Algorithm 3 | (case |
||||||
(case |
|||||||
Algorithm 4 | (case |
||||||
(case |
|||||||
Algorithm 4 |
Algorithm | Cycles | CPU Times (Second) | |||||
Algorithm 3 | (case |
||||||
(case |
|||||||
Algorithm 4 | (case |
||||||
(case |
|||||||
Algorithm 4 |
Algorithm | Cycles | CPU Times (Second) | |||
Algorithm 3 | |||||
Algorithm 4 | |||||
Algorithm | Cycles | CPU Times (Second) | |||
Algorithm 3 | |||||
Algorithm 4 | |||||
[1] |
Shenglong Hu. A note on the solvability of a tensor equation. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021146 |
[2] |
Jin Wang, Jun-E Feng, Hua-Lin Huang. Solvability of the matrix equation $ AX^{2} = B $ with semi-tensor product. Electronic Research Archive, 2021, 29 (3) : 2249-2267. doi: 10.3934/era.2020114 |
[3] |
Mourad Bellassoued, Zouhour Rezig. Recovery of transversal metric tensor in the Schrödinger equation from the Dirichlet-to-Neumann map. Discrete and Continuous Dynamical Systems - S, 2022, 15 (5) : 1061-1084. doi: 10.3934/dcdss.2021158 |
[4] |
Qun Liu, Lihua Fu, Meng Zhang, Wanjuan Zhang. Two-dimensional seismic data reconstruction using patch tensor completion. Inverse Problems and Imaging, 2020, 14 (6) : 985-1000. doi: 10.3934/ipi.2020052 |
[5] |
Jan Boman, Vladimir Sharafutdinov. Stability estimates in tensor tomography. Inverse Problems and Imaging, 2018, 12 (5) : 1245-1262. doi: 10.3934/ipi.2018052 |
[6] |
Chaudry Masood Khalique, Letlhogonolo Daddy Moleleki. A study of a generalized first extended (3+1)-dimensional Jimbo-Miwa equation. Discrete and Continuous Dynamical Systems - S, 2020, 13 (10) : 2789-2802. doi: 10.3934/dcdss.2020169 |
[7] |
Qiao Liang, Qiang Ye. Deflation by restriction for the inverse-free preconditioned Krylov subspace method. Numerical Algebra, Control and Optimization, 2016, 6 (1) : 55-71. doi: 10.3934/naco.2016.6.55 |
[8] |
Dan Li, Chunlai Mu, Pan Zheng, Ke Lin. Boundedness in a three-dimensional Keller-Segel-Stokes system involving tensor-valued sensitivity with saturation. Discrete and Continuous Dynamical Systems - B, 2019, 24 (2) : 831-849. doi: 10.3934/dcdsb.2018209 |
[9] |
Meng Ding, Ting-Zhu Huang, Xi-Le Zhao, Michael K. Ng, Tian-Hui Ma. Tensor train rank minimization with nonlocal self-similarity for tensor completion. Inverse Problems and Imaging, 2021, 15 (3) : 475-498. doi: 10.3934/ipi.2021001 |
[10] |
Mengmeng Zheng, Ying Zhang, Zheng-Hai Huang. Global error bounds for the tensor complementarity problem with a P-tensor. Journal of Industrial and Management Optimization, 2019, 15 (2) : 933-946. doi: 10.3934/jimo.2018078 |
[11] |
Yiju Wang, Guanglu Zhou, Louis Caccetta. Nonsingular $H$-tensor and its criteria. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1173-1186. doi: 10.3934/jimo.2016.12.1173 |
[12] |
Ruixue Zhao, Jinyan Fan. Quadratic tensor eigenvalue complementarity problems. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022073 |
[13] |
Abdollah Borhanifar, Maria Alessandra Ragusa, Sohrab Valizadeh. High-order numerical method for two-dimensional Riesz space fractional advection-dispersion equation. Discrete and Continuous Dynamical Systems - B, 2021, 26 (10) : 5495-5508. doi: 10.3934/dcdsb.2020355 |
[14] |
Daomin Cao, Hang Li. High energy solutions of the Choquard equation. Discrete and Continuous Dynamical Systems, 2018, 38 (6) : 3023-3032. doi: 10.3934/dcds.2018129 |
[15] |
Nicolas Van Goethem. The Frank tensor as a boundary condition in intrinsic linearized elasticity. Journal of Geometric Mechanics, 2016, 8 (4) : 391-411. doi: 10.3934/jgm.2016013 |
[16] |
Henry O. Jacobs, Hiroaki Yoshimura. Tensor products of Dirac structures and interconnection in Lagrangian mechanics. Journal of Geometric Mechanics, 2014, 6 (1) : 67-98. doi: 10.3934/jgm.2014.6.67 |
[17] |
François Monard. Efficient tensor tomography in fan-beam coordinates. Inverse Problems and Imaging, 2016, 10 (2) : 433-459. doi: 10.3934/ipi.2016007 |
[18] |
Kaili Zhang, Haibin Chen, Pengfei Zhao. A potential reduction method for tensor complementarity problems. Journal of Industrial and Management Optimization, 2019, 15 (2) : 429-443. doi: 10.3934/jimo.2018049 |
[19] |
Xia Li, Yong Wang, Zheng-Hai Huang. Continuity, differentiability and semismoothness of generalized tensor functions. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3525-3550. doi: 10.3934/jimo.2020131 |
[20] |
Liqun Qi, Shenglong Hu, Yanwei Xu. Spectral norm and nuclear norm of a third order tensor. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1101-1113. doi: 10.3934/jimo.2021010 |
2020 Impact Factor: 2.425
Tools
Metrics
Other articles
by authors
[Back to Top]