New Estimates for the Rate of Convergence of the Method of Subspace Corrections

We discuss estimates for the rate of convergence of the method of successive subspace corrections in terms of condition number estimate for the method of parallel subspace corrections.We provide upper bounds and in a special case,a lower bound for preconditioners defined via the method of successive subspace corrections.

A Further Result on the Cyclic Subspace

Based on the geometric theories of vector space, a Cross-Identity theorem is proved for the relationship between the power kernels and power images of linear map on its cyclic subspace. By this result, a new approach of proof is found for the fact that a square matrix with only one eigenvalue and one-dimensional eigenspace is similar to a Jordan block matrix.

线性方程组与四个基本子空间

在大学课程教学中,对齐次(或非齐次)线性方程组,通常借助高斯消元法和简化行阶梯型,以及基础解系(极大无关组)等,给出了线性方程组解的整体结构形式.本文试图从系数矩阵“四个基本子空间”出发,探讨矩阵的“四个基本子空间”与线性方程组之间的内在联系,归纳总结了相关结果.以期帮助学生,深刻理解线性方程组与解空间的本质.

关于线性子空间的并集的一个注记

设V是一个线性空间,不考虑V上的数量乘法运算和加法运算满足的交换律,则V构成一个群.给出了一个群V可以写成三个真子群的并集的充分必要条件.

一种基于敏捷集群计算系统的并行GMRES方法

随着通信系统和人工智能的飞速发展,以智慧城市、智慧工厂和智能制造等为代表的多种新型应用场景不断涌现,使得通信、感知和计算等系统的一体化成为技术发展的新趋势。人工智能新型应用场景对大规模高效敏捷计算提出了新的要求,基于敏捷集群计算系统,提出了一种并行广义最小残差(Generalized Minimal Residual, GMRES)方法,主要通过并行矩阵向量乘法和并行高瘦矩阵QR(Tall and Skinny QR,TSQR)分解实现Krylov子空间的高效并行构造,充分利用集群计算系统的计算和通信性能,实现大规模线性方程组Ax=b的快速求解,其中A为一个n×n的矩阵,在工程实践中,n可达数十万甚至百万规模。通过求解二维泊松方程的有限元离散得到的刚度方程,验证了算法的有效性。

基于子空间学习的快速自适应局部比值和判别分析

降维是处理高维数据的一项关键技术,其中线性判别分析及其变体算法均为有效的监督算法。然而大多数判别分析算法存在以下缺点:a)无法选择更具判别性的特征;b)忽略原始空间中噪声和冗余特征的干扰;c)更新邻接图的计算复杂度高。为了克服以上缺点,提出了基于子空间学习的快速自适应局部比值和判别分析算法。首先,提出了统一比值和准则及子空间学习的模型,以在子空间中探索数据的潜在结构,选择出更具判别信息的特征,避免受原始空间中噪声的影响;其次,采用基于锚点的策略构造邻接图来表征数据的局部结构,加速邻接图学习;然后,引入香农熵正则化,以避免平凡解;最后,在多个数据集上进行了对比实验,验证了算法的有效性。

IMinpert:An Incomplete Minimum Perturbation Algorithm for Large Unsymmetric Linear Systems

This paper gives the truncated version of the Minpert method:the incomplete minimum perturbation algorithm(IMinpert).It is based on an incomplete orthogonal- ization of the Krylov vectors in question,and gives a quasi-minimum backward error solution over the Krylov subspace.In order to make the practical implementation of IMinpert easy and convenient,we give another approximate version of the IMinpert method:A-IMinpert.Theoretical properties of the latter algorithm are discussed.Nu- merical experiments are reported to show the proposed method is effective in practice and is competitive with the Minpert algorithm.

Multiple linear system techniques for 3D finite element method modeling of direct current resistivity

The strategies that minimize the overall solution time of multiple linear systems in 3D finite element method (FEM) modeling of direct current (DC) resistivity were discussed. A global stiff matrix is assembled and stored in two parts separately. One part is associated with the volume integral and the other is associated with the subsurface boundary integral. The equivalent multiple linear systems with closer right-hand sides than the original systems were constructed. A recycling Krylov subspace technique was employed to solve the multiple linear systems. The solution of the seed system was used as an initial guess for the subsequent systems. The results of two numerical experiments show that the improved algorithm reduces the iterations and CPU time by almost 50%, compared with the classical preconditioned conjugate gradient method.

