Time-optimal visibility-related algorithms on meshes with multiplebroadcasting

Given a collection of objects in the plane along with a viewpoint ω, the visibility problem involves determining the portion of each object that is visible to an observer positioned at ω. The visibility problem is central to various application areas including computer graphics, image processing, VLSI design, and robot navigation, among many others. The main contribution of this work is to provide time-optimal solutions to this problem for several classes of objects, namely ordered line segments, disks, and iso-oriented rectangles in the plane. In addition, our visibility algorithm for line segments is at the heart of time-optimal solutions for determining, for each element in a given sequence of real numbers, the position of the nearest larger element within that sequence, triangulating a set of points in the plane, determining the visibility pairs among a set of vertical line segments, and constructing the dominance and visibility graphs of a set of iso-oriented rectangles in the plane. All the algorithms in this paper involve an input of size n and run in O(log n) time on a mesh with multiple broadcasting of size n×n. This is the first instance of time-optimal solutions for these problems on this architecture     

Constant-time algorithms for constrained triangulations onreconfigurable meshes

A number of applications in computer-aided manufacturing, CAD, and computer-aided geometric design ask for triangulating pieces of material with defects. These tasks are known collectively as constrained triangulations. Recently, a powerful architecture called the reconfigurable mesh has been proposed: In essence, a reconfigurable mesh consists of a mesh-connected architecture augmented by a dynamically reconfigurable bus system. The main contribution of this paper is to show that the flexibility of the reconfigurable mesh can be exploited for the purpose of obtaining constant-time algorithms for a number of constrained triangulation problems. These include triangulating a convex planar region containing any constant number of convex holes, triangulating a convex planar region in the presence of a collection of rectangular holes, and triangulating a set of ordered line segments. Specifically with a collection of O(n) such objects as input, our algorithms run in O(1) time on a reconfigurable mesh of size n×n. To the best of our knowledge, this is the first time constant time solutions to constrained triangulations are reported on this architecture     

Parallel algorithms for moving Lagrangian data on block structured Eulerian meshes

We present a suite of algorithms for migrating Lagrangian data between processors in a parallel environment when the underlying mesh is Eulerian. The collection of algorithms applies to both uniform and adaptive meshes. The algorithms are implemented in, and distributed with, FLASH, a publicly available multiphysics simulation code. Migrating Lagrangian data on an Eulerian mesh is non-trivial because the Eulerian grid points are spatially fixed whereas Lagrangian entities move with the flow of a simulation. Thus, the movement of Lagrangian data cannot use the data migration methods associated with the Eulerian mesh. Additionally, when the mesh is adaptive, as the simulation progresses the grid resolution changes. The resulting regridding process can cause complex Lagrangian data migration.The algorithms presented in this paper describe Lagrangian data movement on a static uniform mesh and on an adaptive octree based block-structured mesh. Some of the algorithms are general enough to be applicable to any block structured mesh, while some others exploit the meta-data and structure of PARAMESH, the adaptive mesh refinement (AMR) package used in FLASH. We also present an analysis of the algorithms’ comparative performances in different parallel environments, and different flow characteristics.     

Configurable algorithms for complete exchange in 2D meshes

The interprocessor complete exchange communication pattern can be found in many important parallel algorithms. In this paper, we present algorithms for complete exchange on 2D mesh-connected multiprocessors. The unique feature of the proposed algorithms is that they are configurable where the time for message startups can be traded against larger message sizes. At one extreme, the algorithm minimizes the number of message startups at the expense of an increased amount of time spent in message transmission. At the other extreme, the time spent in message transmission is reduced at the expense of an increased number of message startups. The structure of the algorithms is such that intermediate solutions are feasible, i.e., the number of message startups can be increased slightly and the message transmission time is correspondingly reduced. The ability to configure these algorithms enables the algorithm characteristics to be matched with machine characteristics based on specific overheads for message initiation and link speeds to minimize overall execution time. In effect, the algorithms can be configured to strike the right balance between direct and message combining approaches on a specific architecture for a given problem size. We believe these algorithms are distinguished by this ability and contribute to efficient portable implementations of complete exchange algorithms     

