论文标题
不可分割的椭圆方程
Preconditioned Legendre spectral Galerkin methods for the non-separable elliptic equation
论文作者
论文摘要
自相邻二阶椭圆方程的Legendre光谱Galerkin方法通常会导致线性系统具有致密且条件不良的系数矩阵。在本文中，线性系统通过预处理的共轭梯度（PCG）方法解决，其中预处理$ m $是通过在每个方向上以（$ t $+1） - 期限legendre系列近似可变系数来构建的，以达到所需的精度。提出的PCG方法的一个特征是，在达到一定的近似精度时，迭代步骤随所得矩阵的大小略有增加。该方法的效率在于，基于ILU（0）分解的一个步骤迭代方法，使用预处理器$ M $的系统大致求解。 $ m \ in \ mathbb {r}^{（n-1）^d \ times（n-1）^d} $的ILU（0）分解可以使用$ \ Mathcal {o}（t^{2d} n^d）$运算计算，并且在$ \ mathization因子中的数量} $ d = 1,2,3 $。为了进一步加快PCG方法，通过Legendre-Galerkin光谱离散化的结果矩阵开发了一种算法，用于快速矩阵矢量乘法，而无需明确形成它。快速矩阵矢量乘法的复杂性为$ \ Mathcal {o}（n^d（\ log n）^2）$。结果，PCG方法具有$ \ MATHCAL {O}（n^d（\ log n）^2）$对于$（n-1）^d $ UNKNOWS的$ D $ dimensional域的总复杂性，$ d = 1,2,3 $。给出了数值示例，以证明提出的预处理的效率和快速矩阵矢量乘法的算法。
The Legendre spectral Galerkin method of self-adjoint second order elliptic equations usually results in a linear system with a dense and ill-conditioned coefficient matrix. In this paper, the linear system is solved by a preconditioned conjugate gradient (PCG) method where the preconditioner $M$ is constructed by approximating the variable coefficients with a ($T$+1)-term Legendre series in each direction to a desired accuracy. A feature of the proposed PCG method is that the iteration step increases slightly with the size of the resulting matrix when reaching a certain approximation accuracy. The efficiency of the method lies in that the system with the preconditioner $M$ is approximately solved by a one-step iterative method based on the ILU(0) factorization. The ILU(0) factorization of $M\in \mathbb{R}^{(N-1)^d\times(N-1)^d}$ can be computed using $\mathcal{O}(T^{2d} N^d)$ operations, and the number of nonzeros in the factorization factors is of $\mathcal{O}(T^{d} N^d)$, $d=1,2,3$. To further speed up the PCG method, an algorithm is developed for fast matrix-vector multiplications by the resulting matrix of Legendre-Galerkin spectral discretization, without the need to explicitly form it. The complexity of the fast matrix-vector multiplications is of $\mathcal{O}(N^d (\log N)^2)$. As a result, the PCG method has a $\mathcal{O}(N^d (\log N)^2)$ total complexity for a $d$ dimensional domain with $(N-1)^d$ unknows, $d=1,2,3$. Numerical examples are given to demonstrate the efficiency of proposed preconditioners and the algorithm for fast matrix-vector multiplications.
