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

Optimally fast CRCW-PRAM testing 2D-arrays for existence of repetitive patterns

INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE 2001年第7期15卷 1167-1182页

作者： Brimkov, VE Univ Padua Dipartimento Elettr & Informat I-35100 Padua Italy

In classical combinatorial string matching repetitions and other regularities play a central role. Besides their theoretical importance, repetitions in strings have been found relevant to coding and automata theory, formal languages, data compression, and molecular biology. An important motivation for developing a 2D pattern matching theory is seen in its relation with pattern recognition, image processing, computer vision and multimedia. Repetitions in 2D arrays have been defined and classified recently.(5) In this paper we present an optimally fast CRCW-PRAM algorithm for testing whether a given n x n array contains repetitions of certain type. The algorithm takes optimal O (log log n) time with n(2)log(2)n/log log n processors.

关键词： 2D array pattern repetition tandem CRCW-PRAM model parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Concurrent determination of connected components

引用

SCIENCE OF COMPUTER PROGRAMMING 2001年第2期41卷 173-194页

作者： Hesselink, WH Meijster, A Bron, C Univ Groningen Dept Math & Comp Sci NL-9700 AV Groningen Netherlands

The design is described of a parallel version of Tarjan's algorithm for the determination of equivalence classes in graphs that represent images. Distribution of the vertices of the graph over a number of processes leads to a message passing algorithm. The algorithm is mapped to a shared-memory architecture by means of POSIX threads. It is applied to the determination of connected components in image processing. Experiments show a satisfactory speedup for sufficiently large images. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： connected components parallel algorithm pthreads mutex condition variable

来源：评论

学校读者我要写书评

暂无评论

The complexity of acyclic conjunctive queries

引用

JOURNAL OF THE ACM 2001年第3期48卷 431-498页

作者： Gottlob, G Leone, N Scarcello, F Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria Univ Calabria Dept Math I-87030 Arcavacata Di Rende Italy Univ Calabria DEIS I-87030 Arcavacata Di Rende Italy

This paper deals with the evaluation of acyclic Boolean conjunctive queries in relational databases. By well-known results of Yannakakis [1981], this problem is solvable in polynomial time, its precise complexity, however, has not been pinpointed so far, We show that the problem of evaluating acyclic Boolean conjunctive queries is complete for LOGCFL, the class of decision problems that are logspace-reducible to a context-free language. Since LOGCFL is contained in AC(1) and NC(2). the evaluation problem of acyclic Boolean conjunctive queries is highly parallelizable, We present a parallel database algorithm solving this problem with a logarithmic number of parallel join operations. The algorithm is generalized to computing the output of relevant classes of non-Boolean queries. We also show that the acyclic versions of the following well-known database and Al problems are all LOGCFL-complete: The Query Output Tuple problem for conjunctive queries. Conjunctive Query Containment, Clause Subsumption, and Constraint Satisfaction. The LOGCFL-completeness result is extended to the class of queries of bounded treewidth and to other relevant query classes which are more general than the acyclic queries.

关键词： theory acyclic hypergraph algorithm bounded treewidth conjunctive query constraint constraint satisfaction problem CSP database theory degree of cyclicity hinge join tree LOGCFL parallel algorithm query containment query-width subsumption tree query

来源：评论

学校读者我要写书评

暂无评论

An adaptive algorithm for conversion from quadtree to chain codes

引用

PATTERN RECOGNITION 2001年第3期34卷 631-639页

作者： Shih, FY Wong, WT New Jersey Inst Technol Dept Comp & Informat Sci Comp Vis Lab Newark NJ 07102 USA

An adaptive algorithm is presented for converting the quadtree representation of a binary image to its chain code representation. Our algorithm has the advantage of constructing the chain codes of the resulting quadtree of the Boolean operation of two quadtrees by re-using the original chain codes. This algorithm is adaptive because it can adjust the total number of internal nodes to be stored and retrieve it later in the reconstruction stage. The algorithm possesses parallelism and is suited for pyramid architecture. Our algorithm requires time O(H + L) in sequential and time O(N) in parallel, where H is the height of the quadtree, L is the length of the chain code sequence generated, and N x N is the size of the input image. (C) 2001 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.

