Parallel Programming: for Multicore and Cluster Systems- P40: Innovations in hardware architecture, like hyper-threading or multicore processors, mean that parallel computing resources are available for inexpensive desktop computers. In only a few years, many standard software products will be based on concepts of parallel programming implemented on such hardware, and the range of applications will be much broader than that of scientific computing, up to now the main application area for parallel computing | Direct Methods for Linear Systems with Banded Structure 383 where I denotes the N x N unit matrix which has the value 1 in the diagonal elements and the value 0 in all other entries. The matrix B has the structure 4 -1 B -1 4 -1 0 -1 Figure illustrates the two-dimensional mesh with five-point stencil above and the sparsity structure of the corresponding coefficient matrix A of Formula . In summary Formulas and represent a linear equation system with a sparse coefficient matrix which has non-zero elements in the main diagonal and its direct neighbors as well as in the diagonals in distance N . Thus the linear equation system resulting from the Poisson equation has a banded structure which should be exploited when solving the system. In the following we present solution methods for linear equation systems with banded structure and start the description with tridiagonal systems. These systems have only three non-zero diagonals in the main diagonal and its two neighbors. A tridiagonal system results for example when discretizing the one-dimensional Poisson equation. Tridiagonal Systems For the solution of a linear equation system Ax y with a banded or tridiagonal coefficient matrix A e Rnxn specific solution methods can exploit the sparse matrix structure. A matrix A aj kj 1 . n e Rnxn is called banded when its structure takes the form of a band of non-zero elements around the principal diagonal. More precisely this means a matrix A is a banded matrix if there exists r e N r n with aij 0 for i - j r . The number r is called the semi-bandwidth of A. For r 1a banded matrix is called tridiagonal matrix. We first consider the solution of tridiagonal systems which are linear equation systems with tridiagonal coefficient matrix. Gaussian Elimination for Tridiagonal Systems For the solution of a linear equation system Ax y with tridiagonal matrix A the Gaussian elimination can be used. Step k of the forward elimination without .