Hybrid algorithms for complete exchange in 2D meshes

Parallel algorithms for several common problems such as sorting and the FFT involve a personalized exchange of data among all the processors. Past approaches to doing complete exchange have taken one of two broad approaches: direct exchange or the indirect message-combining approaches. While combining approaches reduce the number of message startups, direct exchange minimizes the volume of data transmitted. This paper presents a family of hybrid algorithms for wormhole-routed 2D meshes that can effectively utilize the complementary strengths of these two approaches to complete exchange. The performance of hybrid algorithms using Cyclic Exchange and Scott's Direct Exchange are studied using analytical models, simulation, and implementation on a Cray T3D system. The results show that hybrids achieve lower completion times than either pure algorithm for a range of mesh sizes, data block sizes, and message startup costs. It is also demonstrated that barriers may be used to enhance performance by reducing message contention, whether or not the target system provides hardware support for barrier synchronization. The analytical models are shown useful in selecting the optimum hybrid for any given combination of system parameters (mesh size, message startup time, flit transfer time, and barrier cost) and the problem parameter (data block size)     

Array-based,parallel hierarchical mesh refinement algorithms for unstructured meshes

In this paper, we describe an array-based hierarchical mesh refinement capability through uniform refinement of unstructured meshes for efficient solution of PDE’s using finite element methods and multigrid solvers. A multi-degree, multi-dimensional and multi-level framework is designed to generate the nested hierarchies from an initial coarse mesh that can be used for a variety of purposes such as in multigrid solvers/preconditioners, to do solution convergence and verification studies and to improve overall parallel efficiency by decreasing I/O bandwidth requirements (by loading smaller meshes and in-memory refinement). We also describe a high-order boundary reconstruction capability that can be used to project the new points after refinement using high-order approximations instead of linear projection in order to minimize and provide more control on geometrical errors introduced by curved boundaries.The capability is developed under the parallel unstructured mesh framework “Mesh Oriented dAtaBase” (MOAB Tautges et al. (2004)). We describe the underlying data structures and algorithms to generate such hierarchies in parallel and present numerical results for computational efficiency and effect on mesh quality. We also present results to demonstrate the applicability of the developed capability to study convergence properties of different point projection schemes for various mesh hierarchies and to a multigrid finite-element solver for elliptic problems.     

A general method for deflection worm routing on meshes based onpacket routing algorithms

In this paper, we consider the deflection worm routing problem on n×n meshes. In deflection routing, a message cannot be queued and it is always moving until it reaches its destination. In worm routing, the message is considered to be a worm, a sequence of k flits which, during the routing, follow the head of the worm, which knows the destination address. We show how to derive a deflection worm routing algorithm from a packet routing algorithm which uses queues of size O(f(N))(N is the side-length of the mesh in which the packet routing algorithm is applied). Our result generalizes the method of Newman and Schuster in which only packet routing algorithms with a maximum queue of four packets can be used     

Wavefront diffusion and LMSR: algorithms for dynamic repartitioningof adaptive meshes

Current multilevel repartitioning schemes tend to perform well on certain types of problems while obtaining worse results for other types of problems. We present two new multilevel algorithms for repartitioning adaptive meshes that improve the performance of multilevel schemes for the types of problems that current schemes perform poorly while maintaining similar or better results for those problems that current schemes perform well. Specifically, we present a new scratch-remap scheme called Locally-matched Multilevel Scratch-remap (or simply LMSR) for repartitioning of adaptive meshes. LMSR tries to compute a high-quality partitioning that has a large amount of overlap with the original partitioning. We show that LMSR generally decreases the data redistribution costs required to balance the load compared to current scratch-remap schemes. We present a new diffusion-based scheme that we refer to as Wavefront Diffusion. In Wavefront Diffusion, the flow of vertices moves in a wavefront from overweight to underweight subdomains. We show that Wavefront Diffusion obtains significantly lower data redistribution costs while maintaining similar or better edge-cut results compared to existing diffusion algorithms. We also compare Wavefront Diffusion with LMSR and show that these provide a trade-off between edge-cut and data redistribution costs for a wide range of problems. Our experimental results on a Gray T3E, an IBM SP2, and a cluster of Pentium Pro workstations show that both schemes are fast and scalable. For example, both are capable of repartitioning a seven million vertex graph in under three seconds on 128 processors of a Gray T3E. Our schemes obtained relative speedups of between nine and 12 when the number of processors was increased by a factor of 16 on a Gray T3E     

