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

THE parallel complexity OF ABELIAN PERMUTATION GROUP PROBLEMS: 收藏
分享
引用; SIAM JOURNAL ON COMPUTING 1987年第5期16卷 880-909页; 作者： MCKENZIE, P COOK, SA UNIV TORONTO DEPT COMP SCI TORONTO M5S 1A4 ONTARIO CANADA; We classify Abelian permutation group problems with respect to their parallel complexity. For such groups specified by generating permutations we show that testing membership, computing order and testing isomorphism a... 详细信息; We classify Abelian permutation group problems with respect to their parallel complexity. For such groups specified by generating permutations we show that testing membership, computing order and testing isomorphism are $N C^{1}$; 关键词： 68Q permutation group Abelian group parallel complexity; 来源：评论; 学校读者我要写书评

暂无评论

parallel complexity OF DOMAIN DECOMPOSITION METHODS AND OPTIMAL COARSE GRID SIZE

parallel COMPUTING 1995年第7期21卷 1033-1049页

作者： CHAN, TF SHAO, JP UNIV KENTUCKY CTR COMPUTAT STUDIES LEXINGTON KY 40506 USA

In this paper, we analyze the parallel complexity of domain decomposition method through estimating the arithmetic time as well as the communication time. In most domain decomposition (DD) methods, a coarse grid solve is employed to provide global coupling and obtain an optimal convergence rate. Generally, a small coarse grid size H improves the convergence rate at the cost of a larger coarse grid problem and a large number P of processors results in more costly global communication, whereas a large H and a small P have the opposite effect. Therefore, there often exists an optimal H such that the execution time on the parallel machine reaches a minimum. Our main goal here is to find this optimal coarse grid size H in the parallel environment. We assume the same solver is used for the subdomains as well as the coarse problem. By expressing the parallel complexity as a function of H and h, we can derive the analytic optimal coarse grid size H-opt. When the number of processors is equal to the number of subdomains, we can prove that the choice of H,,, = root h asymptotically minimises the execution time as h tends to zero. This optimal coarse grid size is independent of the choice of subproblem solvers and the spatial dimension. However, when the number of processors is much less than the number of subdomains, the optimal coarse grid size depends on the number of processors, the subdomain solver and dimension.

关键词： COMPUTATION TIME ARITHMETIC TIME COMMUNICATION TIME parallel complexity EXECUTION TIME DOMAIN DECOMPOSITION OPTIMAL COARSE GRID SIZE CHOICE H

来源：评论

学校读者我要写书评

暂无评论

parallel complexity OF COMPUTING A MAXIMAL SET OF DISJOINT PATHS

引用

INFORMATION PROCESSING LETTERS 1992年第3期41卷 149-151页

作者： AGGARWAL, A IBM Res. Div. Thomas J. Watson Res. Cent. P.O. Box 218 Yorktown Heights NY 10598 USA

Given a graph, G = (V, E), and sets S subset-of V and Q subset-of V, the maximal paths problem requires the computation of a maximal set of vertex disjoint paths in G that begin at vertices of S and end at vertices of Q. It is well known that this problem can be solved sequentially in time that is proportional to the number of edges in G. However, its parallel complexity is not known. This note shows that this problem is NC-reducible to that of computing a depth-first search forest in a suitable n-vertex graph. This result can also be extended to directed graphs.

关键词： COMPUTATIONAL complexity MAXIMAL PATHS DEPTH-1ST SEARCH NC POLYLOGARITHMIC TIME parallel complexity DIRECTED GRAPHS PRAMS UNDIRECTED GRAPHS

来源：评论

学校读者我要写书评

暂无评论

parallel complexity of numerically accurate linear system solvers

引用

SIAM JOURNAL ON COMPUTING 1999年第6期28卷 2030-2058页

作者： Leoncini, M Manzini, G Margara, L Univ Pisa Dipartimento Informat I-56125 Pisa Italy CNR IMC I-56126 Pisa Italy Univ Piemonte Orientale Dipartimento Sci & Tecnol Avanzate I-15100 Alessandria Italy Univ Bologna Dipartimento Sci Informaz I-40127 Bologna Italy

