1999工作概述

代数方程组与互补问题的高性能算法

在知识创新工程的支持下, 主要研究了大型稀疏线性与弱非线性代数方程组的异步并行算法, 预处理KRYLOV子空间迭代算法以及大型稀疏线性互补问题的同步与异步并行算法。

代数方程组的数值方法及其理论, 是数值分析与科学计算的基础与核心。高性能的线性与非线性代数解法器, 是获得高计算效率和准确计算结果的需要和保证。因此, 随着计算机, 特别是并行计算机的迅速发展, 并行算法, 子空间迭代算法及其预处理, 已成为当前数值代数的国际前沿研究方向。

异步迭代模型, 是并行计算的一个具有广阔应用前景的重要研究方向。这类计算模型无需处理器之间的相互等待, 通讯灵活自由, 并且能够充分利用现有的信息和资源去及时地更新计算进程, 进而提高算法的并行计算效率。这类计算模型适用于多计算机和分布式计算系统, 以及网络并行计算等。另外, 这类异步迭代模型的数学描述和理论研究不受具体计算机结构的约束。因此, 各种异步并行计算方法及其性质的研究, 受到了数值分析, 科学计算, 以及计算机界的高度重视和普遍关注。根据滞后信息充分利用的原则, 运用分块与内外迭代技术, 我们研究了关于大型稀疏线性与弱非线性代数方程组, 以及线性互补问题的异步迭代算法。由于异步迭代自身的非定常性及其中变量的随机性, 其数学描述和理论分析是相当困难和颇具挑战性的。我们建立了求解线性, 弱非线性代数方程组和线性互补问题的各种算法模型, 并在较弱的条件下, 系统地建立了这些算法模型的收敛理论。大量数值实验表明, 这些新算法是求解上述问题的可靠而有效的计算方法。

KRYLOV子空间迭代算法是求解大规模线性代数方程组的最有效方法之一, 而预处理技术则是改善这类方法收敛性质的最有效手段。但是, 好的预处理子的构造, 以及子空间算法的收敛理论, 是非常困难和富有挑战性的。将多层与不精确迭代策略有机地结合, 我们构造了对称正定代数方程组的修正块SSOR预处理子, 精确地估计了预处理矩阵的条件数, 从而在理论上证实了这类预处理迭代算法的有效性和准确性; 对于一般线性代数方程组, 揭示了KRYLOV子空间迭代算法的收敛性质与系数矩阵的特征值, 特征向量, 以及最大JORDAN块的阶数之间的内在关系, 从而进一步完善了子空间迭代算法的收敛理论。

最后, 我们将区域分解原理和分而治之原则有机地统一, 将多重网格思想与多项式加速技术巧妙地结合, 并创造性地运用于以二阶自共轭椭圆型偏微分方程(组)为背景的对称正定线性代数方程组, 构造了具有很高概括性的串行和并行代数多层迭代算法的一般框架, 并证明了这类算法具有``最优阶"的收敛速度。

获得了中国科学院青年科学家奖二等奖 (1999年) 和中国科学院优秀青年奖 (1999年)。

1999年正式发表的论文如下:

A class of asynchronous parallel multisplitting blockwise relaxation methods, Parallel Computing, 25(1999) 681-701.

