A real-valued block conjugate gradient type method for solving complex symmetric linear systems with multiple right-hand sides

Yasunori Futamura; Takahiro Yano; Akira Imakura; Tetsuya Sakurai

Applications of Mathematics (2017)

  • Volume: 62, Issue: 4, page 333-355
  • ISSN: 0862-7940

Abstract

top
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.

How to cite

top

Futamura, Yasunori, et al. "A real-valued block conjugate gradient type method for solving complex symmetric linear systems with multiple right-hand sides." Applications of Mathematics 62.4 (2017): 333-355. <http://eudml.org/doc/294084>.

@article{Futamura2017,
abstract = {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.},
author = {Futamura, Yasunori, Yano, Takahiro, Imakura, Akira, Sakurai, Tetsuya},
journal = {Applications of Mathematics},
keywords = {linear system with multiple right-hand sides; complex symmetric matrices; block Krylov subspace methods},
language = {eng},
number = {4},
pages = {333-355},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A real-valued block conjugate gradient type method for solving complex symmetric linear systems with multiple right-hand sides},
url = {http://eudml.org/doc/294084},
volume = {62},
year = {2017},
}

TY - JOUR
AU - Futamura, Yasunori
AU - Yano, Takahiro
AU - Imakura, Akira
AU - Sakurai, Tetsuya
TI - A real-valued block conjugate gradient type method for solving complex symmetric linear systems with multiple right-hand sides
JO - Applications of Mathematics
PY - 2017
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 62
IS - 4
SP - 333
EP - 355
AB - 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.
LA - eng
KW - linear system with multiple right-hand sides; complex symmetric matrices; block Krylov subspace methods
UR - http://eudml.org/doc/294084
ER -

References

