On Fast Direct Poisson Solver, INF-SUP Constant and Iterative Stokes Solver by Legendre-Galerkin Method

摘要

In a sequence of recent works, we have presented efficient direct solvers, based on the Legendre- and Chebyshev-Galerkin methods, for the second- and fourth-order elliptic equations with constant coefficients. The complexity of these direct solvers is a small multiple of N~(d+1), where d = 2 or 3 and N is the cutoff number of the polynomial expansion in each direction. These direct solvers were all based on the matrix decomposition method and, hence, did not take full advantage of the special structures of the matrices obtained from the Legendre-Galerkin discretization. We shall see that in the two-dimensional case, more efficient algorithms can be constructed by further exploring the matrix structures. As the title suggests, the aim of this note is twofold: (ⅰ) we shall present a fast direct 2D Poisson solver, based on the Legendre-Galerkin approximation, whose complexity is of order O(N~2 log_2N) (where N is the cutoff number of the Legendre expansion in each direction); (ⅱ) we shall study numerically the asymptotic behavior of the inf-sup constants for a sequence of the discretized Stokes systems. Our results indicate in particular that the iterative Stokes solver, more precisely the conjugate gradient Uzawa algorithm, has a complexity of order O(N~5/2 log_2 N) for a sequence of discretized 2D Stokes systems. Since the convergence rate of the Legendre-Galerkin approximations is exponential for problems with smooth solutions, the algorithms presented below should be very competitive for the specified problems.