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

A FAST SELECTION ALGORITHM FOR MESHES WITH MULTIPLE BROADCASTING

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1994年第7期5卷 772-778页

作者： BHAGAVATHI, D LOOGES, PJ OLARIU, S SCHWING, JL ZHANG, J OLD DOMINION UNIV DEPT COMP SCINORFOLKVA 23529 ELIZABETH CITY STATE UNIV DEPT MATH & COMP SCIELIZABETH CITYNC 27909

One of the fundamental algorithmic problems in computer science involves selecting the kth smallest element in a collection A of n elements. We propose an algorithm design methodology to solve the selection problem on meshes with multiple broadcasting. Our methodology leads to a selection algorithm that runs in O(n1/8(log n)3/4) time on a mesh with multiple broadcasting of size n3/8(log n)1/4 X n5/8/(log n)1/4 . This result is optimal over a large class of selection algorithms. Our result shows that just as for semigroup computations, selection can be done faster on suitably chosen rectangular meshes than on square meshes.

关键词： MESH WITH MULTIPLE BROADCASTING SELECTION QUERY PROCESSING DATABASES ALGORITHM DESIGN METHODOLOGIES PARALLEL algorithms optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

ON THE CRUDE MULTIDIMENSIONAL SEARCH

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 1994年第3期56卷 283-293页

作者： SOBOL, IM BAKIN, SG RUSSIAN ACAD SCI INST MATH MODELLINGMOSCOW 125047RUSSIA

Multivariable trial functions that depend on random parameters are maximized by crude global search. Analytical and numerical investigations of error distributions confirm recent conclusions that in practice random searching points perform better than rectangular lattices, and that quasi-random searching points are even more efficient.

关键词： OPTIMIZATION optimal algorithms CRUDE SEARCH RANDOM SEARCH QUASI-RANDOM SEARCH

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT EREW PRAM algorithms FOR PARENTHESES-MATCHING

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1994年第9期5卷 995-1008页

作者： PRASAD, SK DAS, SK CHEN, CCY UNIV N TEXAS DENTON TX 76203 USA TAMKANG UNIV DEPT COMP & INFORMAT ENGN TAIPEI TAIWAN

We present four polylog-time parallel algorithms for matching parentheses on an exclusive-read and exclusive-write (EREW) parallel random-access machine (PRAM) model. These algorithms provide new insights into the parentheses-matching problem. The first algorithm has a time complexity of O(log2 n) employing O(n/log n) processors for an input string containing n parentheses. Although this algorithm is not cost-optimal, it is extremely simple to implement. The remaining three algorithms, which are based on a different approach, achieve O(log n) time complexity in each case, and represent successive improvements. The second algorithm requires O(n) processors and working space, and it is comparable to the first algorithm in its ease of implementation. The third algorithm uses O(n/log n) processors and O(n log n) space. Thus, it is cost-optimal, but uses extra space compared to the standard stack-based sequential algorithm. The last algorithm reduces the space complexity to O(n) while maintaining the same processor and time complexities. Compared to other existing time-optimal algorithms for the parentheses-matching problem that either employ extensive pipelining or use linked lists and comparable data structures, and employ sorting or a linked list ranking algorithm as subroutines, our last two algorithms have two distinct advantages. First, these algorithms employ arrays as their basic data structures, and second, they do not use any pipelining, sorting, or linked list ranking algorithms.

关键词： EREW PRAM optimal algorithms PARALLEL ALGORITHM PARENTHESES-MATCHING PARSING

来源：评论

学校读者我要写书评

暂无评论

SCALABILITY ASPECTS OF PARALLEL MULTIGRID

引用

FUTURE GENERATION COMPUTER SYSTEMS 1994年第4期10卷 429-439页

作者： LINDEN, J LONSDALE, G RITZDORF, H SCHULLER, A Gesellschaft für Mathematik und Datenverarbeitung mbH P.O. Box 1316 D-5205 St. Augustin 1 Germany

This paper summarizes theoretical and practical investigations into the effect of parallelization by grid-partitioning on the performance of multigrid methods for the solution of partial differential equations on general two-dimensional domains. Particular emphasis will be placed on the algorithmic scalability for MIMD distributed memory systems. Experimental results for two Navier-Stokes test problems, presented in the last section of the paper, show that the theoretically predicted dependency of the combined numerical and parallel efficiencies of multigrid methods on the number of processors employed is in fact very weak. This leads to the conclusion that multigrid is an appropriate candidate for solving partial differential equations on massively parallel machines.

关键词： PARALLEL MULTIGRID SCALABILITY optimal algorithms NAVIER-STOKES EQUATIONS

来源：评论

学校读者我要写书评

暂无评论

ON PARALLEL PREFIX COMPUTATION

引用

Parallel Processing Letters 1994年第4期4卷 429-436页

作者： SANJEEV SAXENA P.C.P. BHATT V.C. PRASAD Computer Science and Engineering Indian Institute Of Technology Kanpur 208 016 India Micro-elec. and Comp.Sys.Lab. Electrical Enginnering Department McGill University 3480 University Street Montreal (Quebec) H3A 2A7 Canada On leave from: Computer Science and Engineering Indian Institute Of Technology Delhi New Delhi 110 016 INDIA Electrical Engineering Indian Institute Of Technology Delhi New Delhi 110 016 India

We prove that prefix sums of n integers of at most b bits can be found on a COMMON CRCW PRAM in time with a linear time-processor product. The algorithm is optimally fast, for any polynomial number of processors. In particular, if the time taken is . This is a generalisation of previous result. The previous time algorithm was valid only for O(log n)-bit numbers. Application of this algorithm to r-way parallel merge sort algorithm is also considered. We also consider a more realistic PRAM variant, in which the word size, m, may be smaller than b (m≥log n). On this model, prefix sums can be found in optimal time.

关键词： Parallel prefix parallel algorithm optimal algorithms shared memory model sorting CRCW model

来源：评论

学校读者我要写书评

暂无评论

optimal PARALLEL algorithms FOR PROBLEMS MODELED BY A FAMILY OF INTERVALS

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1992年第3期3卷 364-374页

作者： OLARIU, S SCHWING, JL ZHANG, JY Department of Computer Science Old Dominion University Norfolk VA USA

A family of intervals on the real line provides a natural model for a vast number of scheduling and VLSI problems. Recently, a number of parallel algorithms to solve a variety of practical problems on such a family of intervals have been proposed in the literature. We develop computational tools and show how they can be used for the purpose of devising cost-optimal parallel algorithms for a number of interval-related problems including finding a largest subset of pairwise nonoverlapping intervals, a minimum dominating subset of intervals, along with algorithms to compute the shortest path between a pair of intervals and, based on the shortest path, a parallel algorithm to find the center of the family of intervals. More precisely, with an arbitrary family of n intervals as input, all our algorithms run in O(log n) time using O(n) processors in the EREW-PRAM model of computation.

关键词： EREW-PRAM EULER-TOUR TECHNIQUE FACILITY-LOCATION INTERVALS LIST RANKING optimal algorithms PARALLEL algorithms SCHEDULING VLSI

来源：评论

学校读者我要写书评

暂无评论

optimal CONVEX-HULL algorithms ON ENHANCED MESHES

引用

BIT 1993年第3期33卷 396-410页

作者： OLARIU, S SCHWING, JL ZHANG, J OLD DOMINION UNIV DEPT COMP SCINORFOLKVA 23529

In this paper we propose time-optimal convex hull algorithms for two classes of enhanced meshes. Our first algorithm computes the convex hull of an arbitrary set of n points in the plane in O(log n) time on a mesh with multiple broadcasting of size n x n. The second algorithm shows that the same problem can be solved in O(1) time on a reconfigurable mesh of size n x n. Both algorithms achieve time lower bounds for their respective model of computation.

关键词： SORTING MESHES WITH MULTIPLE BROADCASTING RECONFIGURABLE MESHES CONVEX HULLS optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

A NOTE ON THE 1-MAXIMAL ELEMENTS PROBLEM

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1993年第3-4期49卷 171-175页

作者： PIGLI, EM Department of Computer Science Norfolk State University Norfolk VA 23504 United States

Consider a set of S points in the plane. A point p in S is said to be k-maximal if exactly k elements in S dominate p. We propose a very simple, cost-optimal, EREW algorithm to solve the 1-maximal elements problem in ... 详细信息

关键词： PARALLEL algorithms optimal algorithms DOMINATION COMPUTATIONAL GEOMETRY MAXIMAL ELEMENTS

来源：评论

学校读者我要写书评

暂无评论

A FIBONACCI VERSION OF KRAFTS INEQUALITY APPLIED TO DISCRETE UNIMODAL SEARCH

引用

SIAM JOURNAL ON COMPUTING 1993年第4期22卷 751-777页

作者： GOLDSTEIN, AS REINGOLD, EM

A function is unimodal if it strictly increases to a unique maximum and then strictly decreases. The problem of determining the smallest possible interval containing the maximum of a unimodal function, by probing only at integer values is studied. In the finite case, the search takes place over the range 0 to N, while in the infinite case the search takes place over the nonnegative integers. The analyses are based on an unusual Fibonacci version of Kraft's inequality.

关键词： UNIMODAL SEARCH FIBONACCI SEARCH KRAFT INEQUALITY FIBONACCI NUMBERS UNIMODAL FUNCTIONS UNBOUNDED SEARCH optimal algorithms ACKERMANN FUNCTION INVERSE ACKERMANN FUNCTION

来源：评论

学校读者我要写书评

暂无评论

ACCELERATED STOCHASTIC APPROXIMATION

引用

SIAM JOURNAL ON OPTIMIZATION 1993年第4期3卷 868-881页

作者： Delyon, Bernard Juditsky, Anatoli Inst Natl Rech Informat & Automat Inst Rech Informat & Syst Aleatoires F-35042 Rennes France

A technique to accelerate convergence of stochastic approximation algorithms is studied. It is based on Kesten's idea of equalization of the gain coefficient for the Robbins-Monro algorithm. Convergence with probability is proved for the multidimensional analog of the Kesten accelerated stochastic approximation algorithm. Asymptotic normality of the delivered estimates is also shown. Results of numerical simulations are presented that demonstrate the efficiency of the acceleration procedure.

关键词： stochastic approximation accelerated algorithms optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：