#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#define N 4 // Size of the matrix (Assuming square matrix for simplicity)
// Function to print matrix (for debugging)
void printMatrix(double *matrix, int rows, int cols) {
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
printf("%.2f\t", matrix
[i
* cols
+ j
]); }
}
}
// Perform Gaussian elimination using MPI
void gaussianEliminationMPI(double *matrix, double *result, int rows_per_process, int my_rank, int num_procs) {
MPI_Status status;
for (int k = 0; k < N - 1; ++k) {
// Broadcast pivot row to all processes
if (my_rank == k / rows_per_process) {
for (int proc = 0; proc < num_procs; ++proc) {
MPI_Bcast(&matrix[k * N], N, MPI_DOUBLE, proc, MPI_COMM_WORLD);
}
}
// Elimination
for (int i = k + 1; i < N; ++i) {
if (i / rows_per_process == my_rank) {
double factor = matrix[i * N + k] / matrix[k * N + k];
for (int j = k; j < N; ++j) {
matrix[i * N + j] -= factor * matrix[k * N + j];
}
}
}
// Synchronize after each elimination step
MPI_Barrier(MPI_COMM_WORLD);
}
// Back substitution (not parallelized)
if (my_rank == 0) {
for (int i = N - 1; i >= 0; --i) {
result[i] = matrix[i * N + N] / matrix[i * N + i];
for (int j = i - 1; j >= 0; --j) {
matrix[j * N + N] -= matrix[j * N + i] * result[i];
}
}
}
}
int main(int argc, char *argv[]) {
MPI_Init(&argc, &argv);
int my_rank, num_procs;
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
MPI_Comm_size(MPI_COMM_WORLD, &num_procs);
int rows_per_process = N / num_procs;
double *matrix
= (double *)malloc(N
* (N
+ 1) * sizeof(double)); double *result
= (double *)malloc(N
* sizeof(double));
// Initialize matrix (for simplicity, assume a specific matrix here)
if (my_rank == 0) {
// Initialize the matrix [A | b] (assuming a specific matrix for demonstration)
matrix[0] = 2.0; matrix[1] = 1.0; matrix[2] = -1.0; matrix[3] = 8.0;
matrix[4] = -3.0; matrix[5] = -1.0; matrix[6] = 2.0; matrix[7] = -11.0;
matrix[8] = -2.0; matrix[9] = 1.0; matrix[10] = 2.0; matrix[11] = -3.0;
matrix[12] = 5.0; matrix[13] = 2.0; matrix[14] = -1.0; matrix[15] = 9.0;
printMatrix(matrix, N, N + 1);
}
// Scatter matrix to all processes
MPI_Scatter(matrix, rows_per_process * (N + 1), MPI_DOUBLE, matrix, rows_per_process * (N + 1), MPI_DOUBLE, 0, MPI_COMM_WORLD);
// Perform Gaussian elimination
gaussianEliminationMPI(matrix, result, rows_per_process, my_rank, num_procs);
// Gather results back to root process
MPI_Gather(result, rows_per_process, MPI_DOUBLE, result, rows_per_process, MPI_DOUBLE, 0, MPI_COMM_WORLD);
// Print the final result (only root process)
if (my_rank == 0) {
for (int i = 0; i < N; ++i) {
printf("x%d = %.2f\n", i
, result
[i
]); }
}
MPI_Finalize();
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPG1waS5oPgoKI2RlZmluZSBOIDQgLy8gU2l6ZSBvZiB0aGUgbWF0cml4IChBc3N1bWluZyBzcXVhcmUgbWF0cml4IGZvciBzaW1wbGljaXR5KQoKLy8gRnVuY3Rpb24gdG8gcHJpbnQgbWF0cml4IChmb3IgZGVidWdnaW5nKQp2b2lkIHByaW50TWF0cml4KGRvdWJsZSAqbWF0cml4LCBpbnQgcm93cywgaW50IGNvbHMpIHsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgcm93czsgKytpKSB7CiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBjb2xzOyArK2opIHsKICAgICAgICAgICAgcHJpbnRmKCIlLjJmXHQiLCBtYXRyaXhbaSAqIGNvbHMgKyBqXSk7CiAgICAgICAgfQogICAgICAgIHByaW50ZigiXG4iKTsKICAgIH0KICAgIHByaW50ZigiXG4iKTsKfQoKLy8gUGVyZm9ybSBHYXVzc2lhbiBlbGltaW5hdGlvbiB1c2luZyBNUEkKdm9pZCBnYXVzc2lhbkVsaW1pbmF0aW9uTVBJKGRvdWJsZSAqbWF0cml4LCBkb3VibGUgKnJlc3VsdCwgaW50IHJvd3NfcGVyX3Byb2Nlc3MsIGludCBteV9yYW5rLCBpbnQgbnVtX3Byb2NzKSB7CiAgICBNUElfU3RhdHVzIHN0YXR1czsKCiAgICBmb3IgKGludCBrID0gMDsgayA8IE4gLSAxOyArK2spIHsKICAgICAgICAvLyBCcm9hZGNhc3QgcGl2b3Qgcm93IHRvIGFsbCBwcm9jZXNzZXMKICAgICAgICBpZiAobXlfcmFuayA9PSBrIC8gcm93c19wZXJfcHJvY2VzcykgewogICAgICAgICAgICBmb3IgKGludCBwcm9jID0gMDsgcHJvYyA8IG51bV9wcm9jczsgKytwcm9jKSB7CiAgICAgICAgICAgICAgICBNUElfQmNhc3QoJm1hdHJpeFtrICogTl0sIE4sIE1QSV9ET1VCTEUsIHByb2MsIE1QSV9DT01NX1dPUkxEKTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgLy8gRWxpbWluYXRpb24KICAgICAgICBmb3IgKGludCBpID0gayArIDE7IGkgPCBOOyArK2kpIHsKICAgICAgICAgICAgaWYgKGkgLyByb3dzX3Blcl9wcm9jZXNzID09IG15X3JhbmspIHsKICAgICAgICAgICAgICAgIGRvdWJsZSBmYWN0b3IgPSBtYXRyaXhbaSAqIE4gKyBrXSAvIG1hdHJpeFtrICogTiArIGtdOwogICAgICAgICAgICAgICAgZm9yIChpbnQgaiA9IGs7IGogPCBOOyArK2opIHsKICAgICAgICAgICAgICAgICAgICBtYXRyaXhbaSAqIE4gKyBqXSAtPSBmYWN0b3IgKiBtYXRyaXhbayAqIE4gKyBqXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgLy8gU3luY2hyb25pemUgYWZ0ZXIgZWFjaCBlbGltaW5hdGlvbiBzdGVwCiAgICAgICAgTVBJX0JhcnJpZXIoTVBJX0NPTU1fV09STEQpOwogICAgfQoKICAgIC8vIEJhY2sgc3Vic3RpdHV0aW9uIChub3QgcGFyYWxsZWxpemVkKQogICAgaWYgKG15X3JhbmsgPT0gMCkgewogICAgICAgIGZvciAoaW50IGkgPSBOIC0gMTsgaSA+PSAwOyAtLWkpIHsKICAgICAgICAgICAgcmVzdWx0W2ldID0gbWF0cml4W2kgKiBOICsgTl0gLyBtYXRyaXhbaSAqIE4gKyBpXTsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IGkgLSAxOyBqID49IDA7IC0taikgewogICAgICAgICAgICAgICAgbWF0cml4W2ogKiBOICsgTl0gLT0gbWF0cml4W2ogKiBOICsgaV0gKiByZXN1bHRbaV07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0KCmludCBtYWluKGludCBhcmdjLCBjaGFyICphcmd2W10pIHsKICAgIE1QSV9Jbml0KCZhcmdjLCAmYXJndik7CgogICAgaW50IG15X3JhbmssIG51bV9wcm9jczsKICAgIE1QSV9Db21tX3JhbmsoTVBJX0NPTU1fV09STEQsICZteV9yYW5rKTsKICAgIE1QSV9Db21tX3NpemUoTVBJX0NPTU1fV09STEQsICZudW1fcHJvY3MpOwoKICAgIGludCByb3dzX3Blcl9wcm9jZXNzID0gTiAvIG51bV9wcm9jczsKICAgIGRvdWJsZSAqbWF0cml4ID0gKGRvdWJsZSAqKW1hbGxvYyhOICogKE4gKyAxKSAqIHNpemVvZihkb3VibGUpKTsKICAgIGRvdWJsZSAqcmVzdWx0ID0gKGRvdWJsZSAqKW1hbGxvYyhOICogc2l6ZW9mKGRvdWJsZSkpOwoKICAgIC8vIEluaXRpYWxpemUgbWF0cml4IChmb3Igc2ltcGxpY2l0eSwgYXNzdW1lIGEgc3BlY2lmaWMgbWF0cml4IGhlcmUpCiAgICBpZiAobXlfcmFuayA9PSAwKSB7CiAgICAgICAgLy8gSW5pdGlhbGl6ZSB0aGUgbWF0cml4IFtBIHwgYl0gKGFzc3VtaW5nIGEgc3BlY2lmaWMgbWF0cml4IGZvciBkZW1vbnN0cmF0aW9uKQogICAgICAgIG1hdHJpeFswXSA9IDIuMDsgbWF0cml4WzFdID0gMS4wOyBtYXRyaXhbMl0gPSAtMS4wOyBtYXRyaXhbM10gPSA4LjA7CiAgICAgICAgbWF0cml4WzRdID0gLTMuMDsgbWF0cml4WzVdID0gLTEuMDsgbWF0cml4WzZdID0gMi4wOyBtYXRyaXhbN10gPSAtMTEuMDsKICAgICAgICBtYXRyaXhbOF0gPSAtMi4wOyBtYXRyaXhbOV0gPSAxLjA7IG1hdHJpeFsxMF0gPSAyLjA7IG1hdHJpeFsxMV0gPSAtMy4wOwogICAgICAgIG1hdHJpeFsxMl0gPSA1LjA7IG1hdHJpeFsxM10gPSAyLjA7IG1hdHJpeFsxNF0gPSAtMS4wOyBtYXRyaXhbMTVdID0gOS4wOwoKICAgICAgICBwcmludGYoIk9yaWdpbmFsIE1hdHJpeDpcbiIpOwogICAgICAgIHByaW50TWF0cml4KG1hdHJpeCwgTiwgTiArIDEpOwogICAgfQoKICAgIC8vIFNjYXR0ZXIgbWF0cml4IHRvIGFsbCBwcm9jZXNzZXMKICAgIE1QSV9TY2F0dGVyKG1hdHJpeCwgcm93c19wZXJfcHJvY2VzcyAqIChOICsgMSksIE1QSV9ET1VCTEUsIG1hdHJpeCwgcm93c19wZXJfcHJvY2VzcyAqIChOICsgMSksIE1QSV9ET1VCTEUsIDAsIE1QSV9DT01NX1dPUkxEKTsKCiAgICAvLyBQZXJmb3JtIEdhdXNzaWFuIGVsaW1pbmF0aW9uCiAgICBnYXVzc2lhbkVsaW1pbmF0aW9uTVBJKG1hdHJpeCwgcmVzdWx0LCByb3dzX3Blcl9wcm9jZXNzLCBteV9yYW5rLCBudW1fcHJvY3MpOwoKICAgIC8vIEdhdGhlciByZXN1bHRzIGJhY2sgdG8gcm9vdCBwcm9jZXNzCiAgICBNUElfR2F0aGVyKHJlc3VsdCwgcm93c19wZXJfcHJvY2VzcywgTVBJX0RPVUJMRSwgcmVzdWx0LCByb3dzX3Blcl9wcm9jZXNzLCBNUElfRE9VQkxFLCAwLCBNUElfQ09NTV9XT1JMRCk7CgogICAgLy8gUHJpbnQgdGhlIGZpbmFsIHJlc3VsdCAob25seSByb290IHByb2Nlc3MpCiAgICBpZiAobXlfcmFuayA9PSAwKSB7CiAgICAgICAgcHJpbnRmKCJSZXN1bHQ6XG4iKTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IE47ICsraSkgewogICAgICAgICAgICBwcmludGYoInglZCA9ICUuMmZcbiIsIGksIHJlc3VsdFtpXSk7CiAgICAgICAgfQogICAgfQoKICAgIGZyZWUobWF0cml4KTsKICAgIGZyZWUocmVzdWx0KTsKCiAgICBNUElfRmluYWxpemUoKTsKICAgIHJldHVybiAwOwp9Cg==