一种LU分解与迭代法的结合策略及算法实现

在矩阵求解算法中，直接法或迭代法都不能有效地求解大规模稀疏或病态矩阵,因此提出一种LU分解与迭代法结合的策略。采用LU分解对矩阵进行预处理，以提高迭代法的收敛性,并采用一种判断策略使矩阵的LU分解结果可最大限度地重复利用。此结合策略应用于两种共轭梯度（CG）法，得到CLUCG和CLUTCG两种算法。它们已应用于模拟和混合信号电路模拟器ZeniVDE中。大量实验结果表明此结合策略是很有效的，得到的两种算法具有较快的速度和较好的收敛性。     

A sequential factorization method for recovering shape and motionfrom image streams

We present a sequential factorization method for recovering the three-dimensional shape of an object and the motion of the camera from a sequence of images, using tracked features. The factorization method originally proposed by Tomasi and Kanade (1992) produces robust and accurate results incorporating the singular value decomposition. However, it is still difficult to apply the method to real-time applications, since it is based on a batch-type operation and the cost of the singular value decomposition is large. We develop the factorization method into a sequential method by regarding the feature positions as a vector time series. The new method produces estimates of shape and motion at each frame. The singular value decomposition is replaced with an updating computation of only three dominant eigenvectors, which can be performed in O(P²) time, while the complete singular value decomposition requires O(FP²) operations for an F×P matrix. Also, the method is able to handle infinite sequences, since it does not store any increasingly large matrices. Experiments using synthetic and real images illustrate that the method has nearly the same accuracy and robustness as the original method     

从运动中恢复目标结构的改进因子分解法

因子分解法是从图像序列中恢复刚体目标几何结构的重要方法。针对传统因子分解法基本过程中存在的不足,及其容易失效的缺点,提出一种改进的因子分解法。该方法避开传统方法中求解修正矩阵的复杂过程,利用旋转矩阵的特性,直接修正由传统方法奇异值分解(SVD)得到的每帧图像的旋转矩阵,然后根据观测矩阵和得到的旋转矩阵,直接利用线性最小二乘法求解目标的结构矩阵。仿真和实测数据的实验结果表明,本文方法能够有效地从序列图像中恢复目标的几何结构,相比传统因子分解法,在稳定性上有较大的提升。     

改进的从运动中恢复目标结构的因子分解法

因子分解法是从图像序列中恢复刚体目标几何结构的重要方法。介绍了传统因子分解法的基本过程,分析了该方法存在的不足,并针对该方法容易失效的缺点,提出一种改进的因子分解法。该方法避开传统方法中求解修正矩阵的复杂过程,利用旋转矩阵的特性,直接修正由传统方法SVD分解得到的每帧图像的旋转矩阵,然后根据观测矩阵和得到旋转矩阵直接利用线性最小二乘法求解目标的结构矩阵。仿真和实测数据的实验结果表明,本文方法能够有效地从序列图像中恢复目标的几何结构,相比传统的因子分解法而言,在稳定性上有较大的提升。     

A simple ILU preconditioning coupled to Orthomin method

Conjugate gradient type methods with preconditionings based on incompleteLU factorization (ILU) are known to be very useful for solving nonsymmetric linear systems of equations. In particular, the effectiveness of such iterative methods has been demonstrated on sparse linear systems which arise from discretizing non-self adjoint elliptic problems. In this paper, we present a simplifiedILU preconditioning coupled to a variational iterative method (Orthomin) on a model problem. It is shown that this simplified version ofILU is easy to implement and when coupled to Orthomin method, is as competitive or better than the standardILU with Orthomin method.     

将椭圆曲线分解算法扩展为三阶段的方案

椭圆曲线法是目前使用最广泛的整数分解算法之一,最早由Lenstra于1985年提出,原始的算法只有第一阶段。自其提出以来,围绕算法和实现的研究层出不穷,最重要的改进是 Brent 和 Montgomery 提出椭圆曲线法的第二阶段,这极大地提升了椭圆曲线算法的分解能力和效率。将椭圆曲线法扩展为三阶段,采用的方法是将第一阶段和第二阶段进行“融合”。对比目前流行的两阶段椭圆曲线法,改进后的算法有两方面的优点：一是在保持同两阶段椭圆曲线法参数相同的情况下,通过增加微不足道的消耗,提升找到因子的概率;二是在搜寻同一个因子时,可以使用较小的“光滑参数”。     

