Abstract
This paper concentrates on applying reordering algorithms as a preprocessing step of a restarted Generalized Minimal Residual (GMRES for short) solver preconditioned by three ILU-type preconditioners. This paper investigates the effect of 13 orderings on the convergence of the preconditioned GMRES solver restarted every 50 steps when applied to nine real large-scale nonsymmetric and not positive definite matrices. Specifically, this paper shows the most promising combination of preconditioners and reordering for each linear system used.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Gonzaga de Oliveira, S.L., Carvalho, C., Osthoff, C.: The effect of symmetric permutations on the convergence of are started GMRES solver with ILU-type preconditioners. In: 2019 Winter Simulation Conference (WSC), National Harbor, MA,USA, pp. 3219–3230. IEEE (2019)
Benzi, M., Haws, J.C., Tuma, M.: Preconditioning highly indefinite and nonsymmetric matrices. SIAM J. Sci. Comput. 22(4), 1333–1353 (2000)
Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7, 856–869 (1986)
Benzi, M., Szyld, D.B., Van Duin, A.: Orderings for incomplete factorization preconditioning of nonsymmetric problems. SIAM J. Sci. Comput. 20(5), 1652–1670 (1999)
Camata, J.J., Rossa, A.L., Valli, A.M.P., Catabriga, L., Carey, G.F., Coutinho, A.L.G.A.: Reordering and incomplete preconditioning in serial and parallel adaptive mesh refinement and coarsening flow solutions. Int. J. Numer. Meth. Fl. 69(4), 802–823 (2012)
Gonzaga de Oliveira, S.L., Bernardes, J.A.B., Chagas, G.O.: An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method. Comput. Appl. Math. 37(3), 2965–3004 (2017). https://doi.org/10.1007/s40314-017-0490-5
Saad, Y.: ILUT: a dual threshold incomplete LU factorization. Numer. Linear Algebra Appl. 1(4), 387–402 (1994)
Li, N., Saad, Y., Chow, E.: Crout versions of ILU for general sparse matrices. SIAM J. Sci. Comput. 25(2), 716–728 (2003)
Saad, Y., Suchomel, B.: ARMS: an algebraic recursive multilevel solver for general sparse linear systems. Numer. Linear Algebra Appl. 9(5), 359–378 (2002)
Saad, Y.: ITSOL vol 2.0: Iterative solvers package (2016)
Gonzaga de Oliveira, S.L., Bernardes, J.A.B., Chagas, G.O.: An evaluation of low-cost heuristics for matrix bandwidth and profile reductions. Comput. Appl. Math. 37(2), 1412–1471 (2016). https://doi.org/10.1007/s40314-016-0394-9
George, A., Liu, J.W.: Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Englewood Cliffs (1981)
Gonzaga de Oliveira, S.L., Abreu, A.A.A.M., Robaina, D.T., Kischnhevsky, M.: An evaluation of four reordering algorithms to reduce the computational cost of the Jacobi-preconditioned conjugate gradient method using high-precision arithmetic. Int. J. Bus. Intell. Data Min. 12(2), 190–209 (2017)
Gonzaga de Oliveira, S.L., Abreu, A.A.A.M.: An evaluation of pseudoperipheral vertex finders for the reverse Cuthill-Mckee method for bandwidth and profile reductions of symmetric matrices. In: Proceedings of the 37th International Conference of the Chilean Computer Science Society (SCCC), Santiago, Chile, pp. 1–9. IEEE (2018). https://doi.org/10.1109/SCCC.2018.8705263
Koohestani, B., Poli, R.: A hyper-heuristic approach to evolving algorithms for bandwidth reduction based on genetic programming. In: Bramer, M., Petridis, M., Nolle, L. (eds.) Research and Development in Intelligent Systems XXVIII, SGAI 2011, pp. 93–106. Springer, London (2011). https://doi.org/10.1007/978-1-4471-2318-7_7
Medeiros, S.R.P., Pimenta, P.M., Goldenberg, P.: Algorithm for profile and wavefront reduction of sparse matrices with a symmetric structure. Eng. Comput. 10(3), 257–266 (1993)
Sloan, S.W.: A Fortran program for profile and wavefront reduction. Int. J. Numer. Meth. Eng. 28(11), 2651–2679 (1989)
Kumfert, G., Pothen, A.: Two improved algorithms for envelope and wavefront reduction. BIT Numer. Math. 37(3), 559–590 (1997)
Reid, J.K., Scott, J.A.: Ordering symmetric sparse matrices for small profile and wavefront. Int. J. Numer. Meth. Eng. 45(12), 1737–1755 (1999)
Cuthill, E., McKee, J.: Reducing the bandwidth of sparse symmetric matrices. In: Proceedings the 1969 24th International Conference, pp. 157–172. ACM (1969)
George, A.: Computer implementation of the finite element method. PhD thesis, Stanford University, Stanford (1971)
Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38(1), 1–25 (2011)
George, A., Liu, J.W.H.: An implementation of a pseudoperipheral node finder. ACM Trans. Math. Softw. 5(3), 284–295 (1979)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
de Oliveira, S.L.G., Carvalho, C., Osthoff, C. (2020). The Influence of Reordering Algorithms on the Convergence of a Preconditioned Restarted GMRES Method. In: Gervasi, O., et al. Computational Science and Its Applications – ICCSA 2020. ICCSA 2020. Lecture Notes in Computer Science(), vol 12249. Springer, Cham. https://doi.org/10.1007/978-3-030-58799-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-58799-4_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-58798-7
Online ISBN: 978-3-030-58799-4
eBook Packages: Computer ScienceComputer Science (R0)