Question

Write a PRAM algorithm using \(n^{3}\) processors to multiply two \(n \times n\) matrices. Your algorithm should run in \(\theta(\lg n)\) time.

Short answer

A PRAM algorithm for multiplying two \(n\times n\) matrices has been derived that operates on \(n^{3}\) processors and runs in \(\theta(\lg n)\) time. This has been achieved by assigning a processor to each possible multiplication of one row element in the first matrix and one column element in the second matrix, summing these results and constructing the resultant matrix.

Step-by-step solution

Initialize Matrix Entries

All the \(n^{2}\) entries in both input matrices \(A\) and \(B\), and the resulting matrix \(C\) are initialized. In other words, each entry has a corresponding processor and the total numbers of processors are \(n^{3}\) for all possible pair of entries.

Processor Assignment

Each processor gets assigned to compute the element of the resultant matrix using a pair of elements, one from the first matrix's row and the second from the second matrix's column. Supposing \(P(i, j, k)\) is assigned to calculate \(C(i, j)\) using \(A(i, k)\) and \(B(k, j)\).

Multiplication and Addition

Each processor \(P(i, j, k)\) first performs the multiplication \(A(i, k).B(k, j)\) to get the computed result. Afterward, in \(\lg n\) steps, each processor sums up the result and gives the value to the processor responsible for the entry \(C(i, j)\) using a binary tree reduction technique.

Construct Resultant Matrix

The processors responsible for each entry of \(C\) will have computed the final value for each entry after adding up all \(A(i, k).B(k, j)\) for \(k\) from \(1\) to \(n\). Therefore, using the computed results, construct the resultant matrix \(C\).

Key concepts

Parallel Computing in Matrix Multiplication

Parallel computing is a form of computation that allows many calculations to be carried out simultaneously, leveraging the power of multiple processing elements. When multiplying matrices, the goal is to calculate the product matrix as efficiently as possible.

In the context of the PRAM (Parallel Random Access Machine) algorithm for matrix multiplication, each element in the resultant matrix is independent of the others. Therefore, we can assign a distinct processor to each entry of the matrix. As mentioned in the exercise, we use as many as \(n^3\) processors. This parallel approach takes advantage of the independent nature of matrix multiplications and allows for a dramatic reduction in the total computation time.

Complexity Analysis of Algorithms

Complexity analysis is vital in understanding how an algorithm performs and scales, particularly as the size of the input, in our case the matrix dimension, increases. There are two types of complexities we are usually interested in: time complexity and space complexity.

In our exercise, we focus on time complexity, which is expressed as \(\theta(\lg n)\). This notation indicates that as the size of the input (matrix size) increases, the time to complete the multiplication increases logarithmically. This is significantly faster than the classical approach to matrix multiplication, which has a time complexity of \(O(n^3)\) when implemented serially. The parallel algorithm is highly efficient, allowing us to achieve a substantial reduction in time complexity.

Improving Algorithmic Efficiency

Algorithmic efficiency refers to how effectively an algorithm uses computational resources to arrive at a result. The PRAM algorithm for matrix multiplication seeks to improve efficiency by dividing the task among many processors.

To maximize efficiency, our PRAM algorithm assigns one processor to compute each element of the product matrix. Each processor independently calculates a product and then contributes this to a sum, which forms the final answer for that element. The processors collaborate by using a binary tree reduction, which is a structured and efficient method for combining all these independent calculations into the final matrix.

Binary Tree Reduction Technique

The binary tree reduction technique is a strategy used in parallel computing to aggregate results from various processors. This technique organizes the addition of elements in a hierarchical binary tree structure, where each node is the sum of its children nodes.

In the context of matrix multiplication, once each processor has computed its respective product, the values are summed up in a binary tree fashion. This means that in each subsequent step, half of the processors exchange their results with the others and sum them up, reducing the number of active processors by half. After \(\lg n\) steps, this process yields the final value for each element of the product matrix with efficient use of computational resources and time.