AnO(n 2) incremental algorithm for modular decomposition of graphs and 2-structures

This paper gives anO(n ²) incremental algorithm for computing the modular decomposition of 2-structures [1], [2]. A 2-structure is a type of edge-colored graph, and its modular decomposition is also known as the prime tree family. Modular decomposition of 2-structures arises in the study of relational systems. The modular decomposition of undirected graphs and digraphs is a special case, and has applications in a number of combinatorial optimization problems. This algorithm generalizes elements of a previousO(n ²) algorithm of Muller and Spinrad [3] for the decomposition of undirected graphs. However, Muller and Spinrad's algorithm employs a sophisticated data structure that impedes its generalization to digraphs and 2-structures, and limits its practical use. We replace this data structure with a scheme that labels each edge with at most one node, thereby obtaining an algorithm that is both practical and general to 2-structures.     

混合像元分解的理论与方法-以神木县为例

识别分类是遥感技术应用中的重要一环,而混合像元是影响识别分类精度的主要因素之一。为了提高识别分类精度,本文提出了四种混合像元分解方法,它们是匹配像元分解、折半像元分解、双邻像元分解、相关像元分解。混合像元分解前,计算机分类识别精度仅为63.65％,混合像元分解后,其识别分类精度达88.67％,可见混合像元分解的效果是很显著的。     

A hybridized angle-encouragement-based decomposition approach for many-objective optimization problems

Due to the large objective space when handling many-objective optimization problems (MaOPs), it is a challenging work for multi-objective evolutionary algorithms (MOEAs) to balance convergence and diversity during the search process. Although a number of decomposition-based MOEAs have been designed for the above purpose, some difficulties are still encountered for tackling some difficult MaOPs. As inspired by the existing decomposition approaches, a new Hybridized Angle-Encouragement-based (HAE) decomposition approach is proposed in this paper, which is embedded into a general framework of decomposition-based MOEAs, called MOEA/D-HAE. Two classes of decomposition approaches, i.e., the angle-based decomposition and the proposed encouragement-based boundary intersection decomposition, are sequentially used in HAE. The first one selects appropriate solutions for association in the feasible region of each subproblem, which is expected to well maintain the diversity of associated solutions. The second one acts as a supplement for the angle-based one under the case that no solution is located in the feasible region of subproblem, which aims to ensure the convergence and explore the boundaries. By this way, HAE can effectively combine their advantages, which helps to appropriately balance convergence and diversity in evolutionary search. To study the effectiveness of HAE, two series of well-known test MaOPs (WFG and DTLZ) are used. The experimental results validate the advantages of HAE when compared to other classic decomposition approaches and also confirm the superiority of MOEA/D-HAE over seven recently proposed many-objective evolutionary algorithms.     

Convex Hodge Decomposition and Regularization of Image Flows

The total variation (TV) measure is a key concept in the field of variational image analysis. In this paper, we focus on vector-valued data and derive from the Hodge decomposition of image flows a definition of TV regularization for vector-valued data that extends the standard componentwise definition in a natural way. We show that our approach leads to a convex decomposition of arbitrary vector fields, providing a richer decomposition into piecewise harmonic fields rather than piecewise constant ones, and motion texture. Furthermore, our regularizer provides a measure for motion boundaries of piecewise harmonic image flows in the same way, as the TV measure does for contours of scalar-valued piecewise constant images.

管道泄漏模拟声发射的压缩感知及经验模态分解

管道泄漏监测中常用到声发射信号检测技术。压缩感知理论是一种高效的信号采集压缩处理方法,将其应用到模拟声发射信号的采样重构中,可以使信号采样不再受Nyquist采样定理的限制,降低了数据采集成本,通过重构算法实现对原始信号的精确重构。进而对重构声发射信号进行分解,通过对比信号的经验模态分解,集合经验模态分解和掩膜信号法分解结果,表明掩膜信号法能有效抑制分解过程中存在的模态混叠现象,使分解结果更加精确有效。为声发射信号的特征提取打下坚实基础。     

Particle-field decomposition and domain decomposition in parallel particle-in-cell beam dynamics simulation