top
  1. Axelsson, O., Kucherov, A., 10.1002/1099-1506(200005)7:4<197::AID-NLA194>3.0.CO;2-S, Numer. Linear Algebra Appl. 7 (2000), 197-218. (2000) Zbl1051.65025MR1762967DOI10.1002/1099-1506(200005)7:4<197::AID-NLA194>3.0.CO;2-S
  2. Axelsson, O., Neytcheva, M., Ahmad, B., 10.1007/s11075-013-9764-1, Numer. Algorithms 66 (2014), 811-841. (2014) Zbl1307.65034MR3240302DOI10.1007/s11075-013-9764-1
  3. Bai, Z.-Z., Benzi, M., Chen, F., 10.1007/s00607-010-0077-0, Computing 87 (2010), 93-111. (2010) Zbl1210.65074MR2640009DOI10.1007/s00607-010-0077-0
  4. Bai, Z.-Z., Benzi, M., Chen, F., 10.1007/s11075-010-9441-6, Numer. Algorithms 56 (2011), 297-317. (2011) Zbl1209.65037MR2755673DOI10.1007/s11075-010-9441-6
  5. Bai, Z.-Z., Benzi, M., Chen, F., Wang, Z.-Q., 10.1093/imanum/drs001, IMA J. Numer. Anal. 33 (2013), 343-369. (2013) Zbl1271.65100MR3020961DOI10.1093/imanum/drs001
  6. Bai, Z.-Z., Golub, G. H., Ng, M. K., 10.1137/S0895479801395458, SIAM J. Matrix Anal. Appl. 24 (2003), 603-626. (2003) Zbl1036.65032MR1972670DOI10.1137/S0895479801395458
  7. Bai, Z.-Z., Golub, G. H., Ng, M. K., 10.1002/nla.517, Numer. Linear Algebra Appl. 14 (2007), 319-335 erratum ibid. 19 2012 891. (2007) Zbl1199.65097MR2310394DOI10.1002/nla.517
  8. CONQUEST: Linear Scaling DFT, http://www.order-n.org/. 
  9. Davis, T. A., Hu, Y., 10.1145/2049662.2049663, ACM Trans. Math. Softw. 38 (2011), Paper No. 1, 25 pages. (2011) Zbl06721804MR2865011DOI10.1145/2049662.2049663
  10. Day, D., Heroux, M. A., 10.1137/S1064827500372262, SIAM J. Sci. Comput. 23 (2001), 480-498. (2001) Zbl0992.65020MR1861261DOI10.1137/S1064827500372262
  11. Du, L., Futamura, Y., Sakurai, T., 10.1016/j.camwa.2013.09.023, Comput. Math. Appl. 66 (2014), 2446-2455. (2014) MR3128571DOI10.1016/j.camwa.2013.09.023
  12. Dubrulle, A. A., Retooling the method of block conjugate gradients, ETNA, Electron. Trans. Numer. Anal. 12 (2001), 216-233. (2001) Zbl0985.65021MR1847919
  13. Eigen, http://eigen.tuxfamily.org/. Zbl1362.81029
  14. Eisenstat, S. C., Elman, H. C., Schultz, M. H., 10.1137/0720023, SIAM J. Numer. Anal. 20 (1983), 345-357. (1983) Zbl0524.65019MR0694523DOI10.1137/0720023
  15. ELSES matrix library, http://www.elses.jp/matrix/. 
  16. Freund, R. W., 10.1137/0913023, SIAM J. Sci. Stat. Comput. 13 (1992), 425-448. (1992) Zbl0761.65018MR1145195DOI10.1137/0913023
  17. Futamura, Y., Tadano, H., Sakurai, T., 10.14495/jsiaml.2.127, JSIAM Lett. 2 (2010), 127-130. (2010) Zbl1271.65063MR3009397DOI10.14495/jsiaml.2.127
  18. Ikegami, T., Sakurai, T., 10.11650/twjm/1500405869, Taiwanese J. Math. 14 (2010), 825-837. (2010) Zbl1198.65071MR2667719DOI10.11650/twjm/1500405869
  19. Ikegami, T., Sakurai, T., Nagashima, U., 10.1016/j.cam.2009.09.029, J. Comput. Appl. Math. 233 (2010), 1927-1936. (2010) Zbl1185.65061MR2564028DOI10.1016/j.cam.2009.09.029
  20. Imakura, A., Du, L., Sakurai, T., 10.1016/j.aml.2014.02.007, Appl. Math. Lett. 32 (2014), 22-27. (2014) Zbl1311.65037MR3182841DOI10.1016/j.aml.2014.02.007
  21. Nikishin, A. A., Yeremin, A. Y., 10.1137/S0895479893247679, SIAM J. Matrix Anal. Appl. 16 (1995), 1135-1153. (1995) Zbl0837.65029MR1351461DOI10.1137/S0895479893247679
  22. O'Leary, D. P., 10.1016/0024-3795(80)90247-5, Linear Algebra Appl. 29 (1980), 293-322. (1980) Zbl0426.65011MR0562766DOI10.1016/0024-3795(80)90247-5
  23. Paige, C. C., Saunders, M. A., 10.1137/0712047, SIAM J. Numer. Anal. 12 (1975), 617-629. (1975) Zbl0319.65025MR0383715DOI10.1137/0712047
  24. Polizzi, E., 10.1103/physrevb.79.115112, Phys. Rev. B 79 (2009), 115112. (2009) DOI10.1103/physrevb.79.115112
  25. Saad, Y., Schultz, M. H., 10.1137/0907058, SIAM J. Sci. Stat. Comput. 7 (1986), 856-869. (1986) Zbl0599.65018MR0848568DOI10.1137/0907058
  26. Sakurai, T., Sugiura, H., 10.1016/S0377-0427(03)00565-X, J. Comput. Appl. Math. 159 (2003), 119-128. (2003) Zbl1037.65040MR2022322DOI10.1016/S0377-0427(03)00565-X
  27. Sakurai, T., Tadano, H., 10.14492/hokmj/1272848031, Hokkaido Math. J. 36 (2007), 745-757. (2007) Zbl1156.65035MR2378289DOI10.14492/hokmj/1272848031
  28. Sogabe, T., Zhang, S.-L., 10.1016/j.cam.2005.07.032, J. Comput. Appl. Math. 199 (2007), 297-303. (2007) Zbl1108.65028MR2269511DOI10.1016/j.cam.2005.07.032
  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. (2009) 
  30. Vorst, H. A. van der, 10.1137/0913035, SIAM J. Sci. Stat. Comput. 13 (1992), 631-644. (1992) Zbl0761.65023MR1149111DOI10.1137/0913035
  31. Vorst, H. A. van der, Melissen, J. B. M., 10.1109/20.106415, IEEE Transactions on Magnetics 26 (1990), 706-708. (1990) DOI10.1109/20.106415

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.