[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

The Explicit Spike Algorithm: Iterative Solution of the Reduced System

  • Chapter
High-Performance Scientific Computing

  • 1885 Accesses

Abstract

The explicit Spike algorithm applies to narrow banded linear systems which are strictly diagonally dominant by rows. The parallel bottleneck is the solution of the so-called reduced system which is block tridiagonal and strictly diagonally dominant by rows. The reduced system can be solved iteratively using the truncated reduced system matrix as a preconditioner. In this paper we derive a tight estimate for the quality of this preconditioner.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 71.50
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Chen, S., Kuck, D., Sameh, A.: Practical parallel band triangular system solvers. ACM Trans. Math. Softw. 4, 270–277 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  2. Dongarra, J.J., Sameh, A.: On some parallel banded system solvers. Parallel Comput. 1(3–4), 223–236 (1984)

    Article  Google Scholar 

  3. Lawrie, D.H., Sameh, A.H.: The computation and communication complexity of a parallel banded system slover. ACM Trans. Math. Softw. 10(2), 185–195 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  4. Manguoglu, M., Sameh, A.H., Schenk, O.: PSPIKE: A parallel hybrid sparse linear system solver. In: Proc. 15th Int’l. Euro-Par Conf. on Parallel Proc., Euro-Par ’09, pp. 797–808. Springer, Berlin (2009)

    Chapter  Google Scholar 

  5. Mikkelsen, C., Kågström, B.: Analysis of incomplete cyclic reduction for narrow banded and strictly diagonally dominant linear systems. Tech. Rep. UMINF 11.07, Department of Computing Science, Umeå University (2011). Submitted to PPAM-2011

    Google Scholar 

  6. Mikkelsen, C.C.K., Manguoglu, M.: Analysis of the truncated Spike algorithm. SIAM J. Matrix Anal. Appl. 30, 1500–1519 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  7. Polizzi, E., Sameh, A.H.: A parallel hybrid banded system solver: The SPIKE algorithm. Parallel Comput. 32(2), 177–194 (2006)

    Article  MathSciNet  Google Scholar 

  8. Polizzi, E., Sameh, A.H.: SPIKE: A parallel environment for solving banded linear systems. Comput. Fluids 36(1), 113–120 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  9. Sameh, A.H., Kuck, D.J.: On stable parallel linear system solvers. J. Assoc. Comput. Mach. 25(1), 81–91 (1978)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The work is supported by eSSENCE, a collaborative e-Science programme funded by the Swedish Research Council within the framework of the strategic research areas designated by the Swedish Government. In addition, support has been provided by the Swedish Foundation for Strategic Research under the frame program A3 02:128 and the EU Mål 2 project UMIT.

Author information

Authors and Affiliations

  1. Department of Computing Science and HPC2N, Umeå University, Umeå, Sweden

    Carl Christian Kjelgaard Mikkelsen

Authors
  1. Carl Christian Kjelgaard Mikkelsen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Carl Christian Kjelgaard Mikkelsen .

Editor information

Editors and Affiliations

  1. Dept. Electrical Eng. & Computer Science, University of Tennessee, Volunteer Boulevard 1122, Knoxville, 37996-3450, Tennessee, USA

    Michael W. Berry

  2. Department of Mathematics, Florida State University, Academic Way 1017, Tallahassee, 32306, Florida, USA

    Kyle A. Gallivan

  3. Dept. Computer Engineering & Informatics, University of Patras, Patras, 26500, Greece

    Efstratios Gallopoulos

  4. Department of Computer Science, Purdue University, 305 North University Street, West Lafayette, 47907-2107, Indiana, USA

    Ananth Grama

  5. IRISA, INRIA Rennes - Bretagne Atlantique, Campus de Beaulieu, Rennes, 35042, France

    Bernard Philippe

  6. Dept. of Computer Science & Engineering, University of Minnesota, Union Street SE 200, Minneapolis, 55455, Minnesota, USA

    Yousef Saad

  7. Department of Computer Science, Purdue University, N. University Street 305, West Lafayette, 47907-2107, Indiana, USA

    Faisal Saied

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag London Limited

About this chapter

Cite this chapter

Mikkelsen, C.C.K. (2012). The Explicit Spike Algorithm: Iterative Solution of the Reduced System. In: Berry, M., et al. High-Performance Scientific Computing. Springer, London. https://doi.org/10.1007/978-1-4471-2437-5_6

Download citation

  • DOI: https://doi.org/10.1007/978-1-4471-2437-5_6

  • Publisher Name: Springer, London

  • Print ISBN: 978-1-4471-2436-8

  • Online ISBN: 978-1-4471-2437-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation