Finite difference iterative solvers for electroencephalography: serial and parallel performance analysis | Medical & Biological Engineering & Computing Skip to main content
Springer Nature Link
Log in

Finite difference iterative solvers for electroencephalography: serial and parallel performance analysis

  • Original Article
  • Published:
Medical & Biological Engineering & Computing Aims and scope Submit manuscript

Abstract

Currently the resolution of the head models used in electroencephalography (EEG) studies is limited by the speed of the forward solver. Here, we present a parallel finite difference technique that can reduce the solution time of the governing Poisson equation for a head model. Multiple processors are used to work on the problem simultaneously in order to speed up the solution and provide the memory for solving large problems. The original computational domain is divided into multiple rectangular partitions. Each partition is then assigned to a processor, which is responsible for all the computations and inter-processor communication associated with the nodes in that particular partition. Since the forward solution time is mainly spent on solving the associated matrix equation, it is desirable to find the optimum matrix solver. A detailed comparison of various iterative solvers was performed for both isotropic and anisotropic realistic head models constructed from MRI images. The conjugate gradient (CG) method preconditioned with an advanced geometric multigrid technique was found to provide the best overall performance. For an anisotropic model with 256 × 128 × 256 cells, this technique provides a speedup of 508 on 32 processors over the serial CG solution, with a speedup of 20.1 and 25.3 through multigrid preconditioning and parallelization, respectively.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Ashby SF, Falgout RD (1996) A parallel multigrid preconditioned conjugate gradient algorithm for groundwater flow simulations. Nucl Sci Eng 124:145–159

    Google Scholar 

  2. Axelsson O (1995) Iterative solution methods. Cambridge University Press, New York

    Google Scholar 

  3. Carstensen C, Kuhn M, Langer U (1998) Fast parallel solvers for symmetric boundary element domain decomposition equations. Numer Math 79:321–347

    Article  MATH  MathSciNet  Google Scholar 

  4. De Sterck H, Yang UM, Heys JJ (2006) Reducing complexity in parallel algebraic multigrid preconditioners. SIAM J Matrix Anal Appl 27:1019–1039

    Article  MATH  MathSciNet  Google Scholar 

  5. Fan Y, Jiang T, Evans DJ (2001) Parallel algorithm for BEM based EEG/MEG. Neuroimage 13:S1301

    Article  Google Scholar 

  6. Fuchs M, Wagner M, Kastner J (2001) Boundary element method volume conductor models for EEG source reconstruction. Clin Neurophysiol 112:1400–1407

    Article  Google Scholar 

  7. Grama A, Karypis G, Kumar V, Gupta A (2003) Introduction to parallel computing. Addison–Wesley, Reading

    Google Scholar 

  8. Gropp W, Lusk E, Skjellum A (1994) Using MPI: portable parallel programming with the message-passing interface. MIT Press, Boston

    Google Scholar 

  9. Gullmar D, Haueisen J, Eiselt M, Giessler F, Flemming L, Anwander A, Knosche TR, Wolters CH, Dumpelmann M, Tuch DS, Reichenbach JR (2006) Influence of anisotropic conductivity on EEG source reconstruction: investigations in a rabbit model. IEEE Trans Biomed Eng 53:1841–1850

    Article  Google Scholar 

  10. Hackbusch W (1994) Iterative solution of large sparse systems of equations. In: Applied mathematical sciences. Springer, New York, Vol. 95

  11. Hallez H, Vanrumste B, Van Hese P, D’asseler Y, Lemahieu I, Van De Walle R (2005) A finite difference method with reciprocity used to incorporate anisotropy in electroencephalogram dipole source localization. Phys Med Biol 50:3787–3806

    Article  Google Scholar 

  12. Hysom D, Pothen A (2001) A scalable parallel algorithm for incomplete factor preconditioning. SIAM J Sci Comput 22:2194–2215

    Article  MathSciNet  Google Scholar 

  13. Jing L, Zhu S, He B (2005) A finite difference method for solving the three-dimensional EEG forward problem. Proceedings of 27th Annual Int. Conf. IEEE EMBS, pp. 1540–1543

  14. Laarne PH, Tenhunen-Eskelinen ML, Hyttinen JK, Eskola HJ (2000) Effect of EEG electrode density on dipole localization accuracy using two realistically shaped skull resistivity models. Brain Topogr 12:249–254

    Article  Google Scholar 

  15. Lemieux L, McBride A, Hand JW (1996) Calculation of electrical potentials on the surface of a realistic head model by finite differences. Phys Med Biol 41:1079–1091

    Article  Google Scholar 

  16. Malmivuo J, Plonsey R (1995) Bioelectromagnetism: principles and applications of bioelectric and biomagnetic fields. Oxford University Press, New York

    Google Scholar 

  17. Mohr M, Vanrumste B (2003) Comparing iterative solvers for linear systems associated with the finite difference discretization of the forward problem in electro-encephalographic source analysis. Med Biol Eng Comput 41:75–84

    Article  Google Scholar 

  18. Neilson LA, Kovalyov M, Koles ZJ (2005) A computationally efficient method for accurately solving the EEG forward problem in a finely discretized head model. Clin Neurophysiol 116:2302–2314

    Article  Google Scholar 

  19. Saleheen HI, Ng KT (1997) New finite difference formulations for general inhomogeneous anisotropic bioelectric problems. IEEE Trans Biomed Eng 44:800–809

    Article  Google Scholar 

  20. Schimpf P, Haueisen J, Ramon C, Nowak H (1998) Realistic computer modeling of electric and magnetic fields of human head and torso. Parallel Comput 24:1433–1460

    Article  Google Scholar 

  21. Vanrumste B, Van Hoey G, Van De Walle R, D’have M, Lemahieu I, Boon P (2000) Dipole location errors in electroencephalogram source analysis due to volume conductor model errors. Med Biol Eng Comput 38:528–534

    Article  Google Scholar 

  22. Vanrumste B, Van Hoey G, Van De Walle R, D’have M, Lemahieu I, Boon P (2001) The validation of the finite difference method and reciprocity for solving the inverse problem in EEG dipole source analysis. Brain Topogr 14:83–92

    Article  Google Scholar 

  23. Wolters CH, Kuhn M, Anwander A, Reitzinger S (2002) A parallel algebraic multigrid solver for finite element method based source localization in the human brain. Comput Vis Sci 5:165–177

    Article  MATH  MathSciNet  Google Scholar 

  24. Yang UM (2006) Parallel algebraic multigrid methods—high performance preconditioners. In: Bruaset AM, Tveito A (eds) Numerical solution of partial differential equations on parallel computers. Springer-Verlag, Berlin, pp. 209–236

    Chapter  Google Scholar 