We prove a number of negative results about practical (i.e., work efficient and numerically accurate) algorithms for computing the main matrix factorizations. In particular, we prove that the popular Householder and Givens methods for computing the QR decomposition are P-complete, and hence presumably inherently sequential, under both real and floating point number models. We also prove that Gaussian elimination (GE) with a weak form of pivoting, which aims only at making the resulting algorithm nondegenerate, is likely to be inherently sequential as well. Finally, we prove that GE with partial pivoting is P-complete over GF(2) or when restricted to symmetric positive definite matrices, for which it is known that even standard GE (no pivoting) does not fail. Altogether, the results of this paper give further formal support to the widespread belief that there is a tradeoff between parallelism and accuracy in numerical algorithms.

关键词： P-complete problems parallel complexity NC algorithms inherently sequential algorithms matrix factorization numerical stability

来源：评论

学校读者我要写书评

暂无评论

parallel complexity of matrix multiplication

引用

JOURNAL OF SUPERCOMPUTING 2003年第2期25卷 155-175页

作者： Santos, EE Virginia Polytech Inst & State Univ Dept Comp Sci Blacksburg VA 24061 USA

Effective design of parallel matrix multiplication algorithms relies on the consideration of many interdependent issues based on the underlying parallel machine or network upon which such algorithms will be implemented, as well as, the type of methodology utilized by an algorithm. In this paper, we determine the parallel complexity of multiplying two (not necessarily square) matrices on parallel distributed-memory machines and/or networks. In other words, we provided an achievable parallel run-time that can not be beaten by any algorithm (known or unknown) for solving this problem. In addition, any algorithm that claims to be optimal must attain this run-time. In order to obtain results that are general and useful throughout a span of machines, we base our results on the well-known LogP model. Furthermore, three important criteria must be considered in order to determine the running time of a parallel algorithm;namely, (i) local computational tasks, (ii) the initial data layout, and (iii) the communication schedule. We provide optimality results by first proving general lower bounds on parallel run-time. These lower bounds lead to significant insights on (i)-(iii) above. In particular, we present what types of data layouts and communication schedules are needed in order to obtain optimal run-times. We prove that no one data layout can achieve optimal running times for all cases. Instead, optimal layouts depend on the dimensions of each matrix, and on the number of processors. Lastly, optimal algorithms are provided.

关键词： parallel complexity matrix multiplication LogP model parallel algorithms lower bounds and optimality numerical algorithms linear algebra parallel models

来源：评论

学校读者我要写书评

暂无评论

parallel complexity of matrix multiplication

Parallel complexity of matrix multiplication

引用

International Conference on parallel and Distributed Processing Techniques and Applications (PDPTA 2001)

作者： Santos, EE Virginia Polytech Inst & State Univ Dept Comp Sci Blacksburg VA 24061 USA

关键词： parallel complexity matrix multiplication LogP model parallel algorithms lower bounds and optimality numerical algorithms linear algebra parallel models

来源：评论

学校读者我要写书评

暂无评论

Computing the graph-based parallel complexity of gene assembly

引用

THEORETICAL COMPUTER SCIENCE 2010年第25期411卷 2359-2367页

作者： Alhazov, Artiom Li, Chang Petre, Ion Acad Finland Helsinki Finland Abo Akad Univ Dept Informat Technol Turku Finland Moldavian Acad Sci Inst Math & Comp Sci MD-2028 Kishinev Moldova Turku Ctr Comp Sci FIN-20520 Turku Finland

We consider a graph-theoretical formalization of the process of gene assembly in ciliates introduced in Ehrenfeucht et al. (2003)[3], where a gene is modeled as a signed graph. The gene assembly, based on three types of operations only, is then modeled as a graph reduction process (to the empty graph). Motivated by the robustness of the gene assembly process, the notions of parallel reduction and parallel complexity of signed graphs have been considered in Harju et al. (2006)[7]. We describe in this paper an exact algorithm for computing the parallel complexity of a given signed graph and for finding an optimal parallel reduction for it. Checking the parallel applicability of a given set of operations and scanning all possible selections amount to a high computational complexity. We also briefly discuss a faster approximate algorithm that however, cannot guarantee finding the optimal reduction. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Gene assembly parallelism Signed graphs parallel complexity Algorithmics

来源：评论

学校读者我要写书评

暂无评论

The parallel complexity of signed graphs: Decidability results and an improved algorithm

引用

THEORETICAL COMPUTER SCIENCE 2009年第24-25期410卷 2308-2315页

作者： Alhazov, Artiom Petre, Ion Rogojin, Vladimir Turku Ctr Comp Sci FIN-20520 Turku Finland Abo Akad Univ Dept Informat Technol Turku Finland Moldavian Acad Sci Inst Math & Comp Sci MD-2028 Kishinev Moldova

