检索结果-内蒙古大学图书馆

Bounded size dictionary compression:: SC^k-completeness and NC algorithms

INFORMATION AND COMPUTATION 2003年第2期180卷 101-112页

作者： De Agostino, S Silvestri, R Armstrong Atlantic State Univ Dept Comp Sci Savannah GA 31419 USA Univ Roma La Sapienza Dipartimento Sci Informaz I-00135 Rome Italy

We study the parallel complexity of a bounded size dictionary version (LRU deletion heuristic) of the LZ2 compression algorithm. The unbounded version was shown to be P-complete. When the size of the dictionary is O(Iog(k)n), the problem of computing the LZ2 compression is shown to be hard for the class of problems solvable simultaneously in polynomial time and O(Iog(k) n) space (that is, SCk). We also introduce a variation of this heuristic that turns out to be an SCk-complete problem (the original heuristic belongs to SCk+1). In virtue of these results, we argue that there are no practical parallel algorithms for LZ2 compression with LRU deletion heuristic or any other heuristic deleting dictionary elements in a continuous way. For simpler heuristics (SWAP, RESTART, FREEZE), practical parallel algorithms are given. (C) 2002 Elsevier Science (USA). All rights reserved.

关键词： parallel complexity NC algorithms SCk-completeness data compression dictionary algorithms

来源：评论

学校读者我要写书评

暂无评论

Lower bounds for arithmetic networks .2. Sum of Betti numbers

引用

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING 1996年第1期7卷 41-51页

作者： Montana, JL Morais, JE Pardo, LM UNIV CANTABRIA FAC CIENCIAS DEPT MATEMAT ESTADIST & COMPUTAC E-39071 SANTANDER SPAIN UNIV PUBL NAVARRA DEPT MATEMAT & INFORMAT E-31006 PAMPLONA NAVARRA SPAIN

We show lower bounds for the parallel complexity of membership problems in semialgebraic sets. Our lower bounds are obtained from the Euler characteristic and the sum of Betti numbers. We remark that these lower bound... 详细信息

关键词： parallel complexity algebraic complexity theory arithmetic networks semi-algebraic sets Borel-Moore homology

来源：评论

学校读者我要写书评

暂无评论

Distributed query evaluation on semistructured data

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2002年第1期27卷 1-62页

作者： Suciu, D Univ Washington Dept Comp Sci & Engn Seattle WA 98195 USA AT&T Corp Shannon Labs New York NY 10013 USA

Semistructured data is modeled as a rooted, labeled graph. The simplest kinds of queries on such data are those which traverse paths described by regular path expressions. More complex queries combine several regular path expressions, with complex data restructuring, and with sub-queries. This article addresses the problem of efficient query evaluation on distributed, semistructured databases. In our setting, the nodes of the database are distributed over a fixed number of sites, and the edges are classified into local (with both ends in the same site) and cross edges (with ends in two distinct sites). Efficient evaluation in this context means that the number of communication steps is fixed (independent on the data or the query), and that the total amount of data sent depends only on the number of cross links and of the size of the query's result. We give such algorithms in three different settings. First, for the simple case of queries consisting of a single regular expression;second, for all queries in a calculus for graphs based on structural recursion which in addition to regular path expressions can perform nontrivial restructuring of the graph;and third, for a class of queries we call select-where queries that combine pattern matching and regular path expressions with data restructuring and subqueries. This article also includes a discussion on how these methods can be used to derive efficient view maintenance algorithms.

关键词： algorithm languages theory distributed evaluation nested queries parallel complexity regular expressions semistructured data

来源：评论

学校读者我要写书评

暂无评论

FAST AND EFFICIENT parallel SOLUTION OF SPARSE LINEAR-SYSTEMS

引用

SIAM JOURNAL ON COMPUTING 1993年第6期22卷 1227-1250页

作者： PAN, V REIF, J SUNY ALBANY DEPT COMP SCI ALBANY NY 12222 USA DUKE UNIV DEPT COMP SCI DURHAM NC 27706 USA

This paper presents a parallel algorithm for the solution of a linear system Ax = b with a sparse n x rr symmetric positive definite matrix A, associated with the graph G(A) that has rr vertices and has an edge for each nonzero entry of A. If G(A) has an s(n)-separator family and a known s(n)-separator tree, then the algorithm requires only O(log(3) n) time and (\E\ + M(s(n)))/log n processors for the evaluation of the solution vector x = A (-1)b, where \E\ is the number of edges in G(A) and M(n) is the number of processors sufficient for multiplying two n x n rational matrices in time O(log n). Furthermore, for this computational cost the algorithm computes a recursive factorization of A such that the solution of any other linear system Ax = b' with the same matrix A requires only O(log(2)n) time and (\E\/logn) + s(n)(2) processors.

关键词： parallel ALGORITHMS SPARSE LINEAR SYSTEMS NESTED DISSECTION parallel complexity GRAPH SEPARATORS

来源：评论

学校读者我要写书评

暂无评论

REVERSAL complexity

引用

SIAM JOURNAL ON COMPUTING 1991年第4期20卷 622-638页

作者： CHEN, JE YAP, CK New York Univ New York NY United States

