Timely Communication: Efficient Algorithms for Solving a Fourth-Order Equation with the Spectral-Galerkin Method

We show that one can derive an O(N³) spectral-Galerkin method for fourth-order (biharmonic type) elliptic equations based on the use of Chebyshev polynomials. The use of Chebyshev polynomials provides a fast transform between physical and spectral space which is advantageous when a sequence of problems must be solved, e.g., as part of a nonlinear iteration. This improves the result of Shen [SIAM J. Sci. Comput., 16 (1995), pp. 74--87] which reported an O(N⁴) algorithm inferior to the O(N³) method developed earlier [Shen, SIAM J. Sci. Comput., 15 (1994), pp. 1440--1451] based on Legendre polynomials but less practical in the case of multiple problems. We further compare our method with an improved implementation of the Legendre--Galerkin method based on the same approach.