We consider a graph-based model for the process of gene assembly in ciliates, as proposed in [A. Ehrenfeucht, T. Harju, I. Petre, D. M. Prescott, G. Rozenberg, Computation in Living Cells: Gene Assembly in Ciliates, Springer, 2003]. The model consists of three operations, each reducing the order of the signed graph. Reducing the graph to the empty graph through a sequence of operations corresponds to assembling a gene. We investigate parallel reductions of a given signed graph, where the graph is reduced through a sequence of parallel steps. A parallel step consists of operations such that any of their sequential compositions are applicable to the current graph. We improve the basic exhaustive search algorithm reported in [A. Alhazov, C. Li, I. Petre, Computing the graph-based parallel complexity of gene assembly, Theoretical Computer Science, 2008 (in press)] to compute the parallel complexity of signed graphs. On the one hand, we reduce the number of sets of operations which should be checked for parallel applicability. On the other hand, we speed up the parallel applicability check procedure. We prove also that deciding whether a given parallel composition of operations is applicable to a given signed graph is a coNP problem. Deciding whether the parallel complexity (the length of a shortest parallel reduction) of a signed graph is bounded by a given constant is in NPNP. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Ciliates parallel gene assembly parallel complexity Signed graphs Algorithm Decidability

来源：评论

学校读者我要写书评

暂无评论

EXPRESSIBILITY AND parallel complexity

引用

SIAM JOURNAL ON COMPUTING 1989年第3期18卷 625-638页

作者： IMMERMAN, N Yale Univ CT United States

It is shown that the time needed by a concurrent-read, concurrent-write parallel random access machine (CRAM) to check if an input has a certain property is the same as the minimal depth of a first-order inductive definition of the property. This in turn is equal to the number of “iterations” of a first-order sentence needed to express the property.

关键词： 68025 computational complexity parallel complexity first-order expressibility polynomial-time hierarchy

来源：评论

学校读者我要写书评

暂无评论

BOOLEAN FUNCTIONS, INVARIANCE-GROUPS, AND parallel complexity

引用

SIAM JOURNAL ON COMPUTING 1991年第3期20卷 553-590页

作者： CLOTE, P KRANAKIS, E UNIV PARIS 07 EQUIPE LOG MATH CNRS UA 753 F-75221 PARIS 05 FRANCE CTR WISKUNDE & INFORMAT 1009 AB AMSTERDAM NETHERLANDS

This paper studies the invariance groups S(f) of boolean functions f member-of B(n) (i.e., f:{0,1}n --> {0,1}) on n variables, i.e., the set of all permutations on n elements which leave f invariant. After building intuition by presenting several examples that suggest relations between algebraic properties of groups and computational complexity of languages, necessary and sufficient conditions are given via Polya's cycle index for an arbitrary finite permutation group to be of the form S(f), for some f member-of B(n). It is shown that asymptotically "almost all" boolean functions have trivial invariance groups. For cyclic groups G less-than-or-equal-to S(n) a logspace algorithm for determining whether the given group is of the form S(f), for some f member-of B(n) is given. The applicability of group theoretic techniques in the study of the parallel complexity of languages is demonstrated. For any language L let L(n) be the characteristic function of the set of all strings in L which have length exactly n and let S(n)(L) be the invariance group of L(n). The index \S(n):S(n)(L)\ are considered as a function of n and the class of languages whose index is polynomial in n is studied. Bochert's lower bound on the index of primitive permutation groups is used together with the O'Nan-Scott theorem, a deep result in the classification of finite simple groups, in order to show that any language with polynomial index is in (nonuniform) TC0 and hence in (nonuniform) NC1. As a corollary, an extension is given of a result of Fagin-Klawe-Pippenger-Stockmeyer, giving necessary and sufficient conditions for a language with polynomial index to be computable by a constant depth polynomial size circuit family. As another corollary, it is shown that the problem of "weight-swapping" for a sequence of groups of polynomial index is in (nonuniform) NC1.

关键词： ABELIAN GROUP BOOLEAN FUNCTION CIRCUIT CLASSIFICATION THEORY CYCLIC GROUPS DIHEDRAL GROUPS HYPEROCATAHEDRAL-GROUPS INDEX OF A GROUP INVARIANCE GROUP OF BOOLEAN FUNCTION NC parallel complexity PERMUTATION GROUP POLYA CYCLE INDEX PUMPING LEMMA REPRESENTABLE GROUP REGULAR LANGUAGE SYMMETRICAL BOOLEAN FUNCTION WREATH PRODUCT

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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