Search

We provide an overview of matrix decomposition algorithms (MDAs) for the solution of systems of linear equations arising when various discretization techniques are applied in the numerical solution of certain separable elliptic boundary value problems in the unit square. An MDA is a direct method which reduces the algebraic problem to one of solving a set of independent one-dimensional problems which are generally banded, block tridiagonal, or almost block diagonal. Often, fast Fourier transforms (FFTs) can be employed in an MDA with a resulting computational cost of O(N 2 logN) on an N?×?N uniform partition of the unit square. To formulate MDAs, we require knowledge of the eigenvalues and eigenvectors of matrices arising in corresponding two---point boundary value problems in one space dimension. In many important cases, these eigensystems are known explicitly, while in others, they must be computed. The first MDAs were formulated almost fifty years ago, for finite difference methods. Herein, we discuss more recent developments in the formulation and application of MDAs in spline collocation, finite element Galerkin and spectral methods, and the method of fundamental solutions. For ease of exposition, we focus primarily on the Dirichlet problem for Poisson's equation in the unit square, sketch extensions to other boundary conditions and to more involved elliptic problems, including the biharmonic Dirichlet problem, and report extensions to three dimensional problems in a cube. MDAs have also been used extensively as preconditioners in iterative methods for solving linear systems arising from discretizations of non-separable boundary value problems.

This paper is concerned with the spectral Chebyshev collocation solution of the Dirichlet problems for the Poisson and biharmonic equations in a square. The collocation schemes are solved at a cost of 2N3 + O(N2 logN) operations using an appropriate set of basis functions, a matrix diagonalization algorithm, and fast Fourier transforms. For the biharmonic problem, the resulting Schur complement system is solved by a preconditioned biconjugate gradient method. An application of the Poisson spectral preconditioner is discussed for the solution of a variable coefficient spectral problem. Numerical results confirm the efficiency of the proposed algorithms and the spectral and polynomial accuracy of the collocation schemes for smooth and singular solutions, respectively. © 2010 Society for Industrial and Applied Mathematics. 32 5 2995 3019 Cited By :1

A Legendre spectral Galerkin method is presented for the solution of the biharmonic Dirichlet problem on a square. The solution and its Laplacian are approximated using the set of basis functions suggested by Shen, which are linear combinations of two Legendre polynomials. A Schur complement approach is used to reduce the resulting linear system to one involving the approximation of the Laplacian of the solution on the two vertical sides of the square. The Schur complement system is solved by a preconditioned conjugate gradient method or the Cholesky method. The total cost of the algorithm is O(N3). Numerical results demonstrate the spectral convergence of the method. 22 5 1549 1569

We consider the Dirichlet boundary value problem for Poisson's equation in an L-shaped region or a rectangle with a cross-point. In both cases, we approximate the Dirichlet problem using Legendre spectral collocation, that is, polynomial collocation at the Legendre-Gauss nodes. The L-shaped region is partitioned into three nonoverlapping rectangular subregions with two interfaces and the rectangle with the cross-point is partitioned into four rectangular subregions with four interfaces. In each rectangular subregion, the approximate solution is a polynomial tensor product that satisfies Poisson's equation at the collocation points. The approximate solution is continuous on the entire domain and its normal derivatives are continuous at the collocation points on the interfaces, but continuity of the normal derivatives across the interfaces is not guaranteed. At the cross point, we require continuity of the normal derivative in the vertical direction. The solution of the collocation problem is first reduced to finding the approximate solution on the interfaces. The discrete Steklov-Poincaré operator corresponding to the interfaces is self-adjoint and positive definite with respect to the discrete inner product associated with the collocation points on the interfaces. The approximate solution on the interfaces is computed using the preconditioned conjugate gradient method. A preconditioner is obtained from the discrete Steklov-Poincaré operators corresponding to pairs of the adjacent rectangular subregions. Once the solution of the discrete Steklov- Poincaré equation is obtained, the collocation solution in each rectangular subregion is computed using a matrix decomposition method. The total cost of the algorithm is O(N 3), where the number of unknowns is proportional to N 2. © 2007 Springer Science+Business Media, LLC. 32 2 373 409 Cited By :5

We consider the solution of various boundary value problems for the Helmholtz equation in the unit square using a nodal cubic spline collocation method and modifications of it which produce optimal (fourth-) order approximations. For the solution of the collocation equations, we formulate matrix decomposition algorithms, fast direct methods which employ fast Fourier transforms and require O(N2 log N) operations on an N × N uniform partition of the unit square. A computational study confirms the published analysis for the Dirichlet problem and indicates that similar results hold for Neumann, mixed, and periodic boundary conditions. The numerical results also exhibit superconvergence phenomena not reported in earlier studies. 24 5 1733 1753 Cited By :9