Multi-Dimensional Pattern Matching with Dimensional Wildcards: Data Structures and Optimal On-Line Search Algorithms

We introduce a new multidimensional pattern matching problem that is a natural generalization of string matching, a well studied problem[1]. The motivation for its algorithmic study is mainly theoretical. LetA[1:n₁,…,1:n_d] be a text matrix withN = n₁…n_dentries andB[1:m₁,…,1:m_r] be a pattern matrix withM = m₁…m_rentries, whered ≥ r ≥ 1 (the matrix entries are taken from an ordered alphabet Σ). We study the problem of checking whether somer-dimensional submatrix ofAis equal toB(i.e., adecisionquery).Acan be preprocessed andBis given on-line. We define a new data structure for preprocessingAand propose CRCW-PRAM algorithms that build it inO(log N) time withN²/n_maxprocessors, wheren_max = max(n₁,…,n_d), such that the decision query forBtakesO(M) work andO(log M) time. By using known techniques, we would get the same preprocessing bounds but anO((^d_r)M) work bound for the decision query. The latter bound is undesirable since it can depend exponentially ond; our bound, in contrast, is independent ofdand optimal. We can also answer, in optimal work, two further types of queries: (a) anenumerationquery retrieving all ther-dimensional submatrices ofAthat are equal toBand (b) anoccurrencequery retrieving only the distinct positions inAthat correspond to all of these submatrices. As a byproduct, we also derive the first efficient sequential algorithms for the new problem.     

Data Structures for Extension Violations in a Query Range

Design Rule Checking (DRC) in VLSI design involves checking if a given VLSI layout satisfies a given set of rules and reporting the violations if any. We propose data structures for reporting violations of the minimum extension rule in a query window of interest.     

方阵的开方问题

运用Jordan标准形理论,完整解决了复数方阵、实数方阵能否开平方、开立方的问题.     

利用矩阵的初等变换求方阵的特征值

高阶方阵的特征值的求得,需求解一元高次方程,这往往有一定的难度.本文依据矩阵的初等变换的一些良好性质,介绍两种利用矩阵的初等变换化简方阵的特征值的计算的方法.     

Construction of Real Band Anti-Symmetric Matrices from Spectral Data

In this paper,we describe how to construct a real anti-symmetric(2p-1)-band matrix with prescribed eigenvalues in its ρ leading principal submatrices.This is done in two steps.First,an anti-symmetric matrix B is constructed with the specified spectral data but not necessary a band matrix.Then B is transformed by Householder transformations to a (2ρ-1)-band matrix with the prescribed eigenvalues.An algorithm is presented.Numerical results are presented to demonstrate that the proposed method is effective.     

A Kind of Square Matrices and Its Qualities

ＡＫｉｎｄｏｆＳｑｕａｒｅＭａｔｒｉｃｅｓａｎｄＩｔｓＱｕａｌｉｔｉｅｓ￥ＷｅｉＺｏｎｇｌｉ（ＬｕｏｙａｎｇＴｅａｃｈｅｒｓＣｏｌｌｅｇｅ）Ａｂｓｔｒａｃｔ：ＴｈｉｓｐｅｐｅｒｄｉｓｃｕｓｓｅｓａｋｉｎｄｏｆＳｑｕａｒｅｍａｔｒｉｃｅｓｗｈｉｃｓｉｓ...     

有关实正定方阵行列式的几个不等式

本文得到实正定方阵行列式的几个不等式，改进了近期研究的一些结果．     

利用矩阵的初等变换求方阵的特征值

高阶方阵的特征多项式以及特征值的求得,在计算上往往有一定的难度.本文首先从理论上分析了存在一个上三角矩阵或者下三角矩阵与一个方阵相似;接着,提出了相似变换的概念,分析了相似变换中初等矩阵的选择方法;然后指出了利用相似变换在求方阵的特征多项式以及特征值时的方法,并列举若干实例给予了说明.     

网络信息披露制度下XBRL金融数据的频繁模式并行挖掘

信息披露制度是上市公司为保障投资者利益、接受社会公众的监督而依照法律规定必须将其自身的财务变化、经营状况等信息向社会及监管部门公开或公告,以便投资者充分了解情况的制度.XBRL作为一种基于XML的可扩展性商业报告语言,目前已广泛应用于财务信息披露制度中,并逐渐成为了信息披露制度的标准数据格式.对XBRL的规范、分类、实例文档进行研究,基于MapReduce和HDFS提出可用于海量XBRL数据的频繁模式并行挖掘方法,基于我国上市公司的XBRL实例数据进行了实验,取得了良好的效果.     

复方阵的一种分解及应用

本文中我们证明了复方阵的一种分解的唯一性，并给出了这种唯一分解的几个应用。     

