Abstract
The preconditioned iterative solvers for solving Sylvester tensor equations are considered in this paper. By fully exploiting the structure of the tensor equation, we propose a projection method based on the tensor format, which needs less flops and storage than the standard projection method. The structure of the coefficient matrices of the tensor equation is used to design the nearest Kronecker product (NKP) preconditioner, which is easy to construct and is able to accelerate the convergence of the iterative solver. Numerical experiments are presented to show good performance of the approaches.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bader B W, Kolda T G. Efficient MATLAB computations with sparse and factored tensors. SIAM J Sci Comput, 2007, 30: 205–231
Bader B W, Kolda T G, MATLAB Tensor Toolbox, Version 2. 4. Available at http://csmr.ca.sandia.gov/~tgkolda/TensorToolbox/, 2010
Bai Z Z, Golub G H, Ng M K. Hermitian and skew-hermitian splitting methods for non-hermitian positive definite linear systems. SIAM J Matrix Anal Appl, 2003, 24: 603–626
Ballani J, Grasedyck L. A Projection method to solve linear systems in tensor format. Numer Linear Algebra Appl, doi: 10.1002/nla.1818
Beylkin G, Mohlenkamp M J. Algorithms for numerical analysis in high dimensions. SIAM J Sci Comput, 2005, 26: 2133–2159
Ding F, Chen T. Gradient based iterative algorithms for solving a class of matrix equations. IEEE Trans Automat Control, 2005, 50: 1216–1221
Ding F, Chen T. Iterative least squares solutions of coupled Sylvester matrix equations. Systems Control Lett, 2005, 54: 95–107
Golub G H, Nash S, Van Loan C F. A Hessenberg-Schur method for the problem AX + XB = C. IEEE Trans Auto Control, 1979, 24: 909–913
Golub G H, Van Loan C F. Matrix Computations, 3rd ed. Baltimore, Maryland: Johns Hopkins University Press, 1996
Grasedyck L. Existence and computation of low Kronecker-rank approximations for large linear systems of tensor product structure. Computing, 2004, 72: 247–265
Grasedyck L. Hierarchical singular value decomposition of tensors. SIAM J Matrix Anal Appl, 2010, 31: 2029–2054
Hu D Y, Reichel L. Krylov-subspace methods for the Sylvester equation. Linear Algebra Appl, 1992, 172: 283–313
Huyer W, Neumaier A. Global optimization by multilevel coordinate search. J Global Optim, 1999, 14: 331–355
Kolda T G, Bader B W. Tensor decompositions and applications. SIAM Rev, 2009, 51: 455–500
Kressner D, Tobler C. Krylov subspace methods for linear systems with tensor product structure. SIAM J Matrix Anal Appl, 2010, 31: 1688–1714
Langville A N, Stewart W J. A Kronecker product approximate preconditioner for SANs. Numer Linear Algebra Appl, 2004, 11: 723–752
Langville A N, Stewart W J. Testing the nearest Kronecker product preconditioner on Markov chains and stochastic automata networks. Informs J Comput, 2004, 16: 300–315
De Lathauwer L. A survey of tensor methods. In: Proceeding of the 2009 IEEE International Symposium on Circuits and Systems (ISCAS). Taipei: IEEE, 2009, 2773–2776
Li B W, Sun Y S, Zhang D W. Chebyshev collocation spectral methods for coupled radiation and conduction in a concentric spherical participating medium. ASME J Heat Transfer, 2009, 131: 062701–062709.
Li B W, Tian S, Sun Y S, et al. Schur-decomposition for 3D matrix equations and its application in solving radiative discrete ordinates equations discretized by Chebyshev collocation spectral method. J Comput Phys, 2010, 229: 1198–1212
Li J R, White J. Low-rank solutions of Lyapunov equations. SIAM J Matrix Anal Appl, 2002, 24: 260–280
Nagy J G, Kilmer M E. Kronecker product approximation for preconditioning in three-dimensional imaging applications. IEEE Transactions on Image Processing, 2006, 15: 604–613
Pitsianis N, Van Loan C F. Approximation with Kronecker products. In: Moonen M S, Golub G H, eds. Linear Algebra for Large Scale and Real Time Applications. Boston: Kluwer Academics, 1993, 293–314
Qi L, Sun W Y, Wang Y J. Numerical multilinear algebra and its applications. Front Math China, 2007, 2: 501–526
Saad Y. Iterative Methods for Sparse Linear Systems. Boston: PWS Publishing Company, 1996
Simoncini V. A new iterative method for solving large-scale Lyapunov matrix equations. SIAM J Sci Comput, 2007, 29: 1268–1288
Trefethen L N, Bau D. Numerical Linear Algebra. Philadelphia: SIAM, 1997
Xiang H, Grigori L. Kronecker product approximation preconditioners for convection-diffusion model problems, Numer Linear Algebra Appl, 2010, 17: 723–752
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chen, Z., Lu, L. A projection method and Kronecker product preconditioner for solving Sylvester tensor equations. Sci. China Math. 55, 1281–1292 (2012). https://doi.org/10.1007/s11425-012-4363-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11425-012-4363-5
Keywords
- Sylvester tensor equation
- Schur decomposition
- projection method
- nearest Kronecker product (NKP)
- preconditioning