关键词： image representation chain code quadtree parallel algorithm adaptive conversion

来源：评论

学校读者我要写书评

暂无评论

Stochastic bilevel programming in structural optimization

引用

STRUCTURAL AND MULTIDISCIPLINARY OPTIMIZATION 2001年第5期21卷 361-371页

作者： Christiansen, S Patriksson, M Wynter, L Ecole Polytech Palaiseau France Chalmers Univ Technol Dept Math S-41296 Gothenburg Sweden Univ Versailles PRISM F-78000 Versailles France

We consider the mathematical modelling and solution of robust and cost-optimizing structural (topology) design problems. The setting is the optimal design of a linear-elastic structure, for example a truss topology, under unilateral frictionless contact, and under uncertainty in the data describing the load conditions, the material properties, and the rigid foundation. The resulting stochastic bilevel optimization model finds a structural design that responds the best to the given probability distribution in the data. This model is of special interest when a structural failure will lead to a reconstruction cost, rather than loss of life. For the mathematical model, we provide results on the existence of optimal solutions which allow for zero lower design bounds. We establish that the optimal solution is continuous in the lower design bounds, a result which validates the use of small but positive values of them, and for such bounds we also establish the locally Lipschitz continuity and directional differentiability of the implicit upper-level objective function. We also provide a heuristic algorithm for the solution of the problem, which makes use of its differentiability properties and parallelization strategies across the scenarios. A small set of numerical experiments illustrates the behaviour of the stochastic solution compared to all average-case deterministic one, establishing ail increased robustness.

关键词： topology optimization mathematical program with equilibrium constraints (MPEC) contact conditions average-case analysis parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient prefix computation on faulty hypercubes

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2001年第1期17卷 1-21页

作者： Chen, YW Chung, KL Aletheia Univ Dept Comp & Informat Sci Taipei 251 Taiwan Natl Taiwan Univ Sci & Technol Inst Comp Sci & Informat Engn Dept Informat Management Taipei 106 Taiwan

Consider an n-dimensional SIMD hypercube H-n with [3n/2] - 1 faulty nodes. Given 2(n) operands, this paper presents an efficient algorithm for prefix computation on the faulty H-n. Employing the newly proposed delay-update technique and the subcube partition scheme, the proposed algorithm takes n+5logn+7 steps, and it tolerates [n/2] more Faulty nodes than does Raghavendra and Sridhar's algorithm [4] although 11 extra steps are needed.

关键词： complexity analysis fault tolerance parallel algorithm prefix computation SIMD hypercube

来源：评论

学校读者我要写书评

暂无评论

L₂ vector median filters on arrays with reconfigurable optical buses

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2001年第12期12卷 1281-1292页

作者： Wu, CH Horng, SJ Chinese Naval Acad Dept Informat Management Kaohsiung Taiwan Natl Taiwan Univ Sci & Technol Dept Elect Engn Taipei Taiwan

In spite of their good filtering characteristics for vector-valued image processing, the usability of vector median filters is limited by their high computational complexity. Given an N x N image and a W x W window, the computational complexity of vector median filter is O((WN2)-N-4). In this paper, we design three fast and efficient parallel algorithms for vector median filtering based on the 2-norm (L-2) on the arrays with reconfigurable optical buses (AROB). For 1 less than or equal to p less than or equal to W less than or equal to q less than or equal to N, our algorithms run in O(W-4 log W/p(4)), O((WN2)-N-4/p(4)p(2) log W) and W(1) times using p(4)N(2)/log W, p(4)q(2)/log W, and W(4)N(2)log N processors, respectively. In the sense of the product of time and the number of processors used, the first two results are cost optimal and the last one is time optimal.

关键词： parallel algorithm scalable algorithm vector median filter nonlinear filter image (signal) processing reconfigurable optical bus system

来源：评论

学校读者我要写书评

暂无评论

Communication efficient BSP algorithm all nearest smaller values problem

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2001年第10期61卷 1425-1438页

