An efficient parallel algorithm for Caputo fractional reaction-diffusion equation with implicit finite-difference method

Qinglin Wang, Jie Liu, Chunye Gong, Xiantuo Tang, Guitao Fu, Zuocheng XingAdvances 2016 · DOI

Abstract

Solving Caputo fractional reaction-diffusion equations is computationally demanding due to the non-local nature of fractional derivatives. This paper presents an efficient parallel algorithm utilizing an implicit finite-difference method. The approach features a novel parallel solver for linear tridiagonal equations based on a reduced system elimination method. Experimental results demonstrate high accuracy and significant performance gains, achieving a 14.55x speedup with 16 parallel processes on Intel Xeon E5-2670 CPUs.

Introduction

Fractional Differential Equations (FDEs) are essential for modeling systems with "memory" or non-local behavior, such as anomalous diffusion in complex physical or financial environments. However, numerical simulation of FDEs is challenging because fractional derivatives depend on the function's entire history. While implicit finite-difference methods offer stability, they necessitate solving large linear systems at every time step, which is computationally prohibitive for serial processors. The challenge lies in parallelizing these solvers—specifically the tridiagonal matrix systems—without losing accuracy or incurring excessive communication overhead.

Methodology

The proposed parallel framework employs a divide-and-conquer strategy using the Message Passing Interface (MPI). The core of the algorithm is a specialized tridiagonal solver designed to handle the diagonally dominant matrices resulting from the discretization of the Caputo fractional equation.

Parallel Tridiagonal Solver

The main matrix is partitioned into $p$ blocks corresponding to the number of processors. A new elimination technique transforms these blocks into a "reduced system," allowing processors to compute local solutions independently. Communication is restricted to small amounts of boundary data exchanged with a master process to finalize the global solution.

Figure 1: Communication workflow between four parallel processes (P1-P4) during the tridiagonal system solution.

Optimization Strategies

Efficiency is further enhanced by recognizing that the tridiagonal matrix $A$ remains constant across time iterations. By recording the initial matrix transformation, subsequent steps only require processing the changing right-hand side vector, significantly reducing redundant computations.

Results and Discussion

The algorithm was evaluated using a benchmark analytic problem ($u(x,t) = x(2-x)t^2$) and synthetic scaling tests with grid sizes ranging from $65 \times 65$ to $2,049 \times 2,049$.

Performance and Scalability

On a dual eight-core Intel Xeon E5-2670 setup, the implementation achieved a 14.55x speedup with 16 processes, representing a scaling efficiency of 91%. Notably, super-linear speedups were observed at low processor counts (2 and 4 processes), attributed to improved data locality and better CPU cache utilization as problem chunks became smaller.

Accuracy

The parallelization method maintains high precision, with a negligible difference ($4.22 \times 10^{-15}$) compared to the serial version. The maximum absolute error against the analytic solution was approximately $7.47 \times 10^{-4}$ for a $65 \times 65$ grid, decreasing consistently as resolution increased.

Conclusion

This research provides a robust parallel solution for Caputo fractional reaction-diffusion equations. By minimizing communication overhead and optimizing matrix operations, the algorithm enables large-scale simulations that were previously impractical. Future work will explore GPGPU acceleration and extending the elimination method to non-linear fractional equations.

Summary updated

Abstract

An efficient parallel algorithm for Caputo fractional reaction-diffusion equation with implicit finite-difference method is proposed in this paper. The parallel algorithm consists of a parallel solver for linear tridiagonal equations and parallel vector arithmetic operations. For the parallel solver, in order to solve the linear tridiagonal equations efficiently, a new tridiagonal reduced system is developed with an elimination method. The experimental results show that the parallel algorithm is in good agreement with the analytic solution. The parallel implementation with 16 parallel processes on two eight-core Intel Xeon E5-2670 CPUs is 14.55 times faster than the serial one on single Xeon E5-2670 core.
BibTeX
@inproceedings{wang2016efficient,
  author = {Qinglin Wang and Jie Liu and Chunye Gong and Xiantuo Tang and Guitao Fu and Zuocheng Xing},
  title = {{An efficient parallel algorithm for Caputo fractional reaction-diffusion equation with implicit finite-difference method}},
  booktitle = {Advances},
  year = {2016},
  doi = {10.1186/s13662-016-0929-9},
}
Figure