Particle-in-cell (PIC) simulation is widely used in many branches of physics and engineering. In this paper, we give an analysis of the particle-field decomposition method and the domain decomposition method in parallel particle-in-cell beam dynamics simulation. The parallel performance of the two decomposition methods was studied on the Cray XT4 and the IBM Blue Gene/P Computers. The domain decomposition method shows better scalability but is slower than the particle-field decomposition in most cases (up to a few thousand processors) for macroparticle dominant applications. The particle-field decomposition method also shows less memory usage than the domain decomposition method due to its use of perfect static load balance. For applications with a smaller ratio of macroparticles to grid points, the domain decomposition method exhibits better scalability and faster speed. Application of the particle-field decomposition scheme to high-resolution macroparticle-dominant parallel beam dynamics simulation for a future light source linear accelerator is presented as an example.     

Information Preserving Time Decompositions of Time Stamped Documents*

Extraction of sequences of events from news and other documents based on the publication times of these documents has been shown to be extremely effective in tracking past events. This paper addresses the issue of constructing an optimal information preserving decomposition of the time period associated with a given document set, i.e., a decomposition with the smallest number of subintervals, subject to no loss of information. We introduce the notion of the compressed interval decomposition, where each subinterval consists of consecutive time points having identical information content. We define optimality, and show that any optimal information preserving decomposition of the time period is a refinement of the compressed interval decomposition. We define several special classes of measure functions (functions that measure the prevalence of keywords in the document set and assign them numeric values), based on their effect on the information computed as document sets are combined. We give algorithms, appropriate for different classes of measure functions, for computing an optimal information preserving decomposition of a given document set. We studied the effectiveness of these algorithms by computing several compressed interval and information preserving decompositions for a subset of the Reuters–21578 document set. The experiments support the obvious conclusion that the temporal information gleaned from a document set is strongly dependent on the measure function used and on other user-defined parameters.

人脸图像的特征提取

人脸识别的研究是模式识别和人工智能领域内的重要课题,有着十分广泛的应用前景。人脸特征的自动提取是人脸自动识别过程中至关重要的一个环节。主要就基于积分投影的人脸图像的特征提取、基于奇异值分解的特征提取及小波特征提取等几种较好方法进行研究。基于积分投影的人脸图像特征点的提取方法对人脸进行定位特别精确。基于小波分解频谱性分析的人脸特征提取极大减少了图像的存储空间和计算复杂度。基于SVD分解的特征提取处理后的正确率很高,计算复杂度也低。     

Singular value decomposition in additive, multiplicative, and logistic forms

Singular value decomposition (SVD) is widely used in data processing, reduction, and visualization. Applied to a positive matrix, the regular additive SVD by the first several dual vectors can yield irrelevant negative elements of the approximated matrix. We consider a multiplicative SVD modification that corresponds to minimizing the relative errors and produces always positive matrices at any approximation step. Another logistic SVD modification can be used for decomposition of the matrices of proportions, when a regular SVD can yield the elements beyond the zero-one range, while the modified SVD decomposition produces all the elements within the correct range at any step of approximation. Several additional modifications of matrix approximation are also considered.     

Partial ensemble approach to resolve the mode mixing of extreme-point weighted mode decomposition

Empirical mode decomposition (EMD) is an effective tool for breaking down components (modes) of a nonlinear and non-stationary signal. Recently, a newly adaptive signal decomposition method, namely extreme-point weighted mode decomposition (EWMD), was put forward to improve the performance of EMD, in particular, to resolve the over- or undershooting issue associated with the large amplitude variations. However, similar to EMD, EWMD also suffers the mode mixing problem caused by intermittence or noisy signals. In this paper, inspired by complementary ensemble EMD (CEEMD), a noise-assisted data analysis method called partial ensemble extreme-point weighted mode decomposition (PEEWMD) is proposed to eliminate the mode mixing problem and enhance the performance of EWMD. In the proposed PEEWMD method, firstly white noises in pairs are added to the targeted signal and then the noisy signals are decomposed using the EWMD method to obtain the intrinsic mode functions (IMFs) in the first several stages. Secondly, permutation entropy is employed to detect the components that cause mode mixing. The residual signal is obtained after the identified components are separated from the original signal. Lastly, the residual signal is fully decomposed by using the EWMD method. The proposed PEEWMD method is compared with original EWMD, ensemble EWMD (EEWMD) and CEEMD using simulated signals. The results demonstrate that PEEWMD can effectively restrain the mode mixing issue and generates IMFs with much better performance. Based on that the PEEWMD and envelope power spectrum based fault diagnosis method was proposed and applied to the rubbing fault identification of rotor system and the fault diagnosis of rolling bearing with inner race. The result indicates that the proposed method of fault diagnosis gets much better effect than EMD and EWMD.     

