×

Restarted Hessenberg method for solving shifted nonsymmetric linear systems. (English) Zbl 1377.65042

Summary: It is known that the restarted full orthogonalization method (FOM) outperforms the restarted generalized minimum residual (GMRES) method in several circumstances for solving shifted linear systems when the shifts are handled simultaneously. Many variants of them have been proposed to enhance their performance. We show that another restarted method, the restarted Hessenberg method [M. Heyouni, Méthode de Hessenberg généralisée et applications. Lille: Université des Sciences et Technologies de Lille (PhD Thesis) (1996)] based on Hessenberg procedure, can effectively be employed, which can provide accelerating convergence rate with respect to the number of restarts. Theoretical analysis shows that the new residual of shifted restarted Hessenberg method is still collinear with each other. In these cases where the proposed algorithm needs less enough elapsed CPU time to converge than the earlier established restarted shifted FOM, the weighted restarted shifted FOM, and some other popular shifted iterative solvers based on the short-term vector recurrence, as shown via extensive numerical experiments involving the recently popular application of handling time fractional differential equations.

MSC:

65F10 Iterative numerical methods for linear systems
65F25 Orthogonalization in numerical linear algebra
35R11 Fractional partial differential equations
65M06 Finite difference methods for initial value and initial-boundary value problems involving PDEs
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Datta, B. N.; Saad, Y., Arnoldi methods for large Sylvester-like observer matrix equations, and an associated algorithm for partial spectrum assignment, Linear Algebra Appl., 154-156, 225-244 (1991) · Zbl 0734.65037
[2] Ahmad, M. I.; Szyld, D. B.; van Gijzen, M. B., Preconditioned multishift BiCG for \(H_2\)-optimal model reduction, SIAM J. Matrix Anal. Appl., 38, 401-424 (2017) · Zbl 1365.65080
[3] Feriani, A.; Perotti, F.; Simoncini, V., Iterative system solvers for the frequency analysis of linear mechanical systems, Comput. Methods Appl. Mech. Engrg., 190, 1719-1739 (2000) · Zbl 0981.70005
[4] Sakurai, T.; Sugiura, H., A projection method for generalized eigenvalue problems using numerical integration, J. Comput. Appl. Math., 159, 119-128 (2003) · Zbl 1037.65040
[5] Weideman, J. A.C.; Trefethen, L. N., Parabolic and hyperbolic contours for computing the Bromwich integral, Math. Comp., 76, 1341-1356 (2007) · Zbl 1113.65119
[6] Garrappa, R.; Popolizio, M., On the use of matrix functions for fractional partial differential equations, Math. Comput. Simulation, 81, 1045-1056 (2011) · Zbl 1210.65162
[7] Bloch, J. C.R.; Frommer, A.; Lang, B.; Wettig, T., An iterative method to compute the sign function of a non-Hermitian matrix and its application to the overlap Dirac operator at nonzero chemical potential, Comput. Phys. Comm., 177, 933-943 (2007) · Zbl 1196.65085
[8] Chan, T. F.; Ng, M. K., Galerkin projection methods for solving multiple linear systems, SIAM J. Sci. Comput., 21, 836-850 (1999) · Zbl 0954.65027
[9] Baumann, M.; van Gijzen, M. B., Nested krylov methods for shifted linear systems, SIAM J. Sci. Comput., 37, S90-S112 (2015) · Zbl 06502306
[10] Wu, G.; Wang, Y.-C.; Jin, X.-Q., A preconditioned and shifted GMRES algorithm for the PageRank problem with multiple damping factors, SIAM J. Sci. Comput., 34, A2558-A2575 (2012) · Zbl 1263.65037
[11] Saibaba, A. K.; Bakhos, T.; Kitanidis, P. K., A flexible Krylov solver for shifted systems with application to oscillatory hydraulic tomography, SIAM J. Sci. Comput., 35, A3001-A3023 (2013) · Zbl 1288.65041
[12] Sogabe, T.; Hoshi, T.; Zhang, S.-L.; Fujiwara, T., A numerical method for calculating the green’s function arising from electronic structure theory, (Kaneda, Y.; Kawamura, H.; Sasai, M., Frontiers of Computational Science (2007), Springer-Verlag: Springer-Verlag Berlin/Heidelberg), 189-195 · Zbl 1344.78022
[13] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM: SIAM Philadelphia, PA · Zbl 1002.65042
[14] B. Jegerlehner, Krylov space solvers for shifted linear systems, arXiv preprint, hep-lat/9612014http://arxiv.org/abs/hep-lat/9612014; B. Jegerlehner, Krylov space solvers for shifted linear systems, arXiv preprint, hep-lat/9612014http://arxiv.org/abs/hep-lat/9612014
[15] Jing, Y.-F.; Huang, T.-Z., Restarted weighted full orthogonalization method for shifted linear systems, Comput. Math. Appl., 57, 1583-1591 (2009) · Zbl 1186.65061
[16] Yin, J.-F.; Yin, G.-J., Restarted full orthogonalization method with deflation for shifted linear systems, Numer. Math. Theor. Meth. Appl., 7, 399-412 (2014) · Zbl 1324.65067
[17] Freund, R. W., Solution of shifted linear systems by quasi-minimal residual iterations, (Reichel, L.; Ruttan, A.; Varga, R. S., Numerical Linear Algebra (1993), de Gruyter: de Gruyter Berlin, Germany), 101-121 · Zbl 0794.65028
[18] Kirchner, S., IDR-Verfahren Zur LÖSung Von Familien Geshifteter Linearer Gleichungssysteme, Diplomarbeit, Fachbereich Mathematik (2011), Bergische Universität Wuppertal: Bergische Universität Wuppertal Germany, (in German)
[19] Du, L.; Sogabe, T.; Zhang, S.-L., IDR \((s)\) for solving shifted nonsymmetric linear systems, J. Comput. Appl. Math., 274, 35-43 (2015) · Zbl 1310.65037
[20] van Gijzen, M. B.; Sleijpen, G. L.G.; Zemke, J.-P. M., Flexible and multi-shift induced dimension reduction algorithms for solving large sparse linear systems, Numer. Linear Algebra Appl., 22, 1-25 (2015) · Zbl 1363.65058
[21] Sogabe, T., Extensions of the Conjugate Residual Method (Ph.D Dissertation) (2006), Department of Applied Physics, University of Tokyo: Department of Applied Physics, University of Tokyo Japan, Available online at http://www.ist.aichi-pu.ac.jp/person/sogabe/thesis.pdf
[22] Frommer, A., BiCGStab \(( \ell )\) for families of shifted linear systems, Computing, 70, 87-109 (2003) · Zbl 1239.65022
[23] Gu, X.-M.; Huang, T.-Z.; Meng, J.; Sogabe, T.; Li, H.-B.; Li, L., BiCR-type methods for families of shifted linear systems, Comput. Math. Appl., 68, 746-758 (2014) · Zbl 1362.65039
[24] Dehghan, M.; Mohammadi-Arani, R., Generalized product-type methods based on bi-conjugate gradient (GPBiCG) for solving shifted linear systems, Comput. Appl. Math. (2016), 16 pages, in press. DOI: 10.1007/s40314-016-0315-y · Zbl 1383.65025
[25] Ahuja, K.; de Sturler, E.; Gugercin, S.; Chang, E. R., Recycling BiCG with an application to model reduction, SIAM J. Sci. Comput., 34, A1925-A1949 (2012) · Zbl 1253.65040
[26] Frommer, A.; Glässner, U., Restarted GMRES for shifted linear systems, SIAM J. Sci. Comput., 19, 15-26 (1998) · Zbl 0912.65023
[27] Gu, G., Restarted GMRES augmented with harmonic Ritz vectors for shifted linear systems, Int. J. Comput. Math., 82, 837-849 (2005) · Zbl 1078.65023
[28] Soodhalter, K. M.; Szyld, D. B.; Xue, F., Krylov subspace recycling for sequences of shifted linear systems, Appl. Numer. Math., 81, 105-118 (2014) · Zbl 1291.65108
[29] Darnell, D.; Morgan, R. B.; Wilcox, W., Deflated GMRES for systems with multiple shifts and multiple right-hand sides, Linear Algebra Appl., 429, 2415-2434 (2008) · Zbl 1153.65032
[30] Simoncini, V., Restarted full orthogonalization method for shifted linear systems, BIT, 43, 459-466 (2003) · Zbl 1033.65015
[31] Morgan, R. B., A restarted GMRES method augmented with eigenvectors, SIAM J. Matrix Anal. Appl., 16, 1154-1171 (1995) · Zbl 0836.65050
[32] Wilkinson, J. H., The Algebraic Eigenvalue Problem (1965), Clarendon Press: Clarendon Press Oxford, UK · Zbl 0258.65037
[33] Sadok, H., CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm, Numer. Alg., 20, 303-321 (1999) · Zbl 0936.65031
[34] Heyouni, M.; Sadok, H., A new implementation of the CMRH method for solving dense linear systems, J. Comput. Appl. Math., 213, 387-399 (2008) · Zbl 1136.65036
[35] Heyouni, M., Méthode De Hessenberg GénéRalisée et Applications (Ph.D thesis) (1996), Université des Sciences et Technologies de Lille: Université des Sciences et Technologies de Lille France, Available online at http://ori.univ-lille1.fr/notice/view/univ-lille1-ori-134864
[36] Sadok, H., Méthodes de projections pour les systèmes linéaires et non linéaires (Habilitation thesis) (1994), University of Lille1: University of Lille1 Lille, France
[37] Sadok, H.; Szyld, D. B., A new look at CMRH and its relation to GMRES, BIT, 52, 485-501 (2012) · Zbl 1247.65045
[38] Duintjer Tebbens, J.; Meurant, G., On the convergence of Q-OR and Q-MR Krylov methods for solving nonsymmetric linear systems, BIT, 56, 77-97 (2016) · Zbl 1350.65023
[39] Zhang, K.; Gu, C., A flexible CMRH algorithm for nonsymmetric linear systems, J. Appl. Math. Comput., 45, 43-61 (2014) · Zbl 1314.65056
[40] Heyouni, M.; Sadok, H., On a variable smoothing procedure for Krylov subspace methods, Linear Algebra Appl., 268, 131-149 (1998) · Zbl 0886.65031
[41] Hessenberg, K., BehandLung Linearer Eigenwertaufgaben Mit Hilfe Der Hamilton-Cayleyschen Gleichung, Numerische Verfahren, Bericht 1 (1940), Institut für Praktische Mathematik (IPM), Technische Hochschule Darmstadt, The scanned report and a biographical sketch of Karl Hessenberg’s life are available at http://www.hessenberg.de/karl1.html
[42] Stephens, D., ELMRES: An Oblique Projection Method To Solve Sparse Non-Symmetric Linear Systems (Ph.D dissertation) (1999), Florida Institute of Technology: Florida Institute of Technology Melbourne, USA, Available online at http://ncsu.edu/hpc/Documents/Publications/gary_howell/stephens.pdf
[43] Howell, G.; Stephens, D., ELMRES, an Oblique Projection Method for Solving Systems of Sparse Linear Equations, Technical Report (2000), Florida Institute of Technology, 18 pages. Available online at http://ncsu.edu/hpc/Documents/Publications/gary_howell/elmres320ps
[44] Higham, N. J., Accuracy and Stability of Numerical Algorithms (2002), SIAM: SIAM Philadelphia, PA · Zbl 1011.65010
[45] Schweitzer, M., Any finite convergence curve is possible in the initial iterations of restarted FOM, Electron. Trans. Numer. Anal., 45, 133-145 (2016) · Zbl 1338.65086
[46] Golub, G. H.; Van Loan, C. F., Matrix Computations (2013), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 1268.65037
[47] Davis, T.; Hu, Y., The university of florida sparse matrix collection, ACM Trans. Math. Software, 38, 1 (2011), Article 1, 25 pages. Available online at http://www.cise.ufl.edu/research/sparse/matrices/ · Zbl 1365.65123
[48] H.-W. Sun, W. Wang, A fourth order compact BVM scheme for the two dimensional heat equations, in: H.R. Arabnia (Ed.), Proceedings of the 2008 International Conference on Scientific Computing, Las Vegas, Nevada, USA, 2008, pp. 310-314.; H.-W. Sun, W. Wang, A fourth order compact BVM scheme for the two dimensional heat equations, in: H.R. Arabnia (Ed.), Proceedings of the 2008 International Conference on Scientific Computing, Las Vegas, Nevada, USA, 2008, pp. 310-314.
[49] Zhai, S.; Gui, D.; Huang, P.; Feng, X., A novel high-order ADI method for 3D fractional convection-diffusion equations, Int. Commun. Heat Mass Transfer, 66, 212-217 (2015)
[50] Podlubny, I., Fractional Differential Equations (1999), Academic Press: Academic Press San Diego, CA · Zbl 0918.34010
[51] Trefethen, L. N.; Weideman, J. A.C.; Schmelzer, T., Talbot quadratures and rational approximations, BIT, 46, 653-670 (2006) · Zbl 1103.65030
[52] Gu, X.-M.; Huang, T.-Z.; Carpentieri, B.; Imakura, A.; Zhang, K.; Du, L., Variants of the CMRH Method for Solving Multi-Shifted Non-Hermitian Linear Systems, Technical Report (2016), University of Groningen: University of Groningen Groningen, the Netherlands, 34 pages. Also available online at https://arxiv.org/abs/161100288
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.