大型稀疏线性系统的保结构并行算法及其在图像分类中的应用

Solving large sparse linear systems is a key problem in science and engineering computation. In general, applying divide and conquer strategy directly may facilitate the choice of numerical algorithms and the parallelization, however, the accuracy of these algorithms is normally low. On the other hand, increasing the accuracy of the numerical algorithms, very often leads to more time-consuming algorithms and, furthermore, the stability properties may become poor. The aim of this project is to construct some high-performance structure preserving parallel algorithms based on the use of special structure and sparsity of the coefficient matrix. In solving linear systems with general structure, the retention of partial correction vector and the distributed matrix-vector multiplication operators will be used to construct the subspace. This strategy could maintain proper linear independence of the basis and thus to mitigate the irregular convergence behavior of the proposed algorithm and enhance its parallel efficiency. In solving linear systems with typical structure, with the aid of structure preserving matrix factorization and the overlapping computation, we will investigate a numerical (or symbolic) algorithm based on the parallel implicit elimination (PIE) process. In the aspect of application, this project concentrates on image classification based on the factorization of nonnegative sparse matrix. We will put forward structure preserving algorithm and its parallelization for natural image classification and face recognition from feature encoding and dimensionality reduction techniques respectively.

大型稀疏线性系统的求解是科学与工程计算中的核心问题。通常情况下，采用直接的分而治之策略虽然有利于算法的选择和并行化，却难以保证计算的精度。另一方面，在提高算法计算精度的过程中又往往伴随着大量的时间消耗以及稳定性的下降。本项目旨在利用原系统系数矩阵的特殊结构和稀疏特性，构造相应的高性能保结构并行算法。在针对一般结构线性系统的求解方面，将采取保留部分修正向量信息和分布式矩阵向量乘积算子相结合的策略来构造求解子空间。这种策略可以使前后求解子空间保持适当的线性无关性，从而有效解决算法的不规则收敛现象并提升其并行效率。对于具有典型结构的线性系统，将借助矩阵的保结构分解和计算重叠技术，研究基于具有内在并行特性的PIE消去过程的数值或符号算法。在应用方面，本项目将研究基于稀疏非负矩阵分解的图像分类方法。我们将从特征编码和数据降维两个角度来讨论针对自然图像分类和人脸识别的保结构算法及其并行实现。

随着现代科学技术的快速发展，大型稀疏线性系统的求解逐渐成为科学与工程计算中的核心问题。然而，单纯依靠硬件设备的改善并不足以解决由于离散系统阶数过高所造成的计算过程不稳定，计算效率低下等问题，因此冲破传统的数值算法设计框架和分析方法，研究大型稀疏系统的高效数值计算方法就显得尤为重要了。本项目在理论方面旨在利用高阶离散系统的特殊结构和稀疏特性，分别构造针对具有一般结构和典型结构的大规模稀疏线性系统的高性能保结构并行求解算法。在应用方面，本项目主要研究了基于稀疏非负矩阵分解的图像分类方法。具体内容包括：（1）研究了基于标准的 Krylov 子空间方法并提出了一种保留部分修正向量信息的多步 Krylov 子空间算法的求解框架及其并行化策略；（2）研究了具有带状、循环、可变带宽等结构的稀疏矩阵的多种保结构分解和式与分解积式，并讨论了分解的存在性条件，进而构造了相应线性系统的并行求解算法；（3）结合分布式矩阵向量乘积算子和经典 GaBP 算法的并行特性提出了动态负载均衡的多核并行 GaBP 算法以平衡各处理器之间的负载。同时，采用通信与计算重叠技术以降低处理器的等待开销。由于各处理器上子系统的求解和缩减方程的求解采用相同的计算逻辑，从而构造出一种新型的两层次方法。（4）借助稀疏非负矩阵的保结构分解算法，研究了基于交替方向法的用于联合稀疏向量恢复的快速求解算法并将其应用于特定的自然图像分类问题。