Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Parallel Programming in C with MPI and OpenMPMichael J. QuinnCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Chapter 12Solving Linear SystemsCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.OutlinenTerminologynBack substitutionnGaussian eliminationnJacobi methodnConjugate gradient methodCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.TerminologynSystem of linear equationsuSolve Ax = b for xnSpecial matricesuSymmetrically bandeduUpper triangularuLower triangularuDiagonally dominantuSymmetricCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Symmetrically Banded42-10003-4560016324002-2092007387000402Semibandwidth 2Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Upper Triangular42-15920-4560-4003246000092000087000002Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Lower Triangular4000000000005430002623008-20180-357952Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Diagonally Dominant19022060-1520-305422-104232130-55-201160-35535-32Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Symmetric3022060743-35540-10423-190-50-30055654-55-3Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Back SubstitutionnUsed to solve upper triangular system Tx = b for xnMethodology: one element of x can be immediately computednUse this value to simplify system, revealing another element that can be immediately computednRepeatCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Back Substitution1x0+1x11x2+4x38= 2x13x2+1x35=2x2 3x30=2x34=Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Back Substitution1x0+1x11x2+4x38= 2x13x2+1x35=2x2 3x30=2x34=x3 = 2Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Back Substitution1x0+1x11x20= 2x13x23=2x26=2x34=Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Back Substitution1x0+1x11x20= 2x13x23=2x26=2x34=x2 = 3Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Back Substitution1x0+1x13= 2x112=2x26=2x34=Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Back Substitution1x0+1x13= 2x112=2x26=2x34=x1 = 6Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Back Substitution1x09= 2x112=2x26=2x34=Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Back Substitution1x09= 2x112=2x26=2x34=x0 = 9Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Pseudocodefor i n 1 down to 1 do x i b i / a i, i for j 0 to i 1 do b j b j x i a j, i endfor endfor Time complexity: (n2)Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Data Dependence DiagramWe cannot execute the outer loop in parallel. We can execute the inner loop in parallel.Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Row-oriented AlgorithmnAssociate primitive task with each row of A and corresponding elements of x and bnDuring iteration i task associated with row j computes new value of bjnTask i must compute xi and broadcast its valuenAgglomerate using rowwise interleaved striped decompositionCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Interleaved DecompositionsRowwise interleaved striped decompositionColumnwise interleaved striped decompositionCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Complexity AnalysisnEach process performs about n / (2p) iterations of loop j in allnA total of n -1 iterations in allnComputational complexity: (n2/p)nOne broadcast per iterationnCommunication complexity: (n log p)Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Column-oriented AlgorithmnAssociate one primitive task per column of A and associated element of xnLast task starts with vector bnDuring iteration i task i computes xi, updates b, and sends b to task i -1nIn other words, no computational concurrencynAgglomerate tasks in interleaved fashionCopyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Complexity AnalysisnSince b always updated by a single process, computational complexity same as sequential algorithm: (n2)nSince elements of b passed from one process to another each iteration, communi