Permutation-based finite implicative fuzzy associative memories

Implicative fuzzy associative memories (IFAMs) are single layer feedforward fuzzy neural networks whose synaptic weights and threshold values are given by implicative fuzzy learning. Despite an excellent tolerance with respect to either pasitive or negative noise, IFAMs are not suited for patterns corrupted by mixed noise. This paper presents a solution to this problem. Precisely, we first introduce the class of finite IFAMs by replacing the unit interval by a finite chain L. Then, we generalize both finite IFAMs and their dual versions by means of a permutation on L. The resulting models are referred to as permutation-based finite IFAMs (π-IFAMs). We show that a π-IFAM can be viewed as a finite IFAM, but defined on an alternative lattice structure (L,?). Thus, π-IFAMs also exhibit optimal absolute storage capacity and one step convergence in the autoassociative case. Furthermore, computational experiments revealed that a certain π-IFAM, called Lukasiewicz π_μ-IFAM, outperformed several other associative memory models for the reconstruction of gray-scale patterns corrupted by salt and pepper noise.     

Multigrid algorithms for $$\varvec{}$$-version interior penalty discontinuous Galerkin methods on polygonal and polyhedral meshes

In this paper we analyze the convergence properties of two-level and W-cycle multigrid solvers for the numerical solution of the linear system of equations arising from hp-version symmetric interior penalty discontinuous Galerkin discretizations of second-order elliptic partial differential equations on polygonal/polyhedral meshes. We prove that the two-level method converges uniformly with respect to the granularity of the grid and the polynomial approximation degree p, provided that the number of smoothing steps, which depends on p, is chosen sufficiently large. An analogous result is obtained for the W-cycle multigrid algorithm, which is proved to be uniformly convergent with respect to the mesh size, the polynomial approximation degree, and the number of levels, provided the number of smoothing steps is chosen sufficiently large. Numerical experiments are presented which underpin the theoretical predictions; moreover, the proposed multilevel solvers are shown to be convergent in practice, even when some of the theoretical assumptions are not fully satisfied.     

List ranking on meshes

The list-ranking problem is considered for parallel computers which communicate through an interconnection network. The algorithms are based on the idea of repeatedly removing the complement of a ruling set. By specific refinements and detailed analysis, earlier results are improved considerably. We concentrate on meshes, but most of the ideas are more general. Each PU holds nodes of a set of linked lists. For the case , on two-dimensional meshes, the deterministic version takes steps; the randomized version steps. Extensions for larger , require and , steps respectively. Received: 24 November 1995 / 24 October 1997     

Generalized algorithms for systematic synthesis ofBranch-and-Combine clock networks for meshes, tori, and hypercubes

Branch-and-Combine (BaC) clock distribution has recently been introduced. The most interesting aspect of the new scheme is its ability to bound skew by a constant irrespective of network size. In this paper, we introduce algorithms for systematic synthesis of BaC networks for clocking meshes, tori, and hypercubes of different dimensionalities. For meshes our approach relies on filing techniques. We start with the identification of basic proper tiles satisfying certain criteria. We define a set of valid transformations on tiles. By appropriately applying a sequence of transformations on a basic proper tile, one could synthesize a valid BaC network. We formally introduce methods and procedures for applying the above steps to systematically construct different valid BaC network designs for 2D and 3D meshes. To construct BaC networks for clocking hypercubes of any dimensionality we describe a formal methodology. In this case, we utilize an approach called replication which is based on constructing larger hypercube clocking networks from smaller ones. We combine the techniques for 2D, 3D meshes with replication techniques to formulate a methodology applicable to meshes and tori of dimensionality greater than three. We provide proofs of correctness for the algorithms we introduce. Besides, we formally define an optimality criterion based on link costs which is utilized to check the optimality of the synthesized network designs. In the case of meshes, we show that the majority of synthesized networks are optimal with respect to our defined criterion. For those suboptimal networks, we describe a procedure for identifying and removing unnecessary (redundant) links. The procedure is guaranteed to optimize the network without changing its behavioral parameters     

