The Methods of Cyclic Reduction, Fourier Analysis and the FACR Algorithm for the Discrete Solution of Poisson’s Equation on a Rectangle

The methods of cyclic reduction and Fourier analysis are reviewed together with the FACR algorithm which combines the two methods. It is shown that the asymptotic operation count of the FACR algorithm for an n × n grid is O(n² log ₂ log ₂ n) which compares with O(n² log ₂ n) for either cyclic reduction or Fourier analysis used independently. In addition to the description of the methods, the treatment of the standard boundary conditions for the Fourier method is given and the efficient use of the fast Fourier transform is also discussed. Computational results are presented for grid sizes up to 1023 × 1023.