Block and asynchronous two-stage methods for mildly nonlinear systems, Numerische Mathematik, 82:1(1999) 1-20. (with V. Migall\'{o}n, J. Penad\'{e}s and D.B. Szyld)

Some properties of the block matrices in the parallel decomposition-type relaxation methods, Applied Numerical Mathematics, 29:2(1999) 167-170. (with R. Nabben)

A class of modified block SSOR preconditioners for symmetric positive definite systems of linear equations, Advances in Computational Mathematics, 10(1999) 169-186.

On the convergence of the multisplitting methods for the linear complementarity problem, SIAM Journal on Matrix Analysis and Applications, 21:1(1999) 67-78.

A class of asynchronous multisplitting two-stage iterations for large sparse block systems of weakly nonlinear equations, Journal of Computational and Applied Mathematics, 110(1999) 271-286. (with D.J. Evans and R.C. Calinescu)

Asynchronous multisplitting AOR methods for a class of systems of weakly nonlinear equations, Applied Mathematics and Computation, 98:1(1999) 49-59.

A class of parallel hybrid two-stage iteration methods for the block bordered linear systems, Applied Mathematics and Computation, 101:2-3(1999) 245-267.

Convergence analysis of the two-stage multisplitting method, Calcolo, 36:2(1999) 63-74.

Asynchronous multisplitting relaxation methods for linear complementarity problems, International Journal of Computer Mathematics, 70(1999) 519-538.

A class of synchronous parallel iterative methods for the systems of nonlinear algebraic equations, Mathematica Numerica Sinica, 21:4(1999) 407-416. (In Chinese)

A unified framework for the construction of various algebraic multilevel preconditioning methods, Acta Mathematica Applicatae Sinica, 15(1999) 132-143. (with O. Axelsson)

A new generalized asynchronous parallel multisplitting iteration method, Journal of Computational Mathematics, 17:5(1999) 449-456.

On the convergence of asynchronous nested matrix multisplitting methods for linear systems, Journal of Computational Mathematics, 17:6(1999) 575-588.

A framework of parallel algebraic multilevel preconditioning iterations, Acta Mathematicae Applicatae Sinica, 15:4(1999) 387-395.

Parallel interval matrix multisplitting AOR methods and their convergence, Applied Mathematics and Mechanics, 20(1999) 179-185.

On the convergence of the generalized asynchronous multisplitting block two-stage relaxation methods for the large sparse systems of mildly nonlinear equations, In Proceedings of the Eleventh International Conference on Domain Decomposition Methods (Held in The University of Greenwich, London, England, July 20-24(1998)), Lai Choi-Hong, Bj\o rstad P.E., Cross M. and Widlund O.B. eds., DDM Organization, 214-222(1999). (with D.J. Evans)

1999年参加国际国内学术会议, 并做邀请报告如下:

Matrix multisplitting methods with applications to the linear complementarity problems, The Eighth International Colloquium on Numerical Analysis and Computer Science with Applications, Plovdiv Technical University, Plovdiv, Bulgaria, August 13-17, 1999. (60 minutes)

On the convergence of the parallel non-stationary multisplitting iteration methods, The '99 International Conference on Scientific and Engineering Computing for Young Chinese Scientists, Institute of Computational Mathematics and Scientific/Engineering Computing of Chinese Academy of Sciences, Beijing, July 1-4, 1999. (35 minutes)

Matrix multisplitting methods with applications to the linear complementarity problems, The First China-Canada Congress of Mathematical Sciences, Tsinghua University, Beijing, August 23-27, 1999. (40 minutes)

Modified block SSOR preconditioners for symmetric positive definite linear systems, Nanjing International Conference on Optimization and Numerical Algebra, Nanjing Normal University, Nanjing, September 27-30, 1999. (40 minutes)

Matrix multisplitting methods with applications to the linear complementarity problems, The '99 Annual Conference of Chinese Computational Mathematical Society, Shanghai Normal University, Shanghai, October 6--10, 1999. (40 minutes)

1999年学术讲座如下:

Matrix multisplitting methods and theories, College of Science and Technology, Nihon University, Tokyo, Japan, October 23, 1999. (75 minutes)

Matrix multisplitting methods with applications to the linear complementarity problems, Faculty of Engineering, Kyoto University, Kyoto, Japan, November 12, 1999. (60 minutes)

On the convergence of the parallel non-stationary multisplitting iteration methods, Faculty of Engineering, The University of Tokushima, Tokushima, Japan, November 16, 1999. (60 minutes)

On the convergence of the parallel non-stationary multisplitting iteration methods, The Institute of Physical and Chemical Research (RIKEN), Tokyo, Japan, November 22-25, 1999. (60 minutes)

Introduction to the parallel matrix multisplitting iteration methods for systems of linear equations, Department of Library and Information Science, The University of Library and Information Science, Tsukuba, Japan, December 3 and 7, 1999. (4 \times 60 minutes)