Parallel Implementation of Jacobi Method

Good morning to everyone,

I am trying to implement a parallel version of the Jacobi method for solving systems of linear equations in MATLAB through the tools offered by the Parallel Computing Toolbox, specifically distributed arrays and functions with built-in multithreading support.

In the attachments, you find the script I wrote, whose interface emulates the one of the MATLAB pcg function.

While testing it out on my PC (with an Intel Core i7 12 gen and 16 Gbs of RAM), pjm resulted extremely slow, featuring an execution time of several minutes for solving a system with a few thousands equations and unknwons.

The coefficient matrix and the right-hand side of the test system were

A = distributed(gallery('poisson',50));

b = sum(A,2);

with an expected solution equals to

xExact = ones(2500,1,'distributed');

I suspect there is some bottleneck in my code but I can't figure it out; the implemetation of the method seems me mathematically correct.

I guess the function is wasting time in checking if the method diverges at each iteration, but I do not want to limit the execution of the functions to systems that will always converge to the exact solution for the Jacobi method. Another expensive computation might be the computation of the residual error throughout the whole algorithm, but I want to provide the user with this type of information.

Again, the function has to behave the same way pcg does.

I'll appreciate some related feedback and I thank you in advance for any effort you'll put in figuring out this problem.

Answer 1

[Sameer]

Hi @THOMAS

From my observation, the main slowdown isn’t in the Jacobi math but in the distributed array overhead. On a single machine, every "A_dist*x_dist" and "norm(r_dist)" involves workers exchanging data, which is far more expensive than the computation itself for a 2500×2500 system.

Each iteration does:

• A distributed matrix–vector multiply, forcing data shuffling between workers.
• A distributed norm, requiring a global reduction across all workers.
• Both are repeated every iteration, so communication dominates runtime.
• Even extracting diag(A_dist) as a distributed array incurs coordination overhead.

When the problem fits in memory, MATLAB’s multithreaded BLAS is usually faster than local distributed arrays, which often end up slower due to this constant communication cost.

Hope this helps!

[THOMAS]

Thank you for your valuable feedback! I'll flag this answer as accepted!

[Edric Ellis]

In general, distributed arrays only provide benefit when your problem will not fit into the memory of a single machine.