Bandwidth truncation for Chebyshev polynomial and ultraspherical/Chebyshev Galerkin discretizations of differential equations: Restrictions and two improvements

详细信息    查看全文

• 作者：Zhu Huang^a ; John P. Boyd^b ; ^{jpboyd@umich.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Pseudospectral ; Chebyshev polynomials ; Spectral method ; Ultraspherical polynomials ; Galerkin matrix
• 刊名：Journal of Computational and Applied Mathematics
• 出版年：2016
• 出版时间：15 August 2016
• 年：2016
• 卷：302
• 期：Complete
• 页码：340-355
• 全文大小：954 K

文摘

The Petrov–Galerkin ultraspherical polynomial/Chebyshev polynomial discretization of the highest derivative of a differential equation is a diagonal   matrix. The same is true for Fourier–Galerkin discretizations. Nevertheless, the spectral discretizations of simple problems like d20473c4f5801b5e6d1" title="Click to view the MathML source">u_xx+q(x)u=f(x)$u_{xx}+q\left(x\right)u=f\left(x\right)$ are usually dense matrices. The villain is the “multiplication matrix”, the Galerkin representation of a term like q(x)u(x)$q\left(x\right)u\left(x\right)$; unfortunately, this part of the Galerkin matrix is dense. However, if the ODE coefficient q(x)$q\left(x\right)$ has a Chebyshev or Fourier series that converges much more rapidly than 16da20dc3a5cf58ae02a3727bcf8f" title="Click to view the MathML source">u(x)$u\left(x\right)$, then it is possible to realize great cost savings at no loss of accuracy by truncating the full N×N$N\times N$ Galerkin matrix to a banded matrix where the bandwidth m≪N$m\ll N$. One of our themes is that when the spectral series for q(x)$q\left(x\right)$ and 16da20dc3a5cf58ae02a3727bcf8f" title="Click to view the MathML source">u(x)$u\left(x\right)$ have similar rates of convergence, as is almost universal when a nonlinear equation is linearized for a Newton–Krylov iteration, such “[accuracy] lossless” truncation is impossible. Nonlinearity is but one of many causes of this sort of solution/coefficient “equiconvergence”. When bandwidth truncation is possible, though, our second theme is to show that a modest amount of floating point operations and memory can be saved by an unsymmetric truncation in which the number of elements retained to the left of the main diagonal is roughly double the number kept to the right. Our second improvement is to replace the M$M$-term spectral series for q(x)$q\left(x\right)$ by its [(M/2)/(M/2)]$[(M/2)/(M/2)]$ Chebyshev–Padé rational approximation. This sometimes allow one to halve the matrix bandwidth, reducing the linear algebra costs by a factor of four.