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

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

来源：评论

学校读者我要写书评

暂无评论

On the computational complexity of graph closures

引用

INFORMATION PROCESSING LETTERS 1996年第6期57卷 291-295页

作者： Monti, A Dipartimento di Scienze dellInformazione Universit&agrave degli studi di Roma (La Sapienza) Via Salaria 113 00198 Roma Italy

This paper resolves the parallel complexity of the graph closure problem, an open question posed by S. Khuller. In particular, we prove that the 2N - k-closure problem is in L for k = 5 and it is P-complete for k grea... 详细信息

关键词： computational complexity graph closure parallel complexity P-completeness

来源：评论

学校读者我要写书评

暂无评论

LOWER BOUNDS FOR ARITHMETIC-NETWORKS

引用

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING 1993年第1期4卷 1-24页

作者： MONTANA, JL PARDO, LM UNIV CANTABRIA FAC CIENCIASDEPT MATEMAT ESTADIST & COMPUTACE-39071 SANTANDERSPAIN

We show lower bounds for depth of arithmetic networks over algebraically closed fields, real closed fields and the field of the rationals. The parameters used are either the degree or the number of connected components. These lower bounds allow us to show the inefficiency of arithmetic networks to parallelize several natural problems. For instance, we show a square-root n lower bound for parallel time of the Knapsack problem over the reals and also that the computation of the ''integer part'' is not well parallelizable by arithmetic networks. Over the rationals we obtain results of similar order and that the Knapsack has an square root n lower bound for the parallel time measured by networks. A simply exponential lower bound for the parallel time of quantifier elimination is also shown. Finally, separations among classes P(K) and NC(K) are available for fields K in the above cases.

关键词： parallel complexity ALGEBRAIC complexity THEORY ARITHMETIC NETWORKS CONSTRUCTIBLE AND SEMIALGEBRAIC SETS DEGREE AND CONNECTED COMPONENTS

来源：评论

学校读者我要写书评

暂无评论

Optimal and efficient parallel tridiagonal solvers using direct methods

引用

JOURNAL OF SUPERCOMPUTING 2004年第2期30卷 97-115页

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

The problem of solving tridiagonal linear systems on parallel distributed-memory environments is considered in this paper. In particular, two common direct methods for solving such systems are considered: odd-even cyclic reduction and prefix summing. For each method, a variety of lower bounds on execution time for solving tridiagonal linear systems are presented. Specifically, lower bounds are presented that (a) hold when the number of data items per processor is bounded, (b) are general lower bounds, and (c) for specific data layouts commonly used in designing parallel algorithms to solve tridiagonal linear systems. Furthermore, algorithms are presented that have running times within a constant factor of the lower bounds provided. Lastly, a comparison of bounds for odd-even cyclic reduction and prefix summing is given.

关键词： tridiagonal solvers parallel algorithms parallel complexity direct methods LogP model linear algebra

来源：评论

学校读者我要写书评

暂无评论

LIMITS ON parallelISM IN THE NUMERICAL-SOLUTION OF LINEAR PARTIAL-DIFFERENTIAL EQUATIONS

引用

SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING 1991年第1期12卷 1-35页

作者： WORLEY, PH

The problem considered is that of approximating the solution of a linear scalar partial differential equation (PDE) at one or more locations in its domain. A lower bound on the amount of data required to satisfy a given error tolerance in the approximation is described. Using this bound, a lower bound on the execution time of parallel algorithms that approximate the solution is derived. The lower bound on the execution time has the form alpha.f(+).log2-epsilon-1, where alpha is a problem-dependent constant, f(+) is a measure of the speed of floating point arithmetic, and epsilon is an upper bound on the error. Thus, when alpha > 0, the execution time increases as epsilon decreases, independent of the number of processors, the interconnection topology, and the algorithm used. Lower bounds on the execution time are also given for the cases where the interconnection network or the number of processors is specified. Recent research has established that it is often possible to use a large number of processors efficiently when calculating the numerical solution of a PDE if the problem is sufficiently large. In this paper, it is shown that increasing the size of such a problem will usually come at the cost of increasing the execution time. Two examples are described that verify this conclusion, an algorithm-independent analysis of an elliptic PDE and an analysis of a specific algorithm for the approximation of a hyperbolic PDE.

关键词： LIMITS ON parallelISM ALGORITHM-INDEPENDENT complexity BOUNDS LINEAR PARTIAL DIFFERENTIAL EQUATIONS NUMERICAL APPROXIMATION parallel complexity parallel EXECUTION TIME PROBLEM SCALING

来源：评论

学校读者我要写书评

暂无评论

