Skip to main content
Have a personal or library account? Click to login
The Non–Symmetric s–Step Lanczos Algorithm: Derivation of Efficient Recurrences and Synchronization–Reducing Variants of BiCG and QMR Cover

The Non–Symmetric s–Step Lanczos Algorithm: Derivation of Efficient Recurrences and Synchronization–Reducing Variants of BiCG and QMR

International Journal of Applied Mathematics and Computer Science
Volume 25 (2015): Issue 4 (December 2015)
By:  and    
Open Access
|Dec 2015
References

References

  1. Balay, S., Gropp, W.D., McInnes, L.C. and Smith, B.F. (1997). Efficient management of parallelism in object oriented numerical software libraries,E. Arge(Eds.),, Birkhäuser Press, Boston, MA, pp. 163–202.
    Open DOISearch in Google Scholar
  2. Bücker, H.M. (2002). Iteratively solving large sparse linear systems on parallel computers,J. Grotendorst, D. Marx and A. Muramatsu (Eds.),, NIC Series, Vol. 10, John Von Neumann Institute for Computing, Jülich, pp. 521–548.
    Search in Google Scholar
  3. Bücker, H.M. and Sauren, M. (1996). A parallel version of the quasi-minimal residual method based on coupled two-term recurrences,J. Waśniewski(Eds.),, Lecture Notes in Computer Science, Vol. 1184, Springer, Berlin, pp. 157–165.
    Open DOISearch in Google Scholar
  4. Bücker, H.M. and Sauren, M. (1997). A variant of the biconjugate gradient method suitable for massively parallel computing,G. Bilardi(Eds.),, Lecture Notes in Computer Science, Vol. 1253, Springer, Berlin, pp. 72–79.
    Open DOISearch in Google Scholar
  5. Bücker, H.M. and Sauren, M. (1999). Reducing global synchronization in the biconjugate gradient method,T. Yang (Ed.),, Kluwer Academic Publishers, Norwell, MA, pp. 63–76.
    Open DOISearch in Google Scholar
  6. Cappello, F., Geist, A., Gropp, B., Kale, L., Kramer, B. and Snir, M. (2009). Toward exascale resilience,(4): 374–388.
    Open DOISearch in Google Scholar
  7. Carson, E. and Demmel, J. (2014). A residual replacement strategy for improving the maximum attainable accuracy of s-step Krylov subspace methods,(1): 22–43.
    Open DOISearch in Google Scholar
  8. Carson, E., Knight, N. and Demmel, J. (2014). Avoiding communication in nonsymmetric Lanczos-based Krylov subspace methods,(5): S42–S61.
    Open DOISearch in Google Scholar
  9. Chronopoulos, A.T. (1986). A class of parallel iterative methods implemented on multiprocessors,, Department of Computer Science, University of Illinois, Urbana, IL.
    Search in Google Scholar
  10. Chronopoulos, A.T. and Gear, C.W. (1989).-Step iterative methods for symmetric linear systems,(2): 153–168.
    Open DOISearch in Google Scholar
  11. Chronopoulos, A.T. and Swanson, C.D. (1996). Parallel iterative-step methods for unsymmetric linear systems,(5): 623–641.
    Open DOISearch in Google Scholar
  12. Curfman McInnes, L., Smith, B., Zhang, H. and Mills, R.T. (2014). Hierarchical Krylov and nested Krylov methods for extreme-scale computing,(1): 17–31.
    Open DOISearch in Google Scholar
  13. Davis, N.E., Robey, R.W., Ferenbaugh, C.R., Nicholaeff, D. and Trujillo, D.P. (2012). Paradigmatic shifts for exascale supercomputing,(2): 1023–1044.
    Open DOISearch in Google Scholar
  14. Demmel, J., Heath, M. and van der Vorst, H. (1993). Parallel numerical linear algebra,(1): 111–197.
    Open DOISearch in Google Scholar
  15. Duff, I.S. (2012). European exascale software initiative: Numerical libraries, solvers and algorithms,D. Hutchison(Eds.),, Lecture Notes in Computer Science, Vol. 7155, Springer, Berlin, pp. 295–304.
    Open DOISearch in Google Scholar
  16. Duff, I.S. and van der Vorst, H.A. (1999). Developments and trends in the parallel solution of linear systems,(13–14): 1931–1970.
    Open DOISearch in Google Scholar
  17. Feuerriegel, S. and Bücker, H.M. (2013a). A normalization scheme for the non-symmetric-step Lanczos algorithm,J. Kolodziej(Eds.),, Lecture Notes in Computer Science, Vol. 8286, Springer, Berlin, pp. 30–39.
    Search in Google Scholar
  18. Feuerriegel, S. and Bücker, H.M. (2013b). Synchronization-reducing variants of the biconjugate gradient and the quasi-minimal residual methods,J. Kolodziej(Eds.),, Lecture Notes in Computer Science, Vol. 8285, Springer, Berlin, pp. 226–235.
    Search in Google Scholar
  19. Fischer, B. and Freund, R. (1994). An inner product-free conjugate gradient-like algorithm for Hermitian positive definite systems,J. Brown(Eds.),, SIAM, Philadelphia, PA, pp. 288–290.
    Search in Google Scholar
  20. Fletcher, R. (1976). Conjugate gradient methods for indefinite systems,G. Watson (Ed.),, Lecture Notes in Computer Science, Vol. 506, Springer, Berlin, pp. 73–89.
    Open DOISearch in Google Scholar
  21. Freund, R. and Nachtigal, N. (1991). QMR: A quasi-minimal residual method for non-Hermitian linear systems,(1): 315–339.
    Open DOISearch in Google Scholar
  22. Freund, R.W. and Hochbruck, M. (1991). A biconjugate gradient type algorithm on massively parallel architectures,R. Vichnevetsky and J.J.H. Miller (Eds.),, Criterion Press, Dublin, pp. 720–721.
    Search in Google Scholar
  23. Freund, R.W. and Hochbruck, M. (1992). A biconjugate gradient-type algorithm for the iterative solution of non-Hermitian linear systems on massively parallel architectures,C. Brezinski and U. Kulisch (Eds.),, North Holland, Amsterdam, pp. 169–178.
    Search in Google Scholar
  24. Freund, R.W. and Nachtigal, N.M. (1994). An implementation of the QMR method based on coupled two-term recurrences,(2): 313.
    Open DOISearch in Google Scholar
  25. Ghysels, P., Ashby, T.J., Meerbergen, K. and Vanroose, W. (2013). Hiding global communication latency in the GMRES algorithm on massively parallel machines,(1): C48–C71.
    Open DOISearch in Google Scholar
  26. Ghysels, P. and Vanroose, W. (2014). Hiding global synchronization latency in the preconditioned conjugate gradient algorithm,(7): 224–238.
    Open DOISearch in Google Scholar
  27. Gustafsson, M., Demmel, J. and Holmgren, S. (2012a). Numerical evaluation of the communication-avoiding Lanczos algorithm,, Department of Information Technology, Uppsala University, Uppsala.
    Search in Google Scholar
  28. Gustafsson, M., Kormann, K. and Holmgren, S. (2012b). Communication-efficient algorithms for numerical quantum dynamics,K. Jónasson (Ed.),Lecture Notes in Computer Science, Vol. 7134, Springer, Berlin, pp. 368–378.
    Search in Google Scholar
  29. Gutknecht, M.H. (1997). Lanczos-type solvers for nonsymmetric linear systems of equations,(1): 271–397.
    Open DOISearch in Google Scholar
  30. Hernandez, V., Roman, J.E. and Vidal, V. (2005). SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems,(3): 351–362.
    Open DOISearch in Google Scholar
  31. Hoemmen, M.F. (2010)., Ph.D. thesis, EECS Department, University of California, Berkeley, CA.
    Search in Google Scholar
  32. Kandalla, K., Yang, U., Keasler, J., Kolev, T., Moody, A., Subramoni, H., Tomko, K., Vienne, J., De Supinski, B. and Panda, D. (2012). Designing non-blocking allreduce with collective offload on InfiniBand clusters: A case study with conjugate gradient solvers,, pp. 1156–1167.
    Search in Google Scholar
  33. Kim, S.K. (2010). Efficient biorthogonal Lanczos algorithm on message passing parallel computer,C.H. Hsu and V. Malyshkin (Eds.),, Lecture Notes in Computer Science, Vol. 6083, Springer, Berlin, pp. 293–299.
    Open DOISearch in Google Scholar
  34. Kim, S.K. and Chronopoulos, A. (1991). A class of Lanczos-like algorithms implemented on parallel computers,(6–7): 763–778.
    Open DOISearch in Google Scholar
  35. Kim, S.K. and Chronopoulos, A.T. (1992). An efficient nonsymmetric Lanczos method on parallel vector computers,(3): 357–374.
    Open DOISearch in Google Scholar
  36. Kim, S.K. and Kim, T.H. (2005). A study on the efficient parallel block Lanczos method,J. Zhang, J.-H. He and Y. Fu (Eds.),, Lecture Notes in Computer Science, Vol. 3314, Springer, Berlin/Heidelberg, pp. 231–237.
    Search in Google Scholar
  37. Lanczos, C. (1950). An iteration method for the solution of the eigenvalue problem of linear differential and integral operators,(4): 255–282.
    Open DOISearch in Google Scholar
  38. Meurant, G. (1986). The conjugate gradient method on supercomputers,: 9–17.
    Search in Google Scholar
  39. Mohiyuddin, M., Hoemmen, M., Demmel, J. and Yelick, K. (2009). Minimizing communication in sparse matrix solvers,, pp. 36:1–36:12.
    Search in Google Scholar
  40. Saad, Y. (1989). Krylov subspace methods on supercomputers,(6): 1200–1232.
    Open DOISearch in Google Scholar
  41. Sauren, M. and Bücker, H.M. (1998). On deriving the quasi-minimal residual method,(4): 922–926.
    Open DOISearch in Google Scholar
  42. Shalf, J., Dosanjh, S. and Morrison, J. (2011). Exascale computing technology challenges,D. Hutchison(Eds.),, Lecture Notes in Computer Science, Vol. 6449, Springer, Berlin, pp. 1–25.
    Open DOISearch in Google Scholar
  43. van der Vorst, H. (1990). Iterative methods for the solution of large systems of equations on supercomputers,(3): 137–146.
    Open DOISearch in Google Scholar
  44. van der Vorst, H.A. and Ye, Q. (2000). Residual replacement strategies for Krylov subspace iterative methods for the convergence of true residuals,(3): 835–852.
    Open DOISearch in Google Scholar
  45. Van Rosendale, J. (1983). Minimizing inner product data dependencies in conjugate gradient iteration,, NASA Langley Research Center, Hampton, VA.
    Search in Google Scholar
  46. Zhu, S.-X., Gu, T.-X. and Liu, X.-P. (2014). Minimizing synchronizations in sparse iterative solvers for distributed supercomputers,(1): 199–209.
    Open DOISearch in Google Scholar
  47. Zuo, X., Gu, T.-X. and Mo, Z. (2010). An improved GPBi-CG algorithm suitable for distributed parallel computing,(12): 4101–4109.
    Open DOISearch in Google Scholar
DOI: https://doi.org/10.1515/amcs-2015-0055 | Journal eISSN: 2083-8492 | Journal ISSN: 1641-876X
Journal RSS Feed
Language: English
Page range: 769 - 785
Submitted on: Apr 15, 2014
Published on: Dec 30, 2015
Published by: University of Zielona Góra
In partnership with: Paradigm Publishing Services
Publication frequency: 4 issues per year
Keywords:
synchronization-reducing,
s-step Lanczos,
s-step BiCG,
s-step QMR,
efficient recurrences
Related subjects:
Mathematics,
Applied mathematics

© 2015 Stefan Feuerriegel, H. Martin Bücker, published by University of Zielona Góra
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Volume 25 (2015): Issue 4 (December 2015)
Previous article
Next article