| Title:
|
A real-valued block conjugate gradient type method for solving complex symmetric linear systems with multiple right-hand sides (English) |
| Author:
|
Futamura, Yasunori |
| Author:
|
Yano, Takahiro |
| Author:
|
Imakura, Akira |
| Author:
|
Sakurai, Tetsuya |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
62 |
| Issue:
|
4 |
| Year:
|
2017 |
| Pages:
|
333-355 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
linear system with multiple right-hand sides |
| Keyword:
|
complex symmetric matrices |
| Keyword:
|
block Krylov subspace methods |
| MSC:
|
65F10 |
| MSC:
|
65F50 |
| idZBL:
|
Zbl 06770048 |
| idMR:
|
MR3686421 |
| DOI:
|
10.21136/AM.2017.0023-17 |
| . |
| Date available:
|
2017-08-31T12:44:47Z |
| Last updated:
|
2020-07-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/146833 |
| . |
| Reference:
|
[1] Axelsson, O., Kucherov, A.: Real valued iterative methods for solving complex symmetric linear systems.Numer. Linear Algebra Appl. 7 (2000), 197-218. Zbl 1051.65025, MR 1762967, 10.1002/1099-1506(200005)7:4<197::AID-NLA194>3.0.CO;2-S |
| Reference:
|
[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. Zbl 1307.65034, MR 3240302, 10.1007/s11075-013-9764-1 |
| Reference:
|
[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. Zbl 1210.65074, MR 2640009, 10.1007/s00607-010-0077-0 |
| Reference:
|
[4] Bai, Z.-Z., Benzi, M., Chen, F.: On preconditioned MHSS iteration methods for complex symmetric linear systems.Numer. Algorithms 56 (2011), 297-317. Zbl 1209.65037, MR 2755673, 10.1007/s11075-010-9441-6 |
| Reference:
|
[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. Zbl 1271.65100, MR 3020961, 10.1093/imanum/drs001 |
| Reference:
|
[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. Zbl 1036.65032, MR 1972670, 10.1137/S0895479801395458 |
| Reference:
|
[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. Zbl 1199.65097, MR 2310394, 10.1002/nla.517 |
| Reference:
|
[8] : CONQUEST: Linear Scaling DFT.http://www.order-n.org/. |
| Reference:
|
[9] Davis, T. A., Hu, Y.: The university of Florida sparse matrix collection.ACM Trans. Math. Softw. 38 (2011), Paper No. 1, 25 pages. Zbl 06721804, MR 2865011, 10.1145/2049662.2049663 |
| Reference:
|
[10] Day, D., Heroux, M. A.: Solving complex-valued linear systems via equivalent real formulations.SIAM J. Sci. Comput. 23 (2001), 480-498. Zbl 0992.65020, MR 1861261, 10.1137/S1064827500372262 |
| Reference:
|
[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. MR 3128571, 10.1016/j.camwa.2013.09.023 |
| Reference:
|
[12] Dubrulle, A. A.: Retooling the method of block conjugate gradients.ETNA, Electron. Trans. Numer. Anal. 12 (2001), 216-233. Zbl 0985.65021, MR 1847919 |
| Reference:
|
[13] : Eigen.http://eigen.tuxfamily.org/. Zbl 1362.81029 |
| Reference:
|
[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. Zbl 0524.65019, MR 0694523, 10.1137/0720023 |
| Reference:
|
[15] : ELSES matrix library.http://www.elses.jp/matrix/. |
| Reference:
|
[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. Zbl 0761.65018, MR 1145195, 10.1137/0913023 |
| Reference:
|
[17] Futamura, Y., Tadano, H., Sakurai, T.: Parallel stochastic estimation method of eigenvalue distribution.JSIAM Lett. 2 (2010), 127-130. Zbl 1271.65063, MR 3009397, 10.14495/jsiaml.2.127 |
| Reference:
|
[18] Ikegami, T., Sakurai, T.: Contour integral eigensolver for non-Hermitian systems: a Rayleigh-Ritz-type approach.Taiwanese J. Math. 14 (2010), 825-837. Zbl 1198.65071, MR 2667719, 10.11650/twjm/1500405869 |
| Reference:
|
[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. Zbl 1185.65061, MR 2564028, 10.1016/j.cam.2009.09.029 |
| Reference:
|
[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. Zbl 1311.65037, MR 3182841, 10.1016/j.aml.2014.02.007 |
| Reference:
|
[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. Zbl 0837.65029, MR 1351461, 10.1137/S0895479893247679 |
| Reference:
|
[22] O'Leary, D. P.: The block conjugate gradient algorithm and related methods.Linear Algebra Appl. 29 (1980), 293-322. Zbl 0426.65011, MR 0562766, 10.1016/0024-3795(80)90247-5 |
| Reference:
|
[23] Paige, C. C., Saunders, M. A.: Solutions of sparse indefinite systems of linear equations.SIAM J. Numer. Anal. 12 (1975), 617-629. Zbl 0319.65025, MR 0383715, 10.1137/0712047 |
| Reference:
|
[24] Polizzi, E.: Density-matrix-based algorithm for solving eigenvalue problems.Phys. Rev. B 79 (2009), 115112. 10.1103/physrevb.79.115112 |
| Reference:
|
[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. Zbl 0599.65018, MR 0848568, 10.1137/0907058 |
| Reference:
|
[26] Sakurai, T., Sugiura, H.: A projection method for generalized eigenvalue problems using numerical integration.J. Comput. Appl. Math. 159 (2003), 119-128. Zbl 1037.65040, MR 2022322, 10.1016/S0377-0427(03)00565-X |
| Reference:
|
[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. Zbl 1156.65035, MR 2378289, 10.14492/hokmj/1272848031 |
| Reference:
|
[28] Sogabe, T., Zhang, S.-L.: A COCR method for solving complex symmetric linear systems.J. Comput. Appl. Math. 199 (2007), 297-303. Zbl 1108.65028, MR 2269511, 10.1016/j.cam.2005.07.032 |
| Reference:
|
[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. |
| Reference:
|
[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. Zbl 0761.65023, MR 1149111, 10.1137/0913035 |
| Reference:
|
[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. 10.1109/20.106415 |
| . |
