分布式计算代写｜CS546 “Parallel and Distributed Processing” Programming Assignment 3

本次美国代写是一个并行和分布式处理的assignment

Exercise:

1. Use MPI to implement the Parallel Partition LU(PPT)algorithm.
Details:

A partition Method for parallel Processing:

The Parallel Partition LU(PPT) Algorithm

Based on the matrix partitioning technique described previously, using p processors, the PPT algorithm
to solve (1) consists of the following steps:

Step 1. Allocate 𝐴!, 𝑑(!) and elements 𝑎!$, 𝑐(!%&)$’& to the ith node, where 0 ≤ 𝑖 ≤ 𝑝 − 1.

Step 2. Use the LU decomposition method to solve 𝐴!,𝑥.(!), 𝑣(!), 𝑤(!)1 = [𝑑(!), 𝑎!$𝑒(, 𝑐(!%&)$’&𝑒$’&]

Step 3. Send 𝑥.((!), 𝑥.$(!)’&, 𝑣((!), 𝑣$(!’) &, 𝑤((!), 𝑤$(!’) & (0 ≤ 𝑖 ≤ 𝑝 − 1) from the ith node to the other nodes to
form matrix Z and vector h on each node.

Step 4. Use the LU decomposition method to solve 𝑍𝑦 = ℎ on all nodes simultaneously.

Step 5. Compute (10) and (11) in parallel on p processors.
∆𝑥(!) = ,𝑣(!), 𝑤(!)1[𝑦𝑦)2!’𝑖&]
𝑥(!) = 𝑥.(!) − ∆𝑥(!)

Hints:

The size of vector h in Equation (7) is a 2(p-1)
The matrix Z in Equation (8) is a 2(p-1) dimension matrix.
When creating vector h and matrix Z by using equation (7) and (8), you need to make Z to be a
2(p-1) tridiagonal matrix through matrix column transformation. Therefore, you need to
introduce a permutation matrix P here and use 𝒁 = 𝑷 + 𝑬𝑻𝒀 to create Z.
Please check the provided implementations of the sequential tridiagonal matrix algorithm:
https://en.wikibooks.org/wiki/Algorithm_Implementation/Linear_Algebra/Tridiagonal_matrix_
algorithm

程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB