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

ISRAEL SYMP ON THE THEORY OF COMPUTING AND SYSTEMS

作者： SADE, I AVERBUCH, A Department of Computer Science School of Mathematical Sciences Tel Aviv University Tel Aviv 69978 Israel

We consider the problem of fast parallel evaluation of multivariate polynomials over a field F. We define “maximal-degree” (maxdeg) of a multivariate polynomial f as maxi degxi(f(xi,⋯,xn)) i=1,⋯, n. The first lower ... 详细信息

ISBN: (纸本)3540555536

We consider the problem of fast parallel evaluation of multivariate polynomials over a field F. We define “maximal-degree” (max_deg) of a multivariate polynomial f as max_i deg_xi(f(x_i,⋯,x_n)) i=1,⋯, n. The first lower bound result states that if a circut G evaluates a multivariate polynomial f, where its nodes are capable of performing (+,*), then the depth(G) is not less than log₂[max_deg(f)]. This result is a generalization of Kung’s[K] results for a univariate polynomial which is log₂ [deg f]. In the second part, we consider the circuit G which evaluates an arbitrary polynomial f in n variables with max_deg(f)≜d_p>1. We present two algorithms that achieve better performance than the classical results of Hyafil[H] and Valiant et al. [VSBR] for most classes of multivariate polynomials. For the class of” dense” polynomials the results are closed to the theorethical bound log C, where C is the sequential *** algorithms generalize Munro-Paterson[MP] method for the univariate case. It should be noticed that the bound obtained by Hyafil[H] and Valiant, Skyum, Berkowitz and Rackoff[VSBR] is not sufficiently tight for the worst-sequential case (dense multivariate polynomials) and their bound can be reduced by the factor of log d while the number of required processors is only O(C). The best improvement is achieved in a case of a”dense” multivariate polynomial. A polynomial is dense if the computation necessitates Ω(dⁿ_p) sequential steps. The simple algorithm requires only n log d_p+O(n√log d_p) parallel steps The second algorithm has parallel complexity, measured by the depth of the circuit, depth(G) ≤ n(log d_p+β)+log n+√log d_p where β ≤ √log d_p. If C=Ω(dⁿ_p) then it is less than log C+√n log C where C is the number of sequential steps, and it requires only O(C) pr

关键词： complexity of parallel computation Dense polynomial Design and analysis of parallel algorithms Maximal-degree Multivariate polynomials

来源：评论

学校读者我要写书评

暂无评论

Fast parallel Matrix Inversion Algorithms: 收藏
分享
引用; SIAM Journal on Computing 1976年第4期5卷 618-623页; 作者： L. Csanky; The parallel arithmetic complexities of matrix inversion, solving systems of linear equations, computing determinants and computing the characteristic polynomial of a matrix are shown to have the same growth rate. Alg... 详细信息; The parallel arithmetic complexities of matrix inversion, solving systems of linear equations, computing determinants and computing the characteristic polynomial of a matrix are shown to have the same growth rate. Algorithms are given that compute these problems in $O (\log^{2} n)$; 来源：评论; 学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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