Fast solution of elliptic partial differential equations using linear combinations of plane waves

Area of Science:

• Numerical Analysis
• Computational Mathematics
• Partial Differential Equations

Background:

• Solving arbitrary elliptic partial differential equations (PDEs) presents computational challenges.
• The standard Ritz method, while effective, leads to non-sparse matrices (A) in the linear system Ax=b.
• Non-sparse matrices hinder the direct application of efficient iterative solution methods.

Purpose of the Study:

• To propose a novel procedure for solving elliptic PDEs using the Ritz method.
• To overcome the computational bottleneck associated with non-sparse matrices generated by the Ritz method.
• To develop fast iterative methods for solving the resulting linear systems.

Main Methods:

• The solution is represented as a linear combination of plane waves, with coefficients determined by variational minimization.
• A recursive bisection approach leveraging the fast Fourier transform (FFT) is employed to circumvent the non-sparse matrix problem.
• Fast versions of stationary iterative methods (e.g., Gauss-Seidel), Krylov subspace methods, and multigrid methods are implemented.

Main Results:

• The FFT-based approach enables efficient iterative methods with O(NlogN) memory and O(Nlog^2N) iteration time, where N is the number of plane waves.
• Tests on Poisson's equation in adaptive coordinates demonstrate the feasibility of the proposed methods.
• The Generalized Minimum Residual (GMRES) method, combined with a multigrid preconditioner using Gauss-Seidel relaxation, yielded the best performance.

Conclusions:

• The proposed Ritz method combined with FFT-based techniques provides an efficient solution strategy for elliptic PDEs.
• This approach effectively addresses the non-sparse matrix challenge, enabling faster computations.
• The GMRES method with multigrid preconditioning is identified as a highly effective solver for this class of problems.