A HIGH PERFORMANCE PC-BASED PARALLEL COMPUTING
 PLATFORM FOR ELECTRO-MAGNETIC SOURCE IMAGING

C. E. Acar, N. G. Gençer
Departmrnt Electrical and Electronics Engineering,
Middle East Technical University, 06531 Ankara, TURKEY

Abstract: Accurate solution of the forward problem of  Electro-Magnetic Source Imaging (EMSI) requires a realistic geometry and an efficient numerical model. In this study, a Finite Element Method (FEM) formulation that uses hexahedral, isoparametric quadratic or linear elements is used. The aim is to create a realistic FEM mesh that closely represents the geometrical and electrical properties of the head. Although the FEM matrix is sparse and symmetric, solution of such a realistic mesh exceeds the memory and computational capacity of modern workstations. To overcome this problem, a computing cluster of eight processors is constructed. And a parallel factorization algorithm is developed. Using this platform, factorization of a 200000 node FEM mesh takes about 15 hours. Once factorized, individual solutions can be obtained in 14 seconds.

INTRODUCTION

The forward problem of the Electro-Magnetic Source Imaging (EMSI) calculates the electrical and magnetic fields for a given source distribution using a computational model of the head. Numerical techniques such as the Finite Element Method (FEM) and the Boundary Element Method (BEM) are used for modeling the head. Since these numerical methods are computationally intensive, the resulting models are either coarse representations of the head or require supercomputers for solution. The aim of this study is to solve the EMSI forward problem with a detailed FEM head model using available workstations.

In this study, the FEM formulation by Özdemir and Gençer is used [1]. The head volume is discretized into hexahedral volume elements on which the potential function is defined by either linear or quadratic interpolation functions. Contributions from all of the elements are assembled to form a system of equations. Assuming a head volume of 4700 cm³, a regular grid of elements with 5 mm edge length requires 37600 elements. This corresponds to a linear mesh with 38000 nodes and a quadratic mesh with 152000 nodes. An edge length of 2 mm requires about 588000 elements with 560000 nodes for linear and 2240000 nodes quadratic elements. Simply storing a 2 million node quadratic FEM matrix in double precision would require more than 1 GB of memory. Although these numbers are calculated for a regular grid, they clearly illustrate the large memory and computational requirements of an accurate realistic FEM mesh.

Other FEM studies on EMSI either solve detailed models with supercomputers [2] or use coarse meshes with small number of elements and iterative solution algorithms [3].

This study solves the forward problem for large meshes using a network of workstations (NoW) as a high-performance computing platform. This architecture, first introduced by the Beowulf project uses available workstations and off-the-shelf hardware to create a high performance parallel processing platform. To solve the forward problem on this platform, a parallel factorization algorithm was implemented [4]. An eight-processor cluster is constructed consisting of four dual processor 933MHz PIII workstations connected using a high-speed network switch.

METHODS

There are two approaches to solving a sparse, symmetric positive-definite matrix equation. Iterative methods, such as the Conjugate Gradient method is fast for obtaining single solutions, and does not require additional memory storage. Direct methods, like Cholesky factorization, have an overhead during factorization. Once the matrix is factorized, individual solutions can be obtained relatively fast. For a large number of solutions, as required by typical inverse problem algorithms, direct methods turn out to be faster. However, factorization introduces fill-in terms to the matrix and greatly increases the memory requirements of the algorithm. The Asymmetric Cholesky factorization algorithm together with recursive partitioning of the matrix is used to distribute the problem over multiple processors while keeping the memory requirements minimum [4].

The parallel cluster consists of four workstations. Each workstation has 1GBytes of RAM and two 933 MHz PIII processors. A fifth workstation is used to connect the cluster to the rest of the world. The computing nodes have Linux operating system. The available computational tools include: GNU C, C++ and f77, Intel C++ and F90 compilers, LAPACK and BLAS libraries and Octave. PVM and MPI libraries are available for message passing during parallel computation.

Generating realistic meshes is another problem in creating realistic head models. Although isoparametric quadratic elements can interpolate both the potential function and element geometry, generating such a mesh for complex geometries such as the brain is very difficult. As an alternative, a simple grid-based mesh generation technique using linear elements is evaluated. Figure 1 illustrates different types of meshes used.

(a)	(b)	(c)

Figure 1. Sample meshes: (a) Spherical linear mesh. (b) grid-based linear spherical mesh. (c) grid-based realistic mesh.

The results obtained on the parallel cluster using these mesh types are given below.

RESULTS

The FEM formulation is validated against the concentric spheres model for which analytical solutions are available. The numerical and analytical solutions are compared using the relative difference measure (RDM). Three different mesh types are used for this comparison: Spherical linear and quadratic meshes and a linear grid-based mesh. The spherical model contains three shells representing scalp, skull and brain. For the solutions, scalp and brain conductivities are assumed to be 0.2 s/m and the skull conductivity is taken as 0.005 s/m. The comparison results can be seen in Figure 2.

Figure 2. FEM formulation results compared to analytical solutions for different mesh types, number of nodes, and dipole depths.

The performance of the parallel algorithm is evaluated. For this purpose, a speed-up figure is calculated which is the ratio of the single processor and multi processor computation times. The results are given in Figure 2.

Solution of a realistic mesh with 122209 elements and 132000 nodes on 8 processors consumed about 115 MB of memory/processor. The factorization took about 5 hours and solutions were obtained in 7 seconds. A quadratic mesh with 24800 elements and 102949 nodes consumed 164 MB/proc. Factorization time was 3 hours and solution time 5 seconds.

Figure 2. Factorization speed-up for grid-based meshes.

DISCUSSION

In this study, a FEM formulation was used that uses linear or quadratic isoparametric hexahedral elements to realistically model the head volume. The formulation was validated against the concentric spheres model. Three different mesh structures were used to obtain solutions. In order to be able to solve the resulting large matrix equations, a parallel matrix factorization algorithm was developed and a parallel processing platform was constructed. The parallel platform built from off-the-shelf hardware and free software and is a powerful computational platform.

Grid based meshes using linear elements were evaluated as an alternative to an optimized quadratic mesh. The RDM values for this mesh type were about 10% while linear meshes that fit the boundaries resulted in about 1% RDM. This large difference suggests that the grid-based mesh is not suitable for realistic head models in its present form. Several techniques, such as moving the nodes to the boundaries and varying the conductivity inside the elements are being investigated.

REFERENCES

[1] K. Özdemir, N. G. Gençer, “A New Finite Element Method Formulation for the Forward Problem Solution of Electro-Magnetic Source Localization,” in 19^th Annual Int. Conf. Proceedings of the IEEE EMBS, 1997, pp. 2104-2107.

[2]  P. Schimpf, J. Haueisen, C. Ramon, et al., “Realistic computer modelling of electric magnetic fields of human head and torso,” Parallel Computing, vol. 24, pp. 1433-1460, 1998.

[3]  P.M. Bonovas, G.A. Kyriacou, J.N. Sahalos. “A realistic three dimensional FEM of the human head,” Physiol. Meas., vol. 22, pp. 65-76, 2001.

[4] C.E. Acar, N.G. Gençer, “Parallel Solution of the Electro-Magnetic Source Imaging Forward Problem on a Network of Workstations,” in Proceedings of the International Conference on Biomagnetism, 1998.