Title: Efficient Spectral-Galerkin Method I. Direct Solvers of Second
        and Fourth Order Equations by Using Legendre Polynomials

Author: Jie Shen

Status: SIAM J. Sci. Comput. 15, 1489-1505, 1994

Abstract:

We present  some efficient algorithms based on the Legendre-Galerkin
approximations for the direct solution
of the second and fourth order elliptic  equations. The key to the
efficiency of our algorithms is to
construct appropriate base functions, which lead to systems
with sparse matrices  for the discrete variational formulations.
The complexities of the algorithms are a small multiple of $N^{d+1}$ operations
for a $d$ dimensional domain with $(N-1)^d$ unknowns, while the
convergence rates of the 
algorithms are exponential for problems with smooth solutions. In
addition, the algorithms can be effectively parallelized since the
bottlenecks of the algorithms are matrix-matrix multiplications.