Strategies for Computing Minimal Free Resolutions

In the present paper we study algorithms based on the theory of Gröbner bases for computing free resolutions of modules over polynomial rings. We propose a technique which consists in the application of special selection strategies to the Schreyer algorithm. The resulting algorithm is efficient and, in the graded case, allows a straightforward minimalization algorithm. These techniques generalize to factor rings, skew commutative rings, and some non-commutative rings. Finally, the proposed approach is compared with other algorithms by means of an implementation developed in the new system Macaulay2.     

Computing Betti Numbers via Combinatorial Laplacians

We use the Laplacian and power method to compute Betti numbers of simplicial complexes. This has a number of advantages over other methods, both in theory and in practice. It requires small storage space in many cases. It seems to run quickly in practice, but its running time depends on a ratio, ν , of eigenvalues which we have yet to understand fully. We numerically verify a conjecture of Bj{?}rner, Lov{á}sz, Vre{\'c}ica, and {\u Z}ivaljevi{\'c} on the chessboard complexes C(4,6) , C(5,7) , and C(5,8) . Our verification suffers a technical weakness, which can be overcome in various ways; we do so for C(4,6) and C(5,8) , giving a completely rigorous (computer) proof of the conjecture in these two cases. This brings up an interesting question in recovering an integral basis from a real basis of vectors. Received November 23, 1995; revised December 7, 1996.     

基于最小PC构架的可配置计算平台及应用

在机器视觉、军事、航空照相等领域需要在有限的空间内设计出小型化、灵活的、能够完成图像处理功能的系统。文中设计了一种以裁剪了的PC1 0 4构架为基础的可配置计算平台 ,该系统的PCB电路板面积只有 90mm× 6 8mm。以一个目标识别图像处理应用系统为例 ,给出了图像协处理器的7个乘法器并行、7级流水的内部结构设计方案。能够实现任意小于 7× 7模板的 2维图像卷积处理算法 ,获得了较高的图像处理性能     

Computing the Map of Geometric Minimal Cuts

In this paper we consider the following problem of computing a map of geometric minimal cuts (called MGMC problem): Given a graph G=(V,E) and a planar rectilinear embedding of a subgraph H=(V _H ,E _H ) of G, compute the map of geometric minimal cuts induced by axis-aligned rectangles in the embedding plane. The MGMC problem is motivated by the critical area extraction problem in VLSI designs and finds applications in several other fields. In this paper, we propose a novel approach based on a mix of geometric and graph algorithm techniques for the MGMC problem. Our approach first shows that unlike the classic min-cut problem on graphs, the number of all rectilinear geometric minimal cuts is bounded by a low polynomial, O(n ³). Our algorithm for identifying geometric minimal cuts runs in O(n ³logn(loglogn)³) expected time which can be reduced to O(nlogn(loglogn)³) when the maximum size of the cut is bounded by a constant, where n=|V _H |. Once geometric minimal cuts are identified we show that the problem can be reduced to computing the L _∞ Hausdorff Voronoi diagram of axis aligned rectangles. We present the first output-sensitive algorithm to compute this diagram which runs in O((N+K)log² NloglogN) time and O(Nlog² N) space, where N is the number of rectangles and K is the complexity of the Hausdorff Voronoi diagram. Our approach settles several open problems regarding the MGMC problem.     

Learning Local Transductions Is Hard

Local deterministic string-to-string transductions arise in natural language processing (NLP) tasks such as letter-to-sound translation or pronunciation modeling. This class of transductions is a simple generalization of morphisms of free monoids; learning local transductions is essentially the same as inference of certain monoid morphisms. However, learning even a highly restricted class of morphisms, the so-called fine morphisms, leads to intractable problems: deciding whether a hypothesized fine morphism is consistent with observations is an NP-complete problem; and maximizing classification accuracy of the even smaller class of alphabetic substitution morphisms is APX-hard. These theoretical results provide some justification for using the kinds of heuristics that are commonly used for this learning task.     

Computing in the Field of Complex Algebraic Numbers

In this paper we present two methods of computing with complex algebraic numbers. The first uses isolating rectangles to distinguish between the roots of the minimal polynomial, the second method uses validated numeric approximations. We present algorithms for arithmetic and for solving polynomial equations, and compare implementations of both methods inMathematica.     

一种快速生成最小浓缩数据立方的算法

语义OLAP技术是近来学者研究的热点之一,浓缩数据立方就是其中一种.本文设计了一个用于快速生成最小浓缩数据立方的算法SQCube.算法分两个阶段：首先利用BottomUpBST算法生成一个非最小的浓缩数据立方,然后对所得到的非最小浓缩数据立方进行后处理,把其中的所有纯BST和隐BST压缩为一条BST,从而生成一个最小浓缩数据立方.实验表明SQCube算法明显优于以往提出的同类算法MinCube.     

Computing Only Minimal Answers in Disjunctive Deductive Databases

A method is presented for computing minimal answers of the form in disjunctive deductive databases under the disjunctive stable model semantics. Such answers are constructed by repeatedly extending partial answers. Our method is complete (in that every minimal answer can be computed) and does not admit redundancy (in the sense that every partial answer generated can be extended to a minimal answer), thus no non-minimal answer is generated. The method does not (necessarily) require the computation of models of the database in their entirety. A partitioning of the database into extensional and intensional components is employed in order to overcome the problems caused by the possible non-existence of disjunctive stable models, and a form of compilation is presented as a means of simplifying and improving the efficiency of the run-time computation, which then reduces to relatively trivial processing within the extensional database. In addition, the output from this compilation process has the significant advantage of being immune to updates to the extensional database. Other forms of database pre-processing are also considered, and three transformations are presented mapping a database onto an equivalent positive database, non-disjunctive database, and set of conditional facts.     

The Complexity of Computing Minimal Unidirectional Covering Sets

A common thread in the social sciences is to identify sets of alternatives that satisfy certain notions of stability according to some binary dominance relation. Examples can be found in areas as diverse as voting theory, game theory, and argumentation theory. Brandt and Fischer (in Math. Soc. Sci. 56(2):254–268, 2008) proved that it is NP-hard to decide whether an alternative is contained in some inclusion-minimal unidirectional (i.e., either upward or downward) covering set. For both problems, we raise this lower bound to the $\varTheta_{2}^{p}$ level of the polynomial hierarchy and provide a $\varSigma_{2}^{p}$ upper bound. Relatedly, we show that a variety of other natural problems regarding minimal or minimum-size unidirectional covering sets are hard or complete for either of NP, coNP, and  $\varTheta_{2}^{p}$ . An important consequence of our results is that neither minimal upward nor minimal downward covering sets (even when guaranteed to exist) can be computed in polynomial time unless P=NP. This sharply contrasts with Brandt and Fischer’s result that minimal bidirectional covering sets are polynomial-time computable.     

Algorithms for Computing Minimal Unsatisfiable Subsets of Constraints

Much research in the area of constraint processing has recently been focused on extracting small unsatisfiable “cores” from unsatisfiable constraint systems with the goal of finding minimal unsatisfiable subsets (MUSes). While most techniques have provided ways to find an approximation of an MUS (not necessarily minimal), we have developed a sound and complete algorithm for producing all MUSes of an unsatisfiable constraint system. In this paper, we describe a relationship between satisfiable and unsatisfiable subsets of constraints that we subsequently use as the foundation for MUS extraction algorithms, implemented for Boolean satisfiability constraints. The algorithms provide a framework with which many related subproblems can be solved, including relaxations of completeness to handle intractable instances, and we develop several variations of the basic algorithms to illustrate this. Experimental results demonstrate the performance of our algorithms, showing how the base algorithms run quickly on many instances, while the variations are valuable for producing results on instances whose complete results are intractably large. Furthermore, our algorithms are shown to perform better than the existing algorithms for solving either of the two distinct phases of our approach.     

Hard Data Is Good to Find

Indices are a common and useful way to summarize a changing field for both the lay and the specialist reader, and it's time that we had them for information security.     

Maximum Cardinality Search for Computing Minimal Triangulations of Graphs

We present a new algorithm, called MCS-M, for computing minimal triangulations of graphs. Lex-BFS, a seminal algorithm for recognizing chordal graphs, was the genesis for two other classical algorithms: LEX M and MCS. LEX M extends the fundamental concept used in Lex-BFS, resulting in an algorithm that not only recognizes chordality, but also computes a minimal triangulation of an arbitrary graph. MCS simplifies the fundamental concept used in Lex-BFS, resulting in a simpler algorithm for recognizing chordal graphs. The new algorithm MCS-M combines the extension of LEX M with the simplification of MCS, achieving all the results of LEX M in the same time complexity.     

A Good Oracle Is Hard to Beat

A well-known result of Sacks [24] states that if A is nonrecursive, then the set {B : A ≤ _T B} has measure zero. Thus, from a measure-theoretic perspective, a ``good' (i.e., nonrecursive) oracle is hard to beat in the partial order of Turing degrees. We show that analogous results hold for the standard notions of inductive inference, as well as for the notions of approximate inference. Received January 25, 1997; revised March 10, 1997, June 3, 1997, and June 15, 1997.     

在基于模型诊断中计算最小碰集算法

介绍了基于模型诊断中的计算碰集的算法 ,并分析比较了各算法的效率和计算结果。其中的逻辑型数组算法、递归算法、BHS 树算法、布尔代数算法、GA算法均是笔者近年来研究的结果。     

基于动态极大度的极小碰集求解方法

在计算集合簇的碰集时,结合SE-Tree(set enumeration tree)形式化地表达计算过程,逐步生成所有的极小碰集.并在SE-Tree中添加了终止结点,避免了非极小碰集的产生,并且不会因剪枝而丢失正确的解.提出未扩展元素度的概念和结点度的概念,进而在扩展SE-Tree结点时按照未扩展元素度由大到小的顺序扩展,极早地生成集合簇的碰集,减少枚举树生成的结点个数,并且直接根据结点度得出结点对应的集合是否为集合簇的碰集,避免计算集合是否为集合簇的碰集.实验结果表明,该算法程序容易编制且效率较好.     

协同创新是下一个计算时代湘召开算时代

"中南大学-英特尔透明计算与平台创新技术研讨会"在湘召开 "中南大学—英特尔透明计算与平台创新技术研讨会"在湖南长沙举行。作为"产、学、研、用"各界进行技术和业务交流的平台,众多国内外专家、学者、业界技术专家、政府部门的领导出席了研讨会,深入交流了透明计算与云计算等平台新技术及应用成果。在2012年9月的英特尔信息技术峰会美国站上英特尔公司高级副总裁、软件与服务事业部总经理詹睿妮女士(Ms.RenéeJames)在主题演讲中给透明计算极高的评价,认为"透明计算将是下一个计算时代,其三     

Computing a Set of Generators of Minimal Cardinality in a Solvable Group

In this paper two algorithms are presented which compute a set of generators of minimal cardinality for a finite soluble group given by a polycyclic presentation. The first can be used when a chief series is available. The second algorithm is less simple, but nevertheless efficient, and can be used when it is difficult or too expensive to compute a chief series. The problem of determining the minimal number d(G) of generators when G is a solvable group has been discussed and solved by Gaschütz, and the ideas for these algorithms are essentially suggested by the work of Gaschütz. In the Appendices CAYLEY V.3.7.2 procedures are listed.     

Approximating the Minimum Length of Synchronizing Words Is Hard

We prove that, unless P=NP, no polynomial-time algorithm can approximate the minimum length of reset words for a given synchronizing automaton within a constant factor.     

Architectural Mismatch: Why Reuse Is Still So Hard

In this article, David Garlan, Robert Allen, and John Ockerbloom reflect on the state of architectural mismatch, a term they coined in their 1995 IEEE Software article, "Architectural Mismatch: Why Reuse Is So Hard." Although the nature of software systems has changed dramatically since the earlier article was published, the challenge of architectural mismatch remains an important concern for the software engineering field.