The orbit problem is in the GapL hierarchy

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2011年第1期21卷 124-137页

作者： Arvind, V. Vijayaraghavan, T. C. Inst Math Sci Madras 600113 Tamil Nadu India Chennai Math Inst Siruseri 603103 India

The Orbit problem is defined as follows: Given a matrix A is an element of Q(nxn) and vectors x, y is an element of Q(n), does there exist a non-negative integer i such that A(i)x = y. This problem was shown to be in deterministic polynomial time by Kannan and Lipton (J. ACM 33(4): 808-821, 1986). In this paper we place the problem in the logspace counting hierarchy GapLH. We also show that the problem is hard for C(=)L with respect to logspace many-one reductions.

关键词： Orbit problem Linear algebra parallel complexity Logspace counting classes parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Athapascan-1: On-line building data flow graph in a parallel language

Athapascan-1: On-line building data flow graph in a parallel...

引用

International Conference on parallel Architectures and Compilation Techniques

作者： Galilee, F Roch, JL Cavalheiro, GGH Doreille, M IMAG LMC APACHE Project Grenoble France

ISBN: (纸本)0818685913

In order to achieve practical efficient execution on a parallel architecture, a knowledge of the data dependencies related to the application appears as the key point for building an efficient schedule. By restricting accesses in shared memory, we show that such a data dependency graph can be computed on-line on a distribute architecture. The overhead introduced is bounded with respect to the parallelism expressed by the user: each basic computation corresponds to a user-defined task;each data-dependency to a user-defined data structure. We introduce a language named Athapascan-1 that allows built a graph of dependencies from a strong typing of shared memory accesses. We detail compilation and implementation of the language. Besides, the performance of a code (parallel time, communication and arithmetic works, memory space) are defined from a cost model without the need of a machine model. We exhibit efficient scheduling with respect to these costs art theoretical machine models.

关键词： multithreading macro-data flow languages on-line scheduling parallel complexity

来源：评论

学校读者我要写书评

暂无评论

引用

Electronic Notes in Discrete Mathematics 2011年第C期37卷 135-140页

作者： Sedjelmaci, Sidi Mohamed LIPN CNRS UMR 7030 Université Paris-Nord 93430 Villetaneuse Av. J.-B. Clément France

We generalize a formula of B. Litow [parallel complexity of Integer Coprimality, in Electronic Colloquium on Computational complexity, Report No. 9, 1998.] and propose several new formula linked with the parallel Integer Coprimality, Integer GCD and Modular Inverse problems as well. Particularly, we find a new trigonometrical definition of the GCD of two integers a, b ≥ 1 : We also suggest a generalization of the GCD function to real numbers. © 2011 Elsevier B.V.

关键词： Algorithms Greatest common divisor (GCD) parallel complexity

来源：评论

学校读者我要写书评

暂无评论

The Mixed Binary Euclid Algorithm

引用

Electronic Notes in Discrete Mathematics 2009年第C期35卷 169-176页

作者： Sedjelmaci, Sidi Mohamed LIPN CNRS UMR 7030 Université Paris-Nord 93430 Villetaneuse Av. J.-B. Clément France

We present a new GCD algorithm for two integers that combines both the Euclidean and the binary gcd approaches. We give its worst case time analysis and we prove that its bit-time complexity is still O (n²) for two n-bit integers in the worst case. Our preliminar experiments show a potential speedup for small integers. A parallel version matches the best presently known time complexity, namely O (n / log n) time with O (n^{1 + ε{lunate}}) processors, for any constant ε{lunate} > 0. © 2009 Elsevier B.V. All rights reserved.

关键词： Algorithms Greatest common divisor (GCD) parallel complexity

来源：评论

学校读者我要写书评

暂无评论

parallel models of computation: an introductory survey

引用

Calcolo 1989年第2-4期26卷 209-236页

作者： Leoncini, M. Istituto per la Matematica Applicata Genova 16132 Via L. B. Alberti 4 Italy

The paper gives an overview of some models of computation which have proved successful in laying a foundation for a general theory of parallel computation. We present three models of parallel computation, namely boolean and arithmetic circuit families, and parallel Random Access Machines. They represent different viewpoints on parallel computing: boolean circuit families are useful for in-depth theoretical studies on the power and limitations of parallel computers;parallel Random Access Machines are the most general vehicles for designing highly parallel algorithms;arithmetic circuit families are an important tool for undertaking studies related to one of the most active areas in parallel computing, i.e. parallel algebraic complexity. © 1989 Instituto di Elaborazione della Informazione del CNR.

关键词： General model parallel complexity Structured model

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：