About DML-CZ | FAQ | Conditions of Use | Math Archives | Contact Us
  Previous |  Up |  Next

Article

Futamura, Yasunori ; Yano, Takahiro ; Imakura, Akira ; Sakurai, Tetsuya
A real-valued block conjugate gradient type method for solving complex symmetric linear systems with multiple right-hand sides. (English). Applications of Mathematics, vol. 62 (2017), issue 4, pp. 333-355
MSC: 65F10, 65F50 | MR 3686421 | Zbl 06770048 | DOI: 10.21136/AM.2017.0023-17
Keywords:
linear system with multiple right-hand sides; complex symmetric matrices; block Krylov subspace methods
Summary:
We consider solving complex symmetric linear systems with multiple right-hand sides. We assume that the coefficient matrix has indefinite real part and positive definite imaginary part. We propose a new block conjugate gradient type method based on the Schur complement of a certain 2-by-2 real block form. The algorithm of the proposed method consists of building blocks that involve only real arithmetic with real symmetric matrices of the original size. We also present the convergence property of the proposed method and an efficient algorithmic implementation. In numerical experiments, we compare our method to a complex-valued direct solver, and a preconditioned and nonpreconditioned block Krylov method that uses complex arithmetic.
References:
[1] Axelsson, O., Kucherov, A.: Real valued iterative methods for solving complex symmetric linear systems. Numer. Linear Algebra Appl. 7 (2000), 197-218. DOI 10.1002/1099-1506(200005)7:4<197::AID-NLA194>3.0.CO;2-S | MR 1762967 | Zbl 1051.65025
[2] Axelsson, O., Neytcheva, M., Ahmad, B.: A comparison of iterative methods to solve complex valued linear algebraic systems. Numer. Algorithms 66 (2014), 811-841. DOI 10.1007/s11075-013-9764-1 | MR 3240302 | Zbl 1307.65034
[3] Bai, Z.-Z., Benzi, M., Chen, F.: Modified HSS iteration methods for a class of complex symmetric linear systems. Computing 87 (2010), 93-111. DOI 10.1007/s00607-010-0077-0 | MR 2640009 | Zbl 1210.65074
[4] Bai, Z.-Z., Benzi, M., Chen, F.: On preconditioned MHSS iteration methods for complex symmetric linear systems. Numer. Algorithms 56 (2011), 297-317. DOI 10.1007/s11075-010-9441-6 | MR 2755673 | Zbl 1209.65037
[5] Bai, Z.-Z., Benzi, M., Chen, F., Wang, Z.-Q.: Preconditioned MHSS iteration methods for a class of block two-by-two linear systems with applications to distributed control problems. IMA J. Numer. Anal. 33 (2013), 343-369. DOI 10.1093/imanum/drs001 | MR 3020961 | Zbl 1271.65100
[6] 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 (2003), 603-626. DOI 10.1137/S0895479801395458 | MR 1972670 | Zbl 1036.65032
[7] 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 (2007), 319-335 erratum ibid. 19 2012 891. DOI 10.1002/nla.517 | MR 2310394 | Zbl 1199.65097
[8] CONQUEST: Linear Scaling DFT. http://www.order-n.org/
[9] Davis, T. A., Hu, Y.: The university of Florida sparse matrix collection. ACM Trans. Math. Softw. 38 (2011), Paper No. 1, 25 pages. DOI 10.1145/2049662.2049663 | MR 2865011 | Zbl 06721804
[10] Day, D., Heroux, M. A.: Solving complex-valued linear systems via equivalent real formulations. SIAM J. Sci. Comput. 23 (2001), 480-498. DOI 10.1137/S1064827500372262 | MR 1861261 | Zbl 0992.65020
[11] Du, L., Futamura, Y., Sakurai, T.: Block conjugate gradient type methods for the approximation of bilinear form $C^H A^{-1} B$. Comput. Math. Appl. 66 (2014), 2446-2455. DOI 10.1016/j.camwa.2013.09.023 | MR 3128571
[12] Dubrulle, A. A.: Retooling the method of block conjugate gradients. ETNA, Electron. Trans. Numer. Anal. 12 (2001), 216-233. MR 1847919 | Zbl 0985.65021
[13] Eigen. http://eigen.tuxfamily.org/ Zbl 1362.81029
[14] Eisenstat, S. C., Elman, H. C., Schultz, M. H.: Variational iterative methods for nonsymmetric systems of linear equations. SIAM J. Numer. Anal. 20 (1983), 345-357. DOI 10.1137/0720023 | MR 0694523 | Zbl 0524.65019
[15] ELSES matrix library. http://www.elses.jp/matrix/
[16] Freund, R. W.: Conjugate gradient-type methods for linear systems with complex symmetric coefficient matrices. SIAM J. Sci. Stat. Comput. 13 (1992), 425-448. DOI 10.1137/0913023 | MR 1145195 | Zbl 0761.65018
[17] Futamura, Y., Tadano, H., Sakurai, T.: Parallel stochastic estimation method of eigenvalue distribution. JSIAM Lett. 2 (2010), 127-130. DOI 10.14495/jsiaml.2.127 | MR 3009397 | Zbl 1271.65063
[18] Ikegami, T., Sakurai, T.: Contour integral eigensolver for non-Hermitian systems: a Rayleigh-Ritz-type approach. Taiwanese J. Math. 14 (2010), 825-837. DOI 10.11650/twjm/1500405869 | MR 2667719 | Zbl 1198.65071
[19] Ikegami, T., Sakurai, T., Nagashima, U.: A filter diagonalization for generalized eigenvalue problems based on the Sakurai-Sugiura projection method. J. Comput. Appl. Math. 233 (2010), 1927-1936. DOI 10.1016/j.cam.2009.09.029 | MR 2564028 | Zbl 1185.65061
[20] Imakura, A., Du, L., Sakurai, T.: A block Arnoldi-type contour integral spectral projection method for solving generalized eigenvalue problems. Appl. Math. Lett. 32 (2014), 22-27. DOI 10.1016/j.aml.2014.02.007 | MR 3182841 | Zbl 1311.65037
[21] Nikishin, A. A., Yeremin, A. Y.: Variable block CG algorithms for solving large sparse symmetric positive definite linear systems on parallel computers. I. General iterative scheme. SIAM J. Matrix Anal. Appl. 16 (1995), 1135-1153. DOI 10.1137/S0895479893247679 | MR 1351461 | Zbl 0837.65029
[22] O'Leary, D. P.: The block conjugate gradient algorithm and related methods. Linear Algebra Appl. 29 (1980), 293-322. DOI 10.1016/0024-3795(80)90247-5 | MR 0562766 | Zbl 0426.65011
[23] Paige, C. C., Saunders, M. A.: Solutions of sparse indefinite systems of linear equations. SIAM J. Numer. Anal. 12 (1975), 617-629. DOI 10.1137/0712047 | MR 0383715 | Zbl 0319.65025
[24] Polizzi, E.: Density-matrix-based algorithm for solving eigenvalue problems. Phys. Rev. B 79 (2009), 115112. DOI 10.1103/physrevb.79.115112
[25] Saad, Y., Schultz, M. H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7 (1986), 856-869. DOI 10.1137/0907058 | MR 0848568 | Zbl 0599.65018
[26] Sakurai, T., Sugiura, H.: A projection method for generalized eigenvalue problems using numerical integration. J. Comput. Appl. Math. 159 (2003), 119-128. DOI 10.1016/S0377-0427(03)00565-X | MR 2022322 | Zbl 1037.65040
[27] Sakurai, T., Tadano, H.: CIRR: a Rayleigh-Ritz type method with contour integral for generalized eigenvalue problems. Hokkaido Math. J. 36 (2007), 745-757. DOI 10.14492/hokmj/1272848031 | MR 2378289 | Zbl 1156.65035
[28] Sogabe, T., Zhang, S.-L.: A COCR method for solving complex symmetric linear systems. J. Comput. Appl. Math. 199 (2007), 297-303. DOI 10.1016/j.cam.2005.07.032 | MR 2269511 | Zbl 1108.65028
[29] Tadano, H., Sakurai, T.: A block Krylov subspace method for the contour integral method and its application to molecular orbital computations. IPSJ Trans. Adv. Comput. Syst. 2 (2009), 10-18 Japanese.
[30] Vorst, H. A. van der: Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the Solution of nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 13 (1992), 631-644. DOI 10.1137/0913035 | MR 1149111 | Zbl 0761.65023
[31] Vorst, H. A. van der, Melissen, J. B. M.: A Petrov-Galerkin type method for solving $Axk=b$, where $A$ is symmetric complex. IEEE Transactions on Magnetics 26 (1990), 706-708. DOI 10.1109/20.106415
Partner of
EuDML logo