求解鞍点问题的混合预处理方法

Restrictively preconditioning is a new kind of preconditioning technique for solving linear saddle-point problem. By the restrictive factorization and variable substitution, the saddle point problem is transformed to the symmetric positive definite one, which can be solved by the short-recurrence methods, for instead, the restrictively preconditioned conjugated gradient method, the restrictively preconditioned Chebyshev method and so on. The Restrictively preconditioned methods are always 'optimal' in terms of the number of iteration steps, i.e. the number of iteration steps is independent on the mesh size of the discretization. However, the efficiency of methods deeply depends on the approximation of Schur Complement matrix. The targets of the project are shortening the number of iteration steps as well as saving the CPU time by approximating the Schur Complement more accurately. Therefore, the Algebraic multigrid method is concerned. We propose to approximate the Schur complements in different mesh size by a serial of matrix polynomials defined recursively and therefore implicitly. The fast algorithm would be developed for this process. With the Collocation of the approximating technique and restrictively preconditioning, the hybrid preconditioning methods for solving saddle-point problem are achieved. The hybrid preconditioning iteration methods is proposed to be optimal in terms of not only number of iteration steps but also CPU time and storage. The convergent theories should be established. The condition number of the hybrid preconditioned matrix and the upper bound of the iterative error should be evidently given.

约束型预处理方法是求解鞍点问题的新型预处理方法。通过约束分解和变量代换，鞍点问题被转化为对称正定问题，继而通过具有短递推格式的迭代算法进行求解，如约束预处理共轭梯度法，约束预处理Chebyshev算法等。这类算法通常具有迭代步数与离散尺度的无关性。该项目拟设计更加准确并且快速近似Schur补矩阵的方法，减少迭代步数的同时，减少单步预处理运行时间。我们采取代数多重网格的思想，依据刚度矩阵与Schur补矩阵在不同网格层上的关系和适当的多项式逼近函数，递归得到Schur补矩阵的隐式近似。这一过程将被设计成快速算法加以实现，并通过与约束预处理算法框架相耦合，得到求解鞍点问题的混合预处理方法。新型预处理方法有望在保持迭代步数“最优”性的同时，缩短预处理过程的计算时间、节约存储空间，达到运行效率上的最优。我们将建立混合预处理的收敛性理论，讨论约束预处理矩阵的条件数并给出迭代误差界的估计。

鞍点问题具有广泛的应用背景，是科学与工程计算的核心问题之一。该线性系统通常规模巨大，其系数矩阵具有非对称、不定且坏条件等特点，如何高效数值求解此类问题是本学科及相关领域的热点问题。本项目结合模型问题的物理背景，利用矩阵分解、矩阵分裂技术等代数学方法，得到了若干高效、稳定的迭代算法和预处理技术，并从理论上阐述了算法的可靠性。主要成果如下：1. 求解带偏微分方程约束优化问题和复对称线性系统的切比雪夫迭代算法。该算法每迭代步在Krylov子空间上找到与真实解误差范数最小的迭代解，具有三项递推格式且无需选取参数，收敛速度与问题参数和网格离散尺度无关且不低于0.42，与其他Krylov子空间类方法相比，由于不含内积运算，更适合于大规模并行计算。2. 求解耦合的分数阶复薛定谔方程的快速迭代算法。此类偏微分方程经有限差分离散后，得到类Toeplitz结构的线性系统，快速Fourier变换无法直接应用。我们针对系数矩阵的结构特点，通过代数学手段，设计了收敛性与离散网格尺度无关的快速算法和预处理子，并通过理论分析，获得了最优参数和最佳收敛速度。3.来源于涡流问题的非埃尔米特鞍点线性系统是电磁场计算中的公认难题。我们发展了求解该问题的分块交替隐式格式，证明了更一般性问题的收敛性，从而得到了高效的迭代格式和预处理子。4. 对于多因子模型序列最小二乘问题，我们构造了修正约束预处理共轭梯度法，在保留已有结果的前提下，通过少量更新，达到股票市场实时求解的需求。团队成员在项目执行过程中积极参加国内外学术活动，与国内外著名学者交流合作，主持和参加了多次国际会议和分组讨论，多次获邀作学术会议的邀请报告和大会报告。积极培养研究生，为本方向培养优秀的科研人才。