Parallel Power Iteration using MPI

Updated on 6th May 2025
See changes

Overview

This project implements a parallel dense matrix and vector format in C++ using MPI and the C++ Standard Template Library (STL). The implementation includes:

Custom C++ matrix and vector classes, utilizing dynamically allocated arrays for efficient data handling.
Link matrix generation using a Bernoulli distribution with a user-defined random seed.
Parallel power iteration to approximate the largest eigenvalue and left stochastic matrix ( P ) derived from the generated link matrix ( L ).

Features

C++ Matrix and Vector Classes:
- Custom implementations with dynamically allocated arrays.
- Efficient memory management and operator overloading.
Link Matrix Generation:
- Constructed using a Bernoulli distribution (0/1 values).
- Accepts a user-defined random seed for reproducibility.
- Transformed into a left stochastic matrix ( P ) by normalizing row sums.
Parallel Matrix-Vector Computation:
- Utilizes MPI for distributed Rayleigh method iterations.
- Supports scatter/gather for efficient communication.
Power Iteration Algorithm:
- Iteratively approximates the dominant eigenvalue.
- Implements convergence checks for numerical stability.

Dependencies

MPI Library (e.g., OpenMPI or MPICH)
CMake
C++ Standard Template Library (STL)

Installation

Install an MPI implementation and CMake:


sudo apt install mpich  # Debian/Ubuntu  
sudo dnf install openmpi  # Fedora 
sudo pacman -S cmake # Arch

Clone the repository:


git clone <repository_url>
cd <repository>

Compile the program using CMake:
- For just a sequential implementation (which does not depend on MPI):
```
cmake -S . -B build -DWITH_MPI=0 
```
- For a parallel implementation (which depends on MPI):
```
cmake -S . -B build -DWITH_MPI=1 
```
- For just a sequential implementation and to build tests:
```
cmake -S . -B build -DWITH_MPI=0 -DBUILD_TESTING=1
```

Usage

Run the program with the desired matrix size:


mpirun -np <num_processes> ./EVP <matrix_size>

where:

<num_processes> is the number of MPI processes.
<matrix_size> defines the dimension ( N \times N ) of the link matrix.

Example


mpirun -np 4 ./EVP 100

Implementation Details

Matrix and Vector Classes

Matrix Class (Matrix):
- Uses a dynamically allocated 2D array (or 1D row-major storage).
- Implements matrix operations (e.g., matrix-vector multiplication).
- Includes MPI distribution functions for parallel computation.
Vector Class (Vector):
- Uses a dynamically allocated array.
- Implements vector operations (e.g., dot product, normalization).
- Overloads operators for clean syntax.