Parallel implementation

Source file for the parallel implementation using MPI.

Author

Mukund Yedunuthala

Functions

Matrix genLinkMatrix(unsigned int &size, int &seed, double &linkProbability)

Generates a link matrix with random connections based on link probability.

This function initializes a square matrix of the given size, where each element is randomly assigned 0 or 1 based on the given link probability. The random values are generated using a Bernoulli distribution with a given seed.

Parameters:

  • size – Reference to the size of the matrix (number of rows and columns).

  • seed – Reference to the seed for the random number generator.

  • linkProbability – Reference to the probability of a link (1) occurring.

Returns:

A Matrix object representing the generated link matrix.

Matrix modifyLinkMatrix(unsigned int size, Matrix &linkMatrix)

Modifies the link matrix to create a transition probability matrix.

This function takes an existing link matrix and modifies it to ensure that it represents a valid stochastic matrix. It constructs the matrices Q, d, e, and edT to handle cases where nodes have no outgoing links.

Parameters:

  • size – The size of the matrix (number of rows and columns).

  • linkMatrix – Reference to the input link matrix.

Returns:

A Matrix object representing the modified transition probability matrix.

Vectors parallelPowerIterations(Matrix &P, int &rank, int &commSize, unsigned int &size, int max_it, double tol)

Computes the eigenvector using power iteration.

This function applies the power iteration method to approximate the dominant eigenvector of the given matrix P. The process iterates until the difference between successive approximations is below the given tolerance or the maximum number of iterations is reached.

Parameters:

  • P – Reference to the transition probability matrix.

  • rank – The rank of the process.

  • commSize – The number of processes present in the swarm.

  • size – The size of the matrix (number of rows and columns).

  • max_it – The maximum number of iterations.

  • tol – The convergence tolerance.

Returns:

A Vectors object representing the eigenvector.

double computeEigenValue(Matrix &P, Vectors &r)

Computes the eigenvalue of the matrix P using Rayleigh quotient.

Parameters:

  • P – Reference to the transition probability matrix.

  • r – Reference to the dominant eigenvector obtained from power iteration.

Returns:

The computed eigenvalue.

int main(int argc, char **argv)

The main function to compute the eigenvalue of a generated matrix.

The program takes the size of the matrix as a command-line argument, generates a link matrix with random connections, modifies it into a transition probability matrix, and then applies the power iteration method to compute the eigenvector. Finally, the eigenvalue is calculated and displayed along with the elapsed time.

Parameters:

  • argc – The number of command-line arguments.

  • argv – The command-line arguments (expects the matrix size as an argument).

Returns:

An integer indicating the exit status (0 for success).