Linear manifold clustering for high dimensional data based on line manifold searching and fusing

High dimensional data clustering,with the inherent sparsity of data and the existence of noise,is a serious challenge for clustering algorithms.A new linear manifold clustering method was proposed to address this problem.The basic idea was to search the line manifold clusters hidden in datasets,and then fuse some of the line manifold clusters to construct higher dimensional manifold clusters.The orthogonal distance and the tangent distance were considered together as the linear manifold distance metrics. Spatial neighbor information was fully utilized to construct the original line manifold and optimize line manifolds during the line manifold cluster searching procedure.The results obtained from experiments over real and synthetic data sets demonstrate the superiority of the proposed method over some competing clustering methods in terms of accuracy and computation time.The proposed method is able to obtain high clustering accuracy for various data sets with different sizes,manifold dimensions and noise ratios,which confirms the anti-noise capability and high clustering accuracy of the proposed method for high dimensional data.

A QUASI-MINIMAL RESIDUAL VARIANT OF THE IOM(q) FOR LARGE UNSYMMETRIC LINEAR SYSTEMS

The Incomplete Orthogonalization Method (IOM(q)), a truncated version of the Full Orthogonalization Method (FOM) proposed by Saad, has been used for solving large unsymme- tric linear systmes. However, the IOM(q) exhibites irregular convergence behavior with wild oscillation in the residual norms though it tends to decrease in a very slow manner, which is owing to the lack of minimization property over the Krylov subspace. QMR method proposed by Freund, Gutknecht and Nachtigal, owing to its ability to avoid breakdowns and smooth convergence behavior, is a robust iterative solver for general nonsingular unsymmetric linear systems. In this paper, we propose a novel quasi-minimal residual (QMR) variant of the Incomplete Orthogona- lization Method (IOM(q)). Numerical experiments show that it has smooth convergence behavior and is more effective, especially when using its restarted version.

Researted FOM for Multiple Shifted Linear Systems

The seed method is used for solving multiple linear systems A (i)x (i) =b (i) for 1≤i≤s, where the coefficient matrix A (i) and the right-hand side b (i) are different in general. It is known that the CG method is an effective method for symmetric coefficient matrices A (i). In this paper, the FOM method is employed to solve multiple linear sy stems when coefficient matrices are non-symmetric matrices. One of the systems is selected as the seed system which generates a Krylov subspace, then the resi duals of other systems are projected onto the generated Krylov subspace to get t he approximate solutions for the unsolved ones. The whole process is repeated u ntil all the systems are solved.

Double Optimal Regularization Algorithms for Solving Ill-Posed Linear Problems under Large Noise

A double optimal solution of an n-dimensional system of linear equations Ax=b has been derived in an affine m-dimensional Krylov subspace with m <<n.We further develop a double optimal iterative algorithm(DOIA),with the descent direction z being solved from the residual equation Az=r0 by using its double optimal solution,to solve ill-posed linear problem under large noise.The DOIA is proven to be absolutely convergent step-by-step with the square residual error ||r||^2=||b-Ax||^2 being reduced by a positive quantity ||Azk||^2 at each iteration step,which is found to be better than those algorithms based on the minimization of the square residual error in an m-dimensional Krylov subspace.In order to tackle the ill-posed linear problem under a large noise,we also propose a novel double optimal regularization algorithm(DORA)to solve it,which is an improvement of the Tikhonov regularization method.Some numerical tests reveal the high performance of DOIA and DORA against large noise.These methods are of use in the ill-posed problems of structural health-monitoring.

A New Preconditioner with Two Variable Relaxation Parameters for Saddle Point Linear Systems with Highly Singular(1,1) Blocks

In this paper, we provide new preconditioner for saddle point linear systems with (1,1) blocks that have a high nullity. The preconditioner is block triangular diagonal with two variable relaxation paremeters and it is extension of results in [1] and [2]. Theoretical analysis shows that all eigenvalues of preconditioned matrix is strongly clustered. Finally, numerical tests confirm our analysis.

A QMR-Type Algorithm for Drazin-Inverse Solution of Singular Nonsymmetric Linear Systems

In this paper, we propose DQMR algorithm for the Drazin-inverse solution of consistent or inconsistent linear systems of the form Ax=b where is a singular and in general non-hermitian matrix that has an arbitrary index. DQMR algorithm for singular systems is analogous to QMR algorithm for non-singular systems. We compare this algorithm with DGMRES by numerical experiments.