A reanalysis method for local modification and the application in large-scale problems

A novel reanalysis method, named independent coefficients (IC) method is suggested in this study. This method is proposed to reanalyze structures with local modification which leads to a low-rank change in the stiffness matrix. IC method requires only initial solution as input, and can determine the independent coefficients for each degree of freedoms (DOFs) influenced by structural modifications. Since any extra operations such as decomposition of the initial stiffness matrix is not involved in computation procedure, the IC is a “cheap” algorithm and can be an alternative choice for reanalysis. In order to verify the performance of IC method, several large scale numerical examples are tested. The results demonstrate that the IC method has high accuracy as well as efficiency when the modification is local. The cases involving beyond 1,500,000 DOFs and 3,000,000 DOFs show that IC method has low demands on computer storage, and large scale problems can be easily reanalyzed by this method.     

Accuracy improvement of a multistep splitting method for nonlinear viscous wave equations

This paper focuses on a multistep splitting method for a class of nonlinear viscous equations in two spaces, which uses second-order backward differentiation formula (BDF2) combined with approximation factorization for time integration, and second-order centred difference approximation to second derivatives for spatial discretization. By the discrete energy method, it is shown that this splitting method can attain second-order accuracy in both time and space with respect to the discrete L²- and H¹-norms. Moreover, for improving computational efficiency, we introduce a Richardson extrapolation method and obtain extrapolation solution of order four in both time and space. Numerical experiments illustrate the accuracy and performance of our algorithms.     

GPU-accelerated preconditioned iterative linear solvers

This work is an overview of our preliminary experience in developing a high-performance iterative linear solver accelerated by GPU coprocessors. Our goal is to illustrate the advantages and difficulties encountered when deploying GPU technology to perform sparse linear algebra computations. Techniques for speeding up sparse matrix-vector product (SpMV) kernels and finding suitable preconditioning methods are discussed. Our experiments with an NVIDIA TESLA M2070 show that for unstructured matrices SpMV kernels can be up to 8 times faster on the GPU than the Intel MKL on the host Intel Xeon X5675 Processor. Overall performance of the GPU-accelerated Incomplete Cholesky (IC) factorization preconditioned CG method can outperform its CPU counterpart by a smaller factor, up to 3, and GPU-accelerated The incomplete LU (ILU) factorization preconditioned GMRES method can achieve a speed-up nearing 4. However, with better suited preconditioning techniques for GPUs, this performance can be further improved.     

Modal Hermite spectral collocation method for solving multi-dimensional hyperbolic telegraph equations

The present research is contemplated proposing a numerical solution of multi-dimensional hyperbolic telegraph equations with appropriate initial time and boundary space conditions. The truncated Hermite series with unknown coefficients are used for approximating the solution in both of the spatial and temporal variables. The basic idea for discretizing the considered one-dimensional (1D), two-dimensional (2D) and three-dimensional (3D) telegraph equations is based on the collocation method together with the Hermite operational matrices of derivatives. The resulted systems of linear algebraic equations are solved by some efficient methods such as LU factorization. The solution of the algebraic system contains the coefficients of the truncated Hermite series. Numerical experiments are provided to illustrate the accuracy and efficiency of the presented numerical scheme. Comparisons of numerical results associated to the proposed method with some of the existing numerical methods confirm that the method is accurate and fast experimentally.     

丰富图像标签的正则化非负矩阵分解方法