作者： He, X Huang, CH SUNY Buffalo Dept Comp Sci & Engn Buffalo NY 14260 USA

We present a BSP (Bulk Synchronous parallel) algorithm for solving the All Nearest Smaller Values Problem (ANSVP), a fundamental problem in both graph theory and computational geometry. Our algorithm achieves optimal sequential computation time and uses only three communication supersteps. In the worst case, each communication phase takes no more than an (n/p + p)-relation, where p is the number of the processors. In addition, our average-case analysis shows that, on random inputs, the expected communication requirements for all three steps are bounded above by a p-relation, which is independent of the problem size n. Experiments have been carried out on an SGI Origin 2000 with 32 R10000 processors and a SUN Enterprise 4000 multiprocessing server supporting 8 UltraSPARC processors, using the MPI libraries. The results clearly demonstrate the communication efficiency and load balancing for computation. (C) 2001 Academic Press.

关键词： BSP ANSVP parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Lifting factorization-based discrete wavelet transform architecture design

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY 2001年第5期11卷 651-657页

作者： Jiang, WQ Ortega, A Univ So Calif Dept Elect Engn Syst Integrated Media Syst Ctr Los Angeles CA 90089 USA

In this paper, tao new system architectures, overlap-state sequential and split-and-merge parallel, are proposed based on a novel boundary postprocessing technique for the computation of the discrete wavelet transform (DWT). The basic idea is to introduce multilevel partial computations for samples near data boundaries based on a finite state machine model of the DWT derived from the lifting scheme. The key observation is that these partially computed (lifted) results can also be stored back to their original locations and the transform can be continued anytime later as long as these partial computed results are preserved. It is shown that such an extension of the in-place calculation feature of the original lifting algorithm greatly helps to reduce the extra buffer and communication overheads, in sequential and parallel system implementations, respectively. Performance analysis and experimental results show that, for the Daubechies (9,7) wavelet filters, using the proposed boundary postprocessing technique, the minimal required buffer size in the line-based sequential DWT algorithm [1] is 40% less than the best available approach. In the parallel DWT algorithm me show 30% faster performance than existing approaches.

关键词： boundary postprocessing discrete wavelet transform overlap-state parallel algorithm sequential algorithm split-and-merge

来源：评论

学校读者我要写书评

暂无评论

parallel algorithm for efficient calculation of second derivatives of conformational energy function in internal coordinates

引用

Journal of Computational Chemistry 1999年第15期19卷

作者： Shugo Nakamura Mitsunori Ikeguchi Kentaro Shimizu Department of Biotechnology The University of Tokyo Yayoi 1‐1‐1 Bunkyo‐ku Tokyo 113‐8657 Japan

A parallel algorithm for efficient calculation of the second derivatives (Hessian) of the conformational energy in internal coordinates is proposed. This parallel algorithm is based on the master/slave model. A master processor distributes the calculations of components of the Hessian to one or more slave processors that, after finishing their calculations, send the results to the master processor that assembles all the components of the Hessian. Our previously developed molecular analysis system for conformational energy optimization, normal mode analysis, and Monte Carlo simulation for internal coordinates is extended to use this parallel algorithm for Hessian calculation on a massively parallel computer. The implementation of our algorithm uses the message passing interface and works effectively on both distributed‐memory parallel computers and shared‐memory parallel computers. We applied this system to the Newton–Raphson energy optimization of the structures of glutaminyl transfer RNA (Gln‐tRNA) with 74 nucleotides and glutaminyl‐tRNA synthetase (GlnRS) with 540 residues to analyze the performance of our system. The parallel speedups for the Hessian calculation were 6.8 for Gln‐tRNA with 24 processors and 11.2 for GlnRS with 54 processors. The parallel speedups for the Newton–Raphson optimization were 6.3 for Gln‐tRNA with 30 processors and 12.0 for GlnRS with 62 processors. © 1998 John Wiley & Sons, Inc. J Comput Chem 19: 1716–1723, 1998

关键词： internal coordinates Hessian parallel algorithm message passing interface Newton–Raphson optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：