Unsupervised linear spectral mixture analysis with AVIRIS data

A new algorithm for unsupervised hyperspectral data unmixing is investigated, which includes a modified minimum noise fraction (MNF) transformation and independent component analysis (ICA). The modified MNF transformation is used to reduce noise and remove correlation between neighboring bands. Then the ICA is applied to unmix hyperspectral images, and independent endmembers are obtained from unmixed images by using post-processing which includes image segmentation based on statistical histograms and morphological operations. The experimental results demonstrate that this algorithm can identify endmembers resident in mixed pixels. Meanwhile, the results show uhe high computational efficiency of the modified MNF transformation. The time consumed by the modified method is almost one fifth of the traditional MNF transformation.

融合线性插值和对抗性学习的深度子空间聚类

聚类算法的研究受到广泛关注,但现有聚类算法通常无法对样本进行精准的聚类且不能有效分离个体聚簇,从而导致聚类模型泛化性能弱等问题。针对于此,提出了一种融合线性插值和对抗性学习的深度子空间聚类模型。该模型在编码器部分使用混合函数和来自均匀分布的α系数对两个样本的隐表示进行线性插值,得到新的混合输出;进而利用子空间聚类模型对混合输出和原样本隐变量进行聚类,有效提升模型对难分类样本的聚类精度。同时,将对抗性学习引入自编码器并在重构数据集上训练一个鉴别器,用于预测α系数,从而提升混合输出的数据质量。在3个公开数据集上进行实验,采用准确率(ACC)和归一化互信息(NMI)对所提算法进行评估。在Extended Yale B、ORL、COIL20数据集上准确率分别达到了0.9761、0.8743、0.9423,与现有的一些算法相比,所提算法的ACC和NMI均有较大的提升,验证了模型在处理难分类样本时,性能具有明显优于现有模型。

基于子空间流形的图像集识别方法

近年来,基于黎曼流形将图像集在线性子空间中进行表征的图像集识别方法已经被证实有良好的效果,针对该领域存在的图像线性子空间大多高维所导致现有黎曼流形的图像集识别方法存在计算成本高、适用性有限的问题,提出一种基于子空间流形的图像集识别方法。首先,从线性子空间的几何结构出发,利用Grassmann流形对线性子空间进行建模,得到基于Grassmann流形的联合黎曼度量。然后,通过该联合黎曼度量,从高维的Grassmann流形中学习到一个低维的Grassmann流形。最后,对通过学习得到的低维流形上的图像集数据进行图像集识别。实验结果表明,在ETH-80数据集上该方法的识别准确率比投影度量学习(PML)和图嵌入Grassmann判别分析(GGDA)都分别提升了2.5个百分点。证明了在通过提出的度量与方法学习到的低维流形上,图像集数据具有更好的分类结构,从而降低图像集识别计算成本,扩大适用范围,提升识别准确率。

The Convergence of Krylov Subspace Methods for Large Unsymmetric Linear Systems

The convergence problem of many Krylov subspace methods, e.g., FOM, GCR, GMRES and QMR, for solving large unsymmetric (non-Hermitian) linear systems is considered in a unified way when the coefficient matrix A is defective and its spectrum lies in the open right (left) half plane. Related theoretical error bounds are established and some intrinsic relationships between the convergence speed and the spectrum of A are exposed. It is shown that these methods are likely to converge slowly once one of the three cases occurs: A is defective, the distribution of its spectrum is not favorable, or the Jordan basis of A is ill conditioned. In the proof, some properties on the higher order derivatives of Chebyshev polynomials in an ellipse in the complex plane are derived, one of which corrects a result that has been used extensively in the literature.

Similarity-Invariant Subspaces and Similarity-Preserving Linear Maps

In this paper, the similarity-invariant subspaces of B(H), which is tile Banach algebra of all bounded linear operators on a separable infinite-dimensional Hilbert space H, are completely characterized and the representations of bounded linear maps on B(H) which preserve similarity in both directions are given.

Some Results on the Range-Restricted GMRES Method

In this paper we reconsider the range-restricted GMRES (RRGMRES) method for solving nonsymmetric linear systems. We first review an important result for the usual GMRES method. Then we give an example to show that the range-restricted GMRES method does not admit such a result. Finally, we give a modified result for the range-restricted GMRES method. We point out that the modified version can be used to show that the range-restricted GMRES method is also a regularization method for solving linear ill-posed problems.