目的 随着Web2.0技术的进步,以用户生成内容为中心的社交网站蓬勃发展,也使得基于图像标签的图像检索技术越来越重要。但是,由于用户标注时的随意性和个性化,导致用户提交的图像标签不够完备,降低了图像检索的准确性。方法 针对这一问题,提出一种正则化的非负矩阵分解方法来丰富图像欠完备的标签,提高图像标签的完备性。利用非负矩阵分解的方法将原始的标签-图像矩阵投影到潜在的低秩空间里消除噪声,同时利用图像的类内视觉离散度作为正则化项提高消除噪声、丰富标签的效果。结果 利用从社交网站Flickr上下载的大量社交图像进行对比实验,验证了本文方法对丰富图像标签的有效性。通过对比目前流行的优化算法,本文算法获得较高的性能提升,算法平均准确度提高了12.3%。结论 将图像类内视觉离散度作为正则化项的非负矩阵分解算法,能较好地丰富社交图像的标签,解决网络图像标签的欠完备问题。     

Improved accuracy for the approximate factorization of parabolic equations

A general procedure to construct alternating direction implicit (ADI) schemes for multidimensional problems was originated by Beam and Warming, using the method of approximate factorization. The technique which can be combined with a high-order linear multistep (LM) method introduces a factorization error that is of order two in the time step Δt. Thus, the approximate factorization method imposes a second-order temporal accuracy limitation independent of the accuracy of the LM method chosen as the time differencing approximation. We introduce a correction term to the right-hand side of a factored scheme to increase the order of the factorization error in Δt, and recover the temporal order of the original scheme. The method leads in particular to the modified ADI scheme proposed by Douglas and Kim. A convergence proof is given for the improved scheme based on the BDF2 method.     

A method of facial expression recognition based on Gabor and NMF

The technology of facial expression recognition is a challenging problem in the field of intelligent human-computer interaction. An algorithm based on the Gabor wavelet transformation and non-negative matrix factorization (G-NMF) is presented. The main process includes image preprocessing, feature extraction and classification. At first, the face region containing emotional information is obtained and normalized. Then, expressional features are extracted by Gabor wavelet transformation and the high-dimensional data are reduced by non-negative matrix factorization (NMF). Finally, two-layer classifier (TLC) is designed for expression recognition. Experiments are done on JAFFE facial expressions database. The results show that the method proposed has a better performance.     

Parallel Performance of Block ILU Preconditioners for a Block-tridiagonal Matrix

The parallelizable block ILU (incomplete LU) factorization preconditioners for a block-tridiagonal matrix have been recently proposed by the author. In this paper, we describe a parallelization of Krylov subspace methods with the block ILU factorization preconditioners on distributed-memory computers such as the Cray T3E, and then parallel performance results of a preconditioned Krylov subspace method are provided to evaluate the effectiveness and efficiency of the block ILU preconditioners on the Cray T3E.     

Matrix factorization method to stabilize multivariable control systems

A new method to study the stability of n-input-n-output linear time-invariant feedback systems is proposed. First, a new factorization of the transfer-functions matrix is developed which allows a direct analysis of the stability of a multivariable system. Then, some properties of this factorization are studied and finally, a design method is inferred from these properties. The method permits an easy design of stable controllers. It allows the influence of the off-diagonal elements of the controller on the stability of the closed loop system to be studied.     

Supernodal sparse Cholesky factorization on graphics processing units

Sparse Cholesky factorization is the most computationally intensive component in solving large sparse linear systems and is the core algorithm of numerous scientific computing applications. A large number of sparse Cholesky factorization algorithms have previously emerged, exploiting architectural features for various computing platforms. The recent use of graphics processing units (GPUs) to accelerate structured parallel applications shows the potential to achieve significant acceleration relative to desktop performance. However, sparse Cholesky factorization has not been explored sufficiently because of the complexity involved in its efficient implementation and the concerns of low GPU utilization. In this paper, we present a new approach for sparse Cholesky factorization on GPUs. We present the organization of the sparse matrix supernode data structure for GPU and propose a queue‐based approach for the generation and scheduling of GPU tasks with dense linear algebraic operations. We also design a subtree‐based parallel method for multi‐GPU system. These approaches increase GPU utilization, thus resulting in substantial computational time reduction. Comparisons are made with the existing parallel solvers by using problems arising from practical applications. The experiment results show that the proposed approaches can substantially improve sparse Cholesky factorization performance on GPUs. Relative to a highly optimized parallel algorithm on a 12‐core node, we were able to obtain speedups in the range 1.59× to 2.31× by using one GPU and 1.80× to 3.21× by using two GPUs. Relative to a state‐of‐the‐art solver based on supernodal method for CPU‐GPU heterogeneous platform, we were able to obtain speedups in the range 1.52× to 2.30× by using one GPU and 2.15× to 2.76× by using two GPUs. Concurrency and Computation: Practice and Experience, 2013. Copyright © 2013 John Wiley & Sons, Ltd.     