时间序列稳定协和性的数值分析

§1.引言 许多观测到的时间序列常显示出非平稳性.当时间序列的一阶差分为白噪声时,就产生了非平稳性的简单形式,在这种情况下,称该序列,比如说yt为一阶求和的,记为yt-Ⅰ(1),而对其一阶差分记为△yt-Ⅰ(0).在求和序列的统计分析中,重要的一步是实现对Ⅰ(1)变量的线性组合使之成为Ⅰ(0)就可能实现了,此时称这些变量为协和的.     

再分解优化设计方法

针对主题图的延时和面积优化问题,提出了“再分解”这一新设计方法。该方法采用“逻辑变换”技术,通过减少主题图中“门”的个数以及“最大延时路径”的长度,达到进一步优化主题图面和延时性能的目的。     

VLSI并行测试生成系统的一种动态层次框架

随着VLSI技术的发展和计算机性能的提高,并行测试生成系统不仅必需而且可行,本文在总结已有并行技术的基础上,提出了并行测试生成系统的一种动态层次框架,并给出了一种实现方案。     

Outlier deletion based improvement on the StOMP algorithm for sparse solution of large-scale underdetermined problems

StOMP algorithm is well suited to large-scale underdetermined applications in sparse vector estimations. It can reduce computation complexity and has some attractive asymptotical statistical properties.However,the estimation speed is at the cost of accuracy violation. This paper suggests an improvement on the StOMP algorithm that is more efficient in finding a sparse solution to the large-scale underdetermined problems. Also,compared with StOMP,this modified algorithm can not only more accurately estimate parameters for the distribution of matched filter coefficients,but also improve estimation accuracy for the sparse vector itself. Theoretical success boundary is provided based on a large-system limit for approximate recovery of sparse vector by modified algorithm,which validates that the modified algorithm is more efficient than StOMP. Actual computations with simulated data show that without significant increment in computation time,the proposed algorithm can greatly improve the estimation accuracy.     

自动计算分解和数据划分算法研究

对于分布内存体系结构的并行计算机而言,如何对计算和数据进行合理划分以增加数据本地化减少处理器间的通信是提高其并行性能的关键。本文主要讨论了一种自动实现无数据重组的静态计算和数据划分算法。     

多变量系统传输零点的计算

本文使用奇异值分解和ＱＲ分解方法来计算多变量系统的传输零点，给出了具体算法以及算例。     

An approach to closed-loop subspace identification by orthogonal decomposition

A method of identifying closed-loop systems is developed by using the orthogonal decomposition (ORT) method. The idea is to project the input and output data onto the space of exogenous inputs by using the LQ decomposition to obtain their deterministic components. The ORT-based method is then applied to deterministic components like the direct approach in order to derive state-space models of the plant. We also show that the present method is a subspace version of the two-stage method for transfer function estimation from closed loop data. Some simulation results are included to show the applicability of the present method.     

Decomposition and intersection of simple splinegons

A splinegon is a polygon whose edges have been replaced by well-behaved curves. We show how to decompose a simple splinegon into a union of monotone pieces and into a union of differences of unions of convex pieces. We also show how to use a fast triangulation algorithm to test whether two given simple splinegons intersect. We conclude with examples of splinegons that make the extension of algorithms from polygons to splinegons difficult.Work on this paper by David A. Dobkin and Diane L. Souvaine was partially supported by National Science Foundation Grants MCS 83-03926 and DCR 85-05517. Diane L. Souvaine was also partially supported by an Exxon Foundation Fellowship.     

GA based decomposition of large scale distributed model predictive control systems

A novel method is proposed to find the optimal decomposition structure of distributed model predictive control (DMPC) systems. The input clustering decomposition (ICD) is first developed to minimize the coupling effects of subsystems and average the computational balance of each subsystem. To select the inputs and outputs in each subsystem, the input–output pairing decomposition (IOPD) is done. Then the genetic algorithm is used to solve decomposition problems for ICD and IOPD. The proposed method can achieve efficient coordination. Its structure is more flexible than the traditional DMPC. Two examples are used to show the abilities of the proposed method.