基于自适应交叉近似的低秩分解算法研究

In recent years, the adaptive cross approximation (ACA)-based low-rank decomposition algorithms have attracted considerable attention because they are accurate and integral kernel-independent. However, these algorithms have relatively high asymptotic computational complexities, which is the major bottleneck of solving electrically (ultra-large) large targets. To address this problem, we focus on the more efficient ACA-based low-rank decomposition algorithms in this project. First, by improving the conventional ACA algorithm and referring to the "butterfly algorithm", we propose a new ACA-based multilevel low-rank decomposition technique, which can reduce the computational complexity of the iterative solution to the ideal O(NlogN) or O(Nlog2N), where N is the number of unknowns. Then, we propose a more efficient direct algorithm base on the new multilevel low-rank decomposition technique. In addition, we develop more powerful methods by combining the new ACA-based algorithms with the characteristic basis function method (CBFM) and multilevel characteristic basis function method (MLCBFM). Finally, these new methods are applied to solve the electromagnetic practical engineering problems. The study has important theoretical and practical value for the development of the accurate, efficient and kernel-independent electromagnetic simulation algorithms.

基于自适应交叉近似(ACA)的低秩分解算法由于具有计算精度高、不依赖于积分核等优点近年来备受关注，但是这些算法均具有较高的渐近计算复杂度，这成为此类方法在(超)电大电磁目标数值仿真分析中的主要瓶颈。为了解决这一问题，本项目对基于ACA的高效低秩分解算法进行深入研究。首先，通过改进传统的ACA分解算法并借鉴“蝶形算法”的思想，研究出一种基于ACA的新型多层低秩分解技术，可以将迭代求解的计算复杂度降至理想的O(NlogN)或者O(Nlog2N)，这里N表示未知量的数目；然后，研究出基于该新型多层低秩分解技术的直接求解算法；在此基础上，与特征基函数法以及多层特征基函数法相结合，通过对缩减矩阵进行快速迭代和直接求解，发展出计算能力更强大的算法；最终将这些新算法应用到实际工程电磁问题中。这对于发展同时具有精度好、效率高、核独立等优点的电磁仿真算法具有重要的理论意义和应用价值。

基于自适应交叉近似(ACA)的低秩分解算法由于具有计算精度高、不依赖于积分核、易于编程实现等优点而备受关注，本项目对基于ACA的低秩分解算法进行深入研究并取得了若干有价值的研究成果。主要的研究成果和进展包括：(1)严格推导出了多层快速自适应交叉(MLACA)分解的误差边界，如果单层ACA 的分解误差不大于e，那么L层MLACA的分解误差不大于(1+e)^(L+1)-1。(2)提出了多层快速自适应交叉近似-特征基函数法(MLFACA-CBFM)快速迭代求解算法，该算法可以将计算和存储复杂度同时降为O(Nlog2N)，这里N表示未知量的数目。(3)提出了基于ACA、SMW公式以及特征基函数的SMWA-CBFM算法，显著降低直接求解的计算时间和存储量。(4)提出了一种基于SMW公式和PI公式的快速算法。当目标的结构发生局部变化时，该算法不需要重复对目标的阻抗矩阵进行LU分解就可以得出精确解，显著提高了计算效率。本项目共发表期刊和会议论文17篇，其中有4篇论文发表在计算电磁学领域顶级期刊IEEE Transaction on Antennas and Propagation上。