The importance of reversal complexity as a basic computational resource has only been recognized in recent years. It is intimately connected to parallel time complexity and circuit depth. In this paper, some basic techniques necessary for establishing analogues of well-known theorems on space and time complexity are developed. The main results are, for reversal-constructible functions s(n) greater-than-or-equal-to log n, DSPACE(s(n)) subset-or-is-equal-to DREVERSAL(s(n)), and a tape reduction theorem. As applications of the tape reduction theorem, a hierarchy theorem is proved and the existence of complete languages for reversal complexity is shown.

关键词： REVERSAL SPACE TAPE REDUCTION THEOREM REVERSAL HIERARCHIES COMPLETE LANGUAGES parallel complexity

来源：评论

学校读者我要写书评

暂无评论

Division in logspace-uniform NC

引用

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS 2001年第3期35卷 259-275页

作者： Chiu, A Davida, G Litow, B Univ Wisconsin Dept EECS Milwaukee WI 53201 USA James Cook Univ N Queensland Sch Informat Technol Townsville Qld 4811 Australia

Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, i.e., NC1 circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform NC1.

关键词： parallel complexity NC integer division uniformity

来源：评论

学校读者我要写书评

暂无评论

A NOTE ON STRATEGY ELIMINATION IN BIMATRIX GAMES

引用

OPERATIONS RESEARCH LETTERS 1988年第3期7卷 103-107页

作者： KNUTH, DE PAPADIMITRIOU, CH TSITSIKLIS, JN UNIV CALIF SAN DIEGO DEPT COMP SCI & ENGNSAN DIEGOCA 92103 MIT DEPT ELECT ENGN & COMP SCICAMBRIDGEMA 02139

In bimatrix games we study the process of successively eliminating strategies which are dominated by other pure strategies. We show how to perform this simplification in O( n 3 ) time, where n is the number of strateg... 详细信息

关键词： game theory strategy domination algorithms parallel complexity matrix multiplication P-completeness

来源：评论

学校读者我要写书评

暂无评论

A NEW APPROACH TO STABLE MATCHING PROBLEMS

引用

SIAM JOURNAL ON COMPUTING 1994年第4期23卷 671-700页

作者： SUBRAMANIAN, A STANFORD UNIV DEPT COMP SCISTANFORDCA 94305

It is shown that Stable Matching problems are the same as problems about stable configurations of X-networks. Consequences include easy proofs of old theorems, a new simple algorithm for finding a stable matching, an understanding of the difference between Stable Marriage and Stable Roommates, NP-completeness of Three-party Stable Marriage, CC-completeness of several Stable Matching problems, and a fast parallel reduction from the Stable Marriage problem to the Assignment problem.

关键词： STABLE MATCHING STABLE MARRIAGE STABLE ROOMMATES STABLE CONFIGURATION CIRCUIT VALUE NETWORK STABILITY parallel complexity COMPARATOR CC SCATTER ASSIGNMENT PROBLEM WEIGHTED MATCHING

来源：评论

学校读者我要写书评

暂无评论

Sampling chaotic trajectories quickly in parallel

引用

JOURNAL OF STATISTICAL PHYSICS 2002年第3-4期109卷 863-873页

作者： Machta, J Univ Massachusetts Dept Phys Amherst MA 01003 USA

The parallel computational complexity of the quadratic map is studied. A parallel algorithm is described that generates typical pseudotrajectories of length t in a time that scales as log t and increases slowly in the accuracy demanded of the pseudotrajectory. Long pseudotrajectories are created in parallel by putting together many short pseudotrajectories;Monte Carlo procedures are used to eliminate the discontinuities between these short pseudotrajectories and then suitably randomize the resulting long pseudotrajectory. Numerical simulations are presented that show the scaling properties of the parallel algorithm. The existence of the fast parallel algorithm provides a way to formalize the intuitive notion that chaotic systems do not generate complex histories.

关键词： chaotic dynamics parallel complexity quadratic map path sampling

来源：评论

学校读者我要写书评

暂无评论

Fast rectangular matrix multiplication and applications

引用

JOURNAL OF complexity 1998年第2期14卷 257-299页

作者： Huang, XH Pan, VY CUNY Grad Sch & Univ Ctr Program Math New York NY 10036 USA CUNY Herbert H Lehman Coll Dept Math & Comp Sci Bronx NY 10468 USA

First we study asymptotically fast algorithms for rectangular matrix multiplication. We begin with new algorithms for multiplication of an n x n matrix by an n x n(2) matrix in arithmetic time O(n(omega)), omega = 3.333953..., which is less by 0.041 than the previous record 3.375477.... Then we present fast multiplication algorithms for matrix pairs of arbitrary dimensions, estimate the asymptotic running time as a function of the dimensions, and optimize the exponents of the complexity estimates. For a large class of input matrix pairs, we improve the known exponents. Finally we show three applications of our results: (a) we decrease from 2.851 to 2.837 the known exponent of *** bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n x n matrix, as well as for the solution to a nonsingular linear system of n equations, (b) we asymptotically accelerate the known sequential algorithms for the univariate polynomial composition mod x(n), yielding the complexity bound O(n(1.667)) versus the old record of O(n(1.688)), and for the univariate polynomial factorization over a finite field, and (c) we improve slightly the known complexity estimates for computing basic solutions to the linear programming problem with n constraints and n variables. (C) 1998 Academic Press.

关键词： rectangular matrix multiplication asymptotic arithmetic complexity bilinear algorithms parallel complexity polynomial composition polynomial factorization over finite fields linear programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：