Download references

Acknowledgments

This work was supported in part by the Los Alamos National Laboratory (LANL). The authors would like to especially thank Dr. Doug Ranken at the Biological and Quantum Physics Group, LANL for providing the segmented MRI image used to construct the head models.

Author information

Authors and Affiliations

  1. Klipsch School of Electrical and Computer Engineering, New Mexico State University, MSC 3-O, Las Cruces, NM, 88003, USA

    Derek N. Barnes & Kwong T. Ng

  2. Biological and Quantum Physics Group, Los Alamos National Laboratory, MS D454, Los Alamos, NM, 87545, USA

    John S. George

Authors
  1. Derek N. Barnes
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. John S. George
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kwong T. Ng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kwong T. Ng.

Appendix 1 Total solution time versus number of processors for tangential white matter fiber model

Appendix 1 Total solution time versus number of processors for tangential white matter fiber model

The total solution time versus the number of processors is given in Fig. 6 for the model with 256 × 128 × 256 cells and tangential fiber orientation in the white matter.

Fig. 6
figure 6

Total solution time for the anisotropic model with 256 × 128 × 256 cells and tangential white matter fiber. The methods shown are the CG (open circle), AMG (hyphenated line), GMG (asterisk), GMG-CG (open square), ILUBJ(0)-CG (open diamond), ILU(0)-CG (open triangle), and the JAC-CG (dots and dashes). The threshold (α) for AMG and the number of levels (l) for ILU are 0.3 and 0, respectively

Full size image

Rights and permissions

Reprints and permissions

About this article

Cite this article

Barnes, D.N., George, J.S. & Ng, K.T. Finite difference iterative solvers for electroencephalography: serial and parallel performance analysis. Med Biol Eng Comput 46, 901–910 (2008). https://doi.org/10.1007/s11517-008-0344-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11517-008-0344-9

Keywords

Search

Navigation