多粒子量子态的超空间克隆

将多粒子量子态的最优克隆和超空间转移结合起来,给出了多粒子态量子超空间克隆的方案,通过对该方案与先克隆再超空间转移方案之间所耗的纠缠资源的比较分析,发现该方案具有消耗纠缠资源少的优点。     

基于互信息的N维多模医学图像配准

目前多模医学图像配准都定位在两幅图像配准的研究,很少涉及N维(3维及3维以上)图像的配准.当用扩展的N维互信息测度(E-NMIM)进行多个图像配准时,不能保证互信息(MI)值的非负性,并且运算速度慢,达不到临床要求.本文提出一种新的N维互信息测度(N-NMIM),不仅保证了MI值的非负性,而且在[1,2]有界范围内,也提高了配准的速度.通过腰椎部位的CT,T1加权的MRI和T2加权的MRI图像进行实验,验证了这种配准方法的有效性.     

N维Hilbert曲线生成算法

Hilbert曲线描述了一种多维空间与1维空间—映射的方法，在图像处理、多维数据索引等领域有着重要的地位。但因为高维Hilbert曲线的复杂性，对高维Hilbert的相关算法研究很少。提出了产生N维Hilbert曲线的一个新算法。该算法基于静态演化规则，自底向上地分析N维Hilbert曲线编码规律，实现N维Hilbert曲线的编码生成。与现有的算法相比，本文算法易于实现。实验结果表明，该算法具有更好的计算性能。     

Gossiping on meshes and tori

Algorithms for performing gossiping on one- and higher-dimensional meshes are presented. As a routing model, the practically important wormhole routing is assumed. We especially focus on the trade-off between the start-up time and the transmission time. For one-dimensional arrays and rings, we give a novel lower bound and an asymptotically optimal gossiping algorithm for all choices of the parameters involved. For two-dimensional meshes and tori, a simple algorithm composed of one-dimensional phases is presented. For an important range of packet and mesh sizes, it gives clear improvements upon previously developed algorithms. The algorithm is analyzed theoretically and the achieved improvements are also convincingly demonstrated by simulations, as well as an implementation on the Paragon. On the Paragon, our algorithm even outperforms the gossiping routine provided in the NX message-passing library. For higher-dimensional meshes, we give algorithms which are based on an interesting generalization of the notion of a diagonal. These algorithms are analyzed theoretically, as well as by simulation     

Box schemes on quadrilateral meshes

Box schemes (finite volume methods) are widely used in fluiddynamics, especially for the solution of conservation laws. In this paper two box-schemes for elliptic equations are analysed with respect to quadrilateral meshes. Using a variational formulation, we gain stability theorems for two different box methods, namely the so-called diagonal boxes and the centre boxes. The analysis is based on an elementwise eigenvalue problem. Stability can only be guaranteed under additional assumptions on the geometry of the quadrilaterals. For the diagonal boxes unsuitable elements can lead to global instabilities. The centre boxes are more robust and differ not so much from the finite element approach. In the stable case, convergence results up to second order are proved with well-known techniques.     

Eigenmodes computation on quadrilateral meshes

We approximate a fluid-structure interaction eigenvalue problem by means of finite elements on quadrilateral meshes. The problem under consideration looks simple and has been the object of a wide investigation: actually, no standard numerical scheme achieves acceptable results in presence of field singularities. We consider a three-field mixed method introduced by Bathe et al. and based on rectangular meshes (see [3, 12]). Recent results show that particular care has to be taken into account when dealing with finite element approximation on general quadrilateral meshes. We present numerical experiments on several sequences of meshes which definitely show how the “local” approach has to be discarded, while the “global” approach gives reasonable results. Received: 30 January 2001 / Accepted: 30 May 2001