I understand that GPU's has hundreds of cores that can handle thousands of threads all at once and that with the Jacobi iteration you're essentially using the same numbers over and over again to update a vector. Is this why implementing the Jacobi method on a GPU is a good idea especially if we have a really large system because we have so many redundant calculations?

I guess I don't really see why the Jacobi method is suitable for a GPU

  • A moderate amount of redundant computations is not necessarily a bad thing for GPUs. Proper memory access patterns is more of an issue, and that seems relatively easy to get right with Jacobi's method. But this is only a guess. – dsign Dec 3 '14 at 13:09
  • At a very abstract level, one looks at the dependency between the computed values of an algorithm (more correctly precedence diagrams) and identify how much of the computations can theoretically be performed either in parallel, or speculatively. The relevant slide. All slides. Some theoretical foundations never go out-of-date, be it GPU or whatnot. – rwong Aug 14 '15 at 10:12

The Jacobi Iterative algorithm calculates every row (hence, every component of the new guess) independently.

And exactly this is the magic trick that is being performed on a GPU. A GPU can make computations highly parallel.

In the Gauss-Seidel Algorithm (which usually converges a lot faster) for example, every row depends on the result of the calculation of the previous row. Thus making it very badly parallelizable and perform terribly on a GPU.


According to Margars, et. al.

The Jacobi iterative algorithms are very good candidates for parallelization …due to being very computationally intensive and inherently divisible into parallel tasks.

A problem that can benefit from parallel programming like that is inherently well suited to implementation on GPUs.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.