摘要:

For ann-gonP, we sayPis weakly visible from segmentsif any point onPis visible from at least one point of the segment. In this paper, we present an optimal preprocessing algorithm which runs inO(logn)time usingO(n) processors under the concurrent read exclusive write parallel random access machine model such that after preprocessing, it takes O(logn) time to test ifPis weakly visible from a given segment using a single processor.

ISSN:1063-7192    

DOI:10.1080/10637199308915433

出版商:Taylor & Francis Group    

年代:1993

数据来源: Taylor

摘要:

In this paper, a systolic array architecture is designed for the parallel implementation of Capon's direction-of-arrival estimation method in array signal processing. The architecture uses the QR decomposition on the data matrix to compute Capon's angular spectrum. The systolic array employsN(N + l)/2 + Nprocessing elements (PEs). The sampling data and the steering vector enter into the systolic array while the angular spectra flow out of the systolic array. The parallel algorithm is simulated by the parallel programming language OCCAM 2 in a single transputer system. The architecture is very efficient with a nigh degree of parallelism.

ISSN:1063-7192    

DOI:10.1080/10637199308915434

出版商:Taylor & Francis Group    

年代:1993

数据来源: Taylor

摘要:

In this paper, we consider the problem of finding the smallest triangle circumscribing a convex polygon withnedges. We show that this can be done inO( √n)time by efficient data partition schemes and proper set mapping and comparison operations using the so-called√n-decomposition technique. Since the nontrivial operation on mesh-connected computers requiresΩ(,√n), the time complexity is optimal within a constant time factor.

ISSN:1063-7192    

DOI:10.1080/10637199308915435

出版商:Taylor & Francis Group    

年代:1993

数据来源: Taylor

摘要:

A mapping procedure for synthesizing uniform recurrence equations from the dynamic programming formulation of the knapsack problem is proposed. Two new systolic arrays are synthesized from the systems of recurrence equations produced. One of these arrays is optimal with respect to both speedup and efficiency and requiresO( nb/q + n − n/q)time andO( q[wmax/2]) processors, wherebis the knapsack capacity,nis the number of items,wmaxis the maximum weight taken over all items, andq > 0 is an arbitrary chosen design parameter.

ISSN:1063-7192    

DOI:10.1080/10637199308915436

出版商:Taylor & Francis Group    

年代:1993

数据来源: Taylor

摘要:

We consider the preconditioned conjugate gradient (PCG) method for solving the linear equations derived from difference approximations to the Laplace operator on 1D line, 2D square or 3D cube domains. If the preconditioner is a block diagonal matrix obtained from cutting the original domain by lines or planes, we can End an upper bound for the condition number of the preconditioned system. For several different parallel machine models, we derive the optimal number of processors to achieve the best asymptotic run time.

ISSN:1063-7192    

DOI:10.1080/10637199308915437

出版商:Taylor & Francis Group    

年代:1993

数据来源: Taylor