迹非零布尔矩阵幂敛指数的极阵刻画

设Ｄｎ（ｄ）是恰含ｄ个非零对角元的ｎ阶布矩阵的集合，１≤ｄ≤ｎ本文完全刻画了Ｄｎ（ｄ）中幂敛指数达到最大值的极矩阵，从而解决了迹非零尔矩阵幂敛指数的极阵刻问题。     

Convergence of Non-stationary Parallel Multisplitting Methods for Hermitian Positive Definite Matrices

Non-stationary multisplitting algorithms for the solution of linear systems are studied. Convergence of these algorithms is analyzed when the coefficient matrix of the linear system is hermitian positive definite. Asynchronous versions of these algorithms are considered and their convergence investigated.

     

反对角算子矩阵及其平方的(ω)性质的摄动

设H为复的无限维可分的Hilbert空间,B(H)为H上的有界线性算子的全体.若σ_a(T)\σ_(ea)(T)=π_(00)(T),则称T∈B(H)满足(ω)性质,其中σ_a(T)和σ_(ea)(T)分别表示算子T的逼近点谱和本质逼近点谱,π_(00)(T)={λ∈isoσ(T):0dimN(T-λI)∞}.T∈B(H)称为满足(ω)性质的摄动,若对任意的紧算子K,T+K满足(ω)性质.本文证明了反对角算子矩阵及其平方具有(ω)性质的摄动的等价性.     

On Parallel Fast Jacobi Algorithm for the Eigenproblem of Real Symmetric Matrices

Jacobi algorithm has been developed for the eigenproblem of real symmetric matrices, singular value decomposition of matrices and least squares of the overdetermined system on a parallel computer. In this paper, the parallel schemes and fast algorithm are discussed, and the error analysis and a new bound are presented.     

Efficient Pattern Matching on Graph Patterns of Bounded Treewidth

This paper deals with a problem to decide whether a given graph structure appears as a pattern in the structure of a given graph. A graph pattern is a connected graph with structured variables. A variable is an ordered list of vertices that can be replaced with a connected graph by a kind of hyperedge replacements. The graph pattern matching problem (GPMP) is the computational problem to decide whether a given graph pattern matches a given graph. In this paper, we show that GPMP is solvable in polynomial time if for a given graph pattern p, the lengths of all variables of p are 2 and the base graph of p is of bounded treewidth.     

布尔矩阵的振荡条件与振荡指数

首先将常用类型的模糊矩阵都纳入到了二阶占优模糊矩阵的统一框架之内,然后利用模糊矩阵的有向伴随图,指出了强连通布尔矩阵振荡的一个充要条件,依次证明了强连通的二阶占优布尔矩阵的振荡指数为2n-2,非强连通的二阶占优布尔矩阵的振荡指数为3n-4.     

Sparsity Inducing Prior Distributions for Correlation Matrices of Longitudinal Data

For longitudinal data, the modeling of a correlation matrix ?R can be a difficult statistical task due to both the positive definite and the unit diagonal constraints. Because the number of parameters increases quadratically in the dimension, it is often useful to consider a sparse parameterization. We introduce a pair of prior distributions on the set of correlation matrices for longitudinal data through the partial autocorrelations (PACs), which vary independently over (?1,1). The first prior shrinks each of the PACs toward zero with increasingly aggressive shrinkage in lag. The second prior (a selection prior) is a mixture of a zero point mass and a continuous component for each PAC, allowing for a sparse representation. The structure implied under our priors is readily interpretable for time-ordered responses because each zero PAC implies a conditional independence relationship in the distribution of the data. Selection priors on the PACs provide a computationally attractive alternative to selection on the elements of ?R or ?R^{? 1} for ordered data. These priors allow for data-dependent shrinkage/selection under an intuitive parameterization in an unconstrained setting. The proposed priors are compared to standard methods through a simulation study and illustrated using a multivariate probit data example. Supplemental materials for this article (appendix, data, and R code) are available online.     

On the Construction of Stability Indicators for Nonnegative Matrices

Mathematical Notes - Given a square nonnegative matrix $$A$$ , a simple algorithm is suggested for constructing a stability indicator characterizing the localization of its spectrum in the unit...     

双随机矩阵收敛指数的最好上界

Ｍ．Ｌｅｗｉｎ（１９７４）已得到了ｎ阶本原双随机矩阵收敛（本原）指数的最好上界。本文对不可约非本原和可约双随机矩阵的收敛指数作出估值，从而证明了Ｌｅｗｉｎ的上界是适用于一切双随机矩阵的最好上界。     

A Solution to a Problem on the Spectra of Sign Pattern Matrices

Mathematical Notes -