Solving Linear Systems参考.ppt

Parallel Programmingin C with MPI and OpenMP Michael J. Quinn Chapter 12 Solving Linear Systems Outline Terminology Back substitution Gaussian elimination Jacobi method Conjugate gradient method Terminology System of linear equations Solve Ax = b for x Special matrices Symmetrically banded Upper triangular Lower triangular Diagonally dominant Symmetric Symmetrically Banded Upper Triangular Lower Triangular Diagonally Dominant Symmetric Back Substitution Used to solve upper triangular systemTx = b for x Methodology: one element of x can be immediately computed Use this value to simplify system, revealing another element that can be immediately computed Repeat Back Substitution Back Substitution Back Substitution Back Substitution Back Substitution Back Substitution Back Substitution Back Substitution Pseudocode Data Dependence Diagram Row-oriented Algorithm Associate primitive task with each row of A and corresponding elements of x and b During iteration i task associated with row j computes new value of bj Task i must compute xi and broadcast its value Agglomerate using rowwise interleaved striped decomposition Interleaved Decompositions Complexity Analysis Each process performs about n / (2p) iterations of loop j in all A total of n -1 iterations in all Computational complexity: ?(n2/p) One broadcast per iteration Communication complexity: ?(n log p) Column-oriented Algorithm Associate one primitive task per column of A and associated element of x Last task starts with vector b During iteration i task i computes xi, updates b, and sends b to task i -1 In other words, no computational concurrency Agglomerate tasks in interleaved fashion Complexity Analysis Since b always updated by a single process, computational complexity same as sequential algorithm: ?(n2) Since elements of b passed from one process to another each iteration, communication complexity is ?(n2) Comparison Gaussian Elimination Used to solve Ax = b when A is dense Reduces Ax = b to upper triangu