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

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.