空间分数阶扩散方程快速算法研究

Space fractional diffusion equations （SFDEs），capable of modeling super diffusion processes, have found many applications in the fields such as physics, biology and economy. The numerical solutions of 2D and 3D SFDEs, which involve solving large-scale systems of linear equations with dense matrices and large condition numbers, at present lack efficient realization methods. . This project aims to design high-efficiency numerical methods for 2D and 3D SFDEs. Its content includes: to design efficient preconditioned iterative methods for the finite element systems, and to theoretically analyze the convergence of the iteration methods. We plan to construct correspondent preconditioners through multigrid methods and domain decomposition methods. Constructing preconditioners is for reducing iteration steps, and employing domain decomposition methods is to make the iterative step parallelizable. The characteristics of the project is that: 1. it pioneers the application of multigrid methods and domain decomposition methods to numerically solving multi-dimensional SFDEs; 2. it expects to acquire fast solvers able to be carried out on the computer cluster, and thus largely increase the efficiency of the solutions for SFDEs.

空间分数阶扩散方程（SFDE）可模拟超扩散现象，在物理、生物、经济等领域有广泛的应用。二维和三维SFDE的数值解法涉及到求解带有“稠密系数矩阵”和“大条件数”的大型线性方程组，至今尚缺少有效的实现方法。. 本项目旨在为二维和三维SFDE研究快速算法，具体内容为：为SFDE的有限元离散系统设计有效的预处理迭代法，并理论分析预处理迭代法的收敛性，其中预处理子我们计划使用多重网格法和区域分解法进行构造。研究预处理子是为了减少迭代法的迭代次数，区域分解法的使用是为了增加每一步迭代的可并行性。本项目的特色为：1、率先将多重网格法和区域分解法应用于多维SFDE的求解；2、得到适用于计算机集群计算的快速算法，有效提高SFDE的求解效率。

本项目研究空间分数阶扩散方程（SFDE）快速求解算法。SFDE离散系统Ax=b中系数矩阵具有如下特点：1）A 是满矩阵或稠密矩阵；2）A的条件数等于O(h^(-2α))，其中h是网格剖分尺度。在二维、三维空间中，离散系统规模大，至今尚缺少有效的实现方法。. 项目计划研究三类问题，已研究前两类，在高收敛速度算法方面取得了一些进展，但研究受阻于计算机硬件数据传输和读写能力（算法在计算机上的实现效率很难提高，不利于成果的应用）。项目已发表SCI论文6篇和一般期刊论文2篇。. 项目针对仅含扩散项的SFDE设计了多重网格法和区域分解法，实验表明算法收敛性好；对称情况下分析出V-cycle多重网格方法和区域分解法分别有最优和拟最优收敛性；对于带有对流项的SFDE，在扩散占优情况下，我们分别设计了多重网格法和区域分解法，且都获得了很好的收敛性；对于对流占优情况下的SFDE，我们特别发展了质量传输型多重网格法和区域分解算法，实验表明我们的算法在求解整数阶对流占优问题时有很好的效果，现阶段我们正在使用依据此思想设计的方法计算对流占优SFDE。. 项目部分成果暂时较难应用于实践-----受限于计算机硬件读写和数据传输能力，算法在计算机上的实现效率尚待提高。能获得收敛速度快的算法，但实现效率难提高，原因是稠密A与向量的乘积无法有效的并行。理想情况下A有Toeplitz矩阵特征，与向量乘积可以通过FFT变换实现，但FFT并行效率不高。.我们耗费大量时间研究并行算法，尝试了多线程共享内存和分布式并行，但都无法显著提高效率。如我们设计方法并行计算Toeplitz矩阵与向量乘积，每个进程的运算量和数据传输量分别是O((N/p)log⁡(N/p))和N/p，其中N是未知数个数，p是进程数；实验中，用多线程共享内存，时间仅降到串行编程的1/5（32线程环境下），原因是每个线程读写共享内存的数据量大，且读写需排队进行（硬件不支持并行读写）；使用多线程分布式存储时，并行效率不如串行。. 从目前的研究来看，分布式存储环境下的编程是无法提高求解SPDE的快速算法的效率。多线程共享内存环境下，如能实现内存读写的并行就可以实现这种效率的提高，而这正是当前并行计算的一个瓶颈。