基于独立成分的局部建模方法及其在近红外光谱分析中的应用研究

建立了一种基于独立成分分析的局部建模新方法,该方法首先将独立成分分析(ICA)用于近红外光谱的特征提取,然后,根据所提取的独立成分选择校正集中与预测样本相邻近的样本构成校正子集,建立局部偏最小二乘(PLS)回归模型并对预测样本进行预测。将所提出的方法应用于烟草样品中尼古丁含量的测定,所得结果优于常用的全局建模方法。     

面向社会化电子商务的信任感知协同过滤推荐方法

为提高社会化电子商务推荐服务的精确度和有效性,综合考虑交易评价得分、交易次数、交易金额、直接信任、推荐信任等影响社会化电子商务用户信任关系的因素,设计了一种信任感知协同过滤推荐方法.该方法利用置信因子计算用户间的信任关系,采用余弦相关度法计算用户间的相似度,引入调和因子综合用户信任关系和用户相似度对商品预测评分的影响,以平均绝对误差(MAE)、评分覆盖率和用户覆盖率作为评价指标.实验结果表明,与标准协同过滤推荐方法、基于规范矩阵因式分解的推荐方法相比,信任感知协同过滤推荐方法将MAE降低到0.162,并将评分覆盖率和用户覆盖率分别提高到77%和80%,能够解决交易评价较少商品的推荐问题.     

A CPU-GPU hybrid approach for the unsymmetric multifrontal method

Multifrontal is an efficient direct method for solving large-scale sparse and unsymmetric linear systems. The method transforms a large sparse matrix factorization process into a sequence of factorizations involving smaller dense frontal matrices. Some of these dense operations can be accelerated by using a graphic processing unit (GPU). We analyze the unsymmetric multifrontal method from both an algorithmic and implementational perspective to see how a GPU, in particular the NVIDIA Tesla C2070, can be used to accelerate the computations. Our main accelerating strategies include (i) performing BLAS on both CPU and GPU, (ii) improving the communication efficiency between the CPU and GPU by using page-locked memory, zero-copy memory, and asynchronous memory copy, and (iii) a modified algorithm that reuses the memory between different GPU tasks and sets thresholds to determine whether certain tasks be performed on the GPU. The proposed acceleration strategies are implemented by modifying UMFPACK, which is an unsymmetric multifrontal linear system solver. Numerical results show that the CPU-GPU hybrid approach can accelerate the unsymmetric multifrontal solver, especially for computationally expensive problems.     

Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization

The matrix separation problem aims to separate a low-rank matrix and a sparse matrix from their sum. This problem has recently attracted considerable research attention due to its wide range of potential applications. Nuclear-norm minimization models have been proposed for matrix separation and proved to yield exact separations under suitable conditions. These models, however, typically require the calculation of a full or partial singular value decomposition at every iteration that can become increasingly costly as matrix dimensions and rank grow. To improve scalability, in this paper, we propose and investigate an alternative approach based on solving a non-convex, low-rank factorization model by an augmented Lagrangian alternating direction method. Numerical studies indicate that the effectiveness of the proposed model is limited to problems where the sparse matrix does not dominate the low-rank one in magnitude, though this limitation can be alleviated by certain data pre-processing techniques. On the other hand, extensive numerical results show that, within its applicability range, the proposed method in general has a much faster solution speed than nuclear-norm minimization algorithms and often provides better recoverability.