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

• ALL

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:

1. The size of vector h in Equation (7) is a 2(p-1)
2. The matrix Z in Equation (8) is a 2(p-1) dimension matrix.
3. 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.
4. Please check the provided implementations of the sequential tridiagonal matrix algorithm:
https://en.wikibooks.org/wiki/Algorithm_Implementation/Linear_Algebra/Tridiagonal_matrix_
algorithm E-mail: vipdue@outlook.com  微信号:vipnxx 