Optimization of extrapolated Cayley transform with non-Hermitian positive definite matrix. (English) Zbl 1300.65020
Summary: For the extrapolated Cayley transform, we give necessary and sufficient conditions for guaranteeing its convergence and contraction (in the Euclidean norm). We derive upper bounds for the convergence and the contraction factors, and compute the optimal parameters minimizing these upper bounds and the corresponding optimal values of these upper bounds. Numerical computations show that these upper bounds are reasonably sharp compared with the exact convergence and the exact contraction factors of the extrapolated Cayley transform, respectively.
MSC:
| 65F30 | Other matrix algorithms (MSC2010) |
| 15B48 | Positive matrices and their generalizations; cones of matrices |
| 65F10 | Iterative numerical methods for linear systems |
Keywords:
Cayley transform; extrapolation; optimization; matrix splitting iteration; numerical examples; convergence; contraction factorReferences:
| [1] | Axelsson, O., Iterative Solution Methods (1994), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0795.65014 |
| [2] | Axelsson, O.; Neytcheva, M. G.; Ahmad, B., A comparison of iterative methods to solve complex valued linear algebraic systems (March 2013), Institute for Information Technology, Uppsala University, TR 2013-005 |
| [3] | Bai, Z.-Z., Splitting iteration methods for non-Hermitian positive definite systems of linear equations, Hokkaido Math. J., 36, 801-814 (2007) · Zbl 1138.65027 |
| [4] | Bai, Z.-Z., Optimal parameters in the HSS-like methods for saddle-point problems, Numer. Linear Algebra Appl., 16, 447-479 (2009) · Zbl 1224.65081 |
| [5] | Bai, Z.-Z., On semi-convergence of Hermitian and skew-Hermitian splitting methods for singular linear systems, Computing, 89, 171-197 (2010) · Zbl 1205.65146 |
| [6] | Bai, Z.-Z., Modulus-based matrix splitting iteration methods for linear complementarity problems, Numer. Linear Algebra Appl., 17, 917-933 (2010) · Zbl 1240.65181 |
| [7] | Bai, Z.-Z., Block alternating splitting implicit iteration methods for saddle-point problems from time-harmonic eddy current models, Numer. Linear Algebra Appl., 19, 914-936 (2012) · Zbl 1289.65048 |
| [8] | Bai, Z.-Z.; Benzi, M.; Chen, F., Modified HSS iteration methods for a class of complex symmetric linear systems, Computing, 87, 93-111 (2010) · Zbl 1210.65074 |
| [9] | Bai, Z.-Z.; Golub, G. H., Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems, IMA J. Numer. Anal., 27, 1-23 (2007) · Zbl 1134.65022 |
| [10] | Bai, Z.-Z.; Golub, G. H.; Li, C.-K., Optimal parameter in Hermitian and skew-Hermitian splitting method for certain two-by-two block matrices, SIAM J. Sci. Comput., 28, 583-603 (2006) · Zbl 1116.65039 |
| [11] | Bai, Z.-Z.; Golub, G. H.; Li, C.-K., Convergence properties of preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite matrices, Math. Comp., 76, 287-298 (2007) · Zbl 1114.65034 |
| [12] | Bai, Z.-Z.; Golub, G. H.; Lu, L.-Z.; Yin, J.-F., Block triangular and skew-Hermitian splitting methods for positive-definite linear systems, SIAM J. Sci. Comput., 26, 844-863 (2005) · Zbl 1079.65028 |
| [13] | 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., 24, 603-626 (2003) · Zbl 1036.65032 |
| [14] | Bai, Z.-Z.; Golub, G. H.; Ng, M. K., On successive overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iterations, Numer. Linear Algebra Appl., 14, 319-335 (2007) · Zbl 1199.65097 |
| [15] | Bai, Z.-Z.; Golub, G. H.; Pan, J.-Y., Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems, Numer. Math., 98, 1-32 (2004) · Zbl 1056.65025 |
| [16] | Bai, Z.-Z.; Guo, X.-X.; Xu, S.-F., Alternately linearized implicit iteration methods for the minimal nonnegative solutions of the nonsymmetric algebraic Riccati equations, Numer. Linear Algebra Appl., 13, 655-674 (2006) · Zbl 1174.65381 |
| [17] | Bai, Z.-Z.; Krukier, L. A.; Martynova, T. S., Two-step iterative methods for solving the stationary convection-diffusion equation with a small parameter at the highest derivative on a uniform grid, Comput. Math. Math. Phys., 46, 282-293 (2006) · Zbl 1210.39018 |
| [18] | Bai, Z.-Z.; Yin, J.-F.; Su, Y.-F., A shift-splitting preconditioner for non-Hermitian positive definite matrices, J. Comput. Math., 24, 539-552 (2006) · Zbl 1120.65054 |
| [19] | Benzi, M., A generalization of the Hermitian and skew-Hermitian splitting iteration, SIAM J. Matrix Anal. Appl., 31, 360-374 (2009) · Zbl 1191.65025 |
| [20] | Benzi, M.; Guo, X.-P., A dimensional split preconditioner for Stokes and linearized Navier-Stokes equations, Appl. Numer. Math., 61, 66-76 (2011) · Zbl 1302.65074 |
| [21] | Bertaccini, D.; Golub, G. H.; Serra Capizzano, S.; Tablino Possio, C., Preconditioned HSS methods for the solution of non-Hermitian positive definite linear systems and applications to the discrete convection-diffusion equation, Numer. Math., 99, 441-484 (2005) · Zbl 1068.65041 |
| [22] | van Bokhoven, W. M.G., Piecewise-linear modelling and analysis (1981), Proefschrift, Eindhoven |
| [23] | Chiang, C.-Y.; Fan, H.-Y.; Lin, W.-W., A structured doubling algorithm for discrete-time algebraic Riccati equations with singular control weighting matrices, Taiwanese J. Math., 14, 933-954 (2010) · Zbl 1206.65169 |
| [24] | Chikina, L. G.; Krukier, B. L., Solution of linear equation systems with a dominant skew-symmetric part using the product triangular iterative method, Comput. Methods Appl. Math., 3, 647-650 (2003) · Zbl 1038.65026 |
| [25] | Coxeter, H. S.M., Introduction to Geometry (1989), John Wiley & Sons: John Wiley & Sons New York · Zbl 0095.34502 |
| [26] | Deift, E.; Nanda, T.; Tomei, T., Ordinary differential equations and the symmetric eigenvalue problem, SIAM J. Numer. Anal., 20, 1-22 (1983) · Zbl 0526.65032 |
| [27] | Diele, F.; Lopez, L.; Peluso, R., The Cayley transform in the numerical solution of unitary differential systems, Adv. Comput. Math., 8, 317-334 (1998) · Zbl 0904.65069 |
| [28] | Dong, J.-L.; Jiang, M.-Q., A modified modulus method for symmetric positive-definite linear complementarity problems, Numer. Linear Algebra Appl., 16, 129-143 (2009) · Zbl 1224.65152 |
| [29] | Elman, H. C.; Golub, G. H., Iterative methods for cyclically reduced non-self-adjoint linear systems, Math. Comp., 54, 671-700 (1990) · Zbl 0699.65021 |
| [30] | Elman, H. C.; Golub, G. H., Iterative methods for cyclically reduced non-self-adjoint linear systems II, Math. Comp., 56, 215-242 (1991) · Zbl 0716.65096 |
| [31] | Fallat, S. M.; Tsatsomeros, M. J., On the Cayley transform of positivity classes of matrices, Electron. J. Linear Algebra, 9, 190-196 (2002) · Zbl 1023.15009 |
| [32] | Gao, Y.-H.; Bai, Z.-Z., On inexact Newton methods based on doubling iteration scheme for non-symmetric algebraic Riccati equations, Numer. Linear Algebra Appl., 18, 325-341 (2011) · Zbl 1249.65093 |
| [33] | Greif, C.; Varah, J. M., Iterative solution of cyclically reduced systems arising from discretization of the three-dimensional convection-diffusion equation, SIAM J. Sci. Comput., 19, 1918-1940 (1998) · Zbl 0916.65028 |
| [34] | Greif, C.; Varah, J. M., Block stationary methods for nonsymmetric cyclically reduced systems arising from three-dimensional elliptic equations, SIAM J. Matrix Anal. Appl., 20, 1038-1059 (1999) · Zbl 0936.65125 |
| [35] | Guo, X.-X.; Lin, W.-W.; Xu, S.-F., A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation, Numer. Math., 103, 393-412 (2006) · Zbl 1097.65055 |
| [36] | Hadjidimos, A.; Lapidakis, M., Stationary biparametric ADI preconditioners for conjugate gradient methods, J. Comput. Appl. Math., 205, 364-381 (2007) · Zbl 1120.65036 |
| [37] | Hadjidimos, A.; Lapidakis, M.; Tzoumas, M., On iterative solution for linear complementarity problem with an \(H_+\)-matrix, SIAM J. Matrix Anal. Appl., 33, 97-110 (2012) · Zbl 1251.65088 |
| [38] | Hadjidimos, A.; Tzoumas, M., The principle of extrapolation and the Cayley transform, Linear Algebra Appl., 429, 2465-2480 (2008) · Zbl 1156.65027 |
| [39] | Hadjidimos, A.; Tzoumas, M., On the optimal complex extrapolation of the complex Cayley transform, Linear Algebra Appl., 430, 619-632 (2009) · Zbl 1190.65051 |
| [40] | Hadjidimos, A.; Tzoumas, M., Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem, Linear Algebra Appl., 431, 197-210 (2009) · Zbl 1168.65027 |
| [41] | Hassibi, B.; Hochwald, B., Cayley differential unitary space-time codes, IEEE Trans. Inform. Theory, 48, 1485-1503 (2002) · Zbl 1061.94001 |
| [42] | Hochwald, B. M.; Marzetta, T. L., Unitary space-time modulation for multiple-antenna communication in Rayleigh flat-fading, IEEE Trans. Inform. Theory, 46, 543-564 (2000) · Zbl 0999.94511 |
| [43] | Huang, T.-M.; Lin, W.-W., Structured doubling algorithms for weakly stabilizing Hermitian solutions of algebraic Riccati equations, Linear Algebra Appl., 430, 1452-1478 (2009) · Zbl 1169.65038 |
| [44] | Iserles, A., On Cayley-transform methods for the discretization of Lie-group equations, Found. Comput. Math., 1, 129-160 (2001) · Zbl 1014.65060 |
| [45] | Jing, Y.-D.; Hassibi, B., Unitary space-time modulation via Cayley transform, IEEE Trans. Signal Process., 51, 2891-2904 (2003) · Zbl 1369.94392 |
| [46] | Johnson, C. R.; Krukier, L. A., General resolution of a convergence question of L. Krukier, Numer. Linear Algebra Appl., 16, 949-950 (2009) · Zbl 1224.15044 |
| [47] | Kappel, N. W.; Watson, L. T., Iterative algorithms for the linear complementarity problem, Int. J. Comput. Math., 19, 273-297 (1986) · Zbl 0654.65047 |
| [48] | Kellogg, R. B., Another alternating-direction-implicit method, J. Soc. Ind. Appl. Math., 11, 976-979 (1963) · Zbl 0214.14703 |
| [49] | Krishnaprasad, P. S.; Tan, X.-B., Cayley transforms in micromagnetics, Phys. B, 306, 195-199 (2001) |
| [50] | Krukier, L. A.; Chikina, L. G.; Belokon, T. V., Triangular skew-symmetric iterative solvers for strongly nonsymmetric positive real linear system of equations, Appl. Numer. Math., 41, 89-105 (2002) · Zbl 1004.65042 |
| [51] | Krukier, L. A.; Martynova, T. S.; Bai, Z.-Z., Product-type skew-Hermitian triangular splitting iteration methods for strongly non-Hermitian positive definite linear systems, J. Comput. Appl. Math., 232, 3-16 (2009) · Zbl 1184.65038 |
| [52] | Leenaerts, D. M.W.; van Bokhoven, W. M.G., Piecewise Linear Modeling and Analysis (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht |
| [53] | Lewis, D.; Simo, J. C., Conserving algorithms for the dynamics of Hamiltonian systems on Lie groups, J. Nonlinear Sci., 4, 253-299 (1994) · Zbl 0799.58069 |
| [54] | Lin, W.-W.; Xu, S.-F., Convergence analysis of structure-preserving doubling algorithms for Riccati-type matrix equations, SIAM J. Matrix Anal. Appl., 28, 26-39 (2006) · Zbl 1116.65051 |
| [55] | Marchuk, G. I., Methods of Computational Mathematics (1973), Nauka: Nauka Novosibirsk, (in Russian) |
| [56] | Meerbergen, K.; Spence, A.; Roose, D., Shift-invert and Cayley transforms for detection of rightmost eigenvalues of nonsymmetric matrices, BIT, 34, 409-423 (1994) · Zbl 0814.65037 |
| [57] | Murty, K. G., Linear Complementarity, Linear and Nonlinear Programming (1988), Heldermann-Verlag: Heldermann-Verlag Berlin · Zbl 0634.90037 |
| [58] | Peaceman, D. W.; Rachford, H. H., The numerical solution of parabolic and elliptic differential equations, J. Soc. Ind. Appl. Math., 3, 28-41 (1955) · Zbl 0067.35801 |
| [59] | Silverman, R. A., Introductory Complex Analysis (1967), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0145.29804 |
| [60] | Wang, L.; Bai, Z.-Z., Skew-Hermitian triangular splitting iteration methods for non-Hermitian positive definite linear systems of strong skew-Hermitian parts, BIT, 44, 363-386 (2004) · Zbl 1069.65031 |
| [61] | Yang, A.-L.; Wu, Y.-J.; Wu, Y.-Q.; Ren, D.-W., Bi-parameter incremental unknowns ADI iterative methods for elliptic problems, Numer. Algorithms, 60, 483-499 (2012) · Zbl 1253.65169 |
| [62] | Zanna, A., Collocation and relaxed collocation for the FER and the Magnus expansions, SIAM J. Numer. Anal., 36, 1145-1182 (1999) · Zbl 0936.65092 |
| [63] | Zhang, L.-L., Two-step modulus-based matrix splitting iteration method for linear complementarity problems, Numer. Algorithms, 57, 83-99 (2011) · Zbl 1219.65057 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
