This work describes an adaptation of multilevel search to the covering design problem. The search engine is a tabu search algorithm which explores several levels of overlapping search spaces of a t-(v, k, lambda) cove...
详细信息
ISBN:
(纸本)3540335897
This work describes an adaptation of multilevel search to the covering design problem. The search engine is a tabu search algorithm which explores several levels of overlapping search spaces of a t-(v, k, lambda) covering design problem. Tabu search finds "good" approximations of covering designs in each search space. Blocks from those approximate solutions are transferred to other levels, redefining the corresponding search spaces. The dynamics of cooperation among levels tends to regroup good approximate solutions into small search spaces. Tabu search has been quite effective at finding re-combinations of blocks in small search spaces which provide successful search directions in larger search spaces.
In this paper, the authors introduce a robust numerical technique for radiation-conduction heat transfer in the high temperature fields of gas turbine combustors. The conduction and radiation effects are analyzed by a...
详细信息
In this paper, the authors introduce a robust numerical technique for radiation-conduction heat transfer in the high temperature fields of gas turbine combustors. The conduction and radiation effects are analyzed by a differential and an integral equation, respectively. Using discrete ordinates for the angular discretization of the integral equation for the radiation effects and a Galerkin discretization for the heat equation, the authors propose a fast multilevel algorithm to solve the fully discretized problem. The algorithm uses the same mesh hierarchy for both radiation and conduction effects, but with two different smoothing operators. Numerical results are shown for test problems in three space dimensions, and comparisons to other methods are also given.
A novel multilevel algorithm for computing the radiation patterns of nonplanar aperture antennas over a range of observation angles is presented. The proposed technique is directly applicable to reflector and lens ant...
详细信息
A novel multilevel algorithm for computing the radiation patterns of nonplanar aperture antennas over a range of observation angles is presented. The proposed technique is directly applicable to reflector and lens antennas as well as to radomes. The multilevel computational sequence is based on a hierarchical decomposition of the. radiating aperture and comprises two main steps. First, computation of the radiation patterns of all subapertures of the finest level over a very coarse angular grid. Second, multilevel aggregation of the radiation patterns of neighboring subapertures into the final pattern of the whole aperture via a phase compensated interpolation. The multilevel algorithm attains computational complexity comparable to that of the fast Fourier transform based techniques while avoiding their limitations.
We propose some algorithms to solve the system of linens equations arising from the finite difference discretization on sparse grids. For this, we will use the multilevel structure of the sparse grid space or its full...
详细信息
We propose some algorithms to solve the system of linens equations arising from the finite difference discretization on sparse grids. For this, we will use the multilevel structure of the sparse grid space or its full grid subspaces, respectively.
In this article, we show that multigrid-like algorithms can be obtained by combining space decomposition with time discretization by operator splitting. (C) 2002 Elsevier Science Ltd. All rights reserved.
In this article, we show that multigrid-like algorithms can be obtained by combining space decomposition with time discretization by operator splitting. (C) 2002 Elsevier Science Ltd. All rights reserved.
The objectives in this paper are twofold: design an approach for the netlist partitioning problem using the cooperative multilevel search paradigm introduced by Toulouse et aL and study the effectiveness of this parad...
详细信息
The objectives in this paper are twofold: design an approach for the netlist partitioning problem using the cooperative multilevel search paradigm introduced by Toulouse et aL and study the effectiveness of this paradigm for solving combinatorial optimization problems, in particular, those arising in the very large scale integration (VLSI) computer-aided design (CAD) area. The authors present, a cooperative multilevel search algorithm CoMHP and describe a parallel implementation on the SGI O2000 system. Experiments on ISPD98 benchmark suite of circuits show, for four-way and eight-way partitioning, a reduction of 3% to 15% in the size of hyperedge cuts compared to those obtained by hMETIS. Bisections of hypergraphs based on the algorithm also outperform hMETIS, although more modestly. The authors present experimental results to demonstrate that the cooperation scheme plays a key role in the performance of CoMHP. In fact, the improvement in the quality of the solutions produced by CoMHP is to a large extent independent of the partitioners used in the implementation of CoMHP. The experimental results also demonstrate the effectiveness of the cooperative multilevel search paradigm for solving the netlist partitioning problem and show that the cooperative multilevel search strategy can be used as a paradigm for designing effective solution techniques for combinatorial optimization problems such as those arising in the VLSI CAD area.
A novel algorithm to efficiently compute time-harmonic fields produced by known two-dimensional source constellations is proposed. The algorithm relies on domain decomposition and comprises two steps to be repeated fo...
详细信息
A novel algorithm to efficiently compute time-harmonic fields produced by known two-dimensional source constellations is proposed. The algorithm relies on domain decomposition and comprises two steps to be repeated for each subdomain. In the first step, phase, and amplitude compensated fields, produced by currents residing within each subdomain are computed over a sparse set of points surrounding the observation domain. During the second step, total fields in the observer domain are evaluated by interpolation, phase and amplitude restoration and aggregation of subdomain fields. The proposed approach is applied to the fast iterative analysis of scattering phenomena using the method of moments.
Three parallel optimisation algorithms, for use in the context of multilevel graph partitioning of unstructured meshes, are described. The first, interface optimisation, reduces the computation to a set of independent...
详细信息
Three parallel optimisation algorithms, for use in the context of multilevel graph partitioning of unstructured meshes, are described. The first, interface optimisation, reduces the computation to a set of independent optimisation problems in interface regions. The next, alternating optimisation, is a restriction of this technique in which mesh entities are only allowed to migrate between subdomains in one direction. The third treats the gain as a potential held and uses the concept of relative gain for selecting appropriate vertices to migrate. The results are compared and seen to produce very high global quality partitions, very rapidly. The results are also compared with another partitioning tool and shown to be of higher quality although taking longer to compute. (C) 2000 Elsevier Science B.V. All rights reserved.
multilevel algorithms are a successful class of optimization techniques which addresses the mesh partitioning problem. They usually combine a graph contraction algorithm together with a local optimization method which...
详细信息
multilevel algorithms are a successful class of optimization techniques which addresses the mesh partitioning problem. They usually combine a graph contraction algorithm together with a local optimization method which refines the partition at each graph level. In this paper we present an enhancement of the technique which uses imbalance to achieve higher quality partitions. We also present a formulation of the Kernighan-Lin partition optimization algorithm which incorporates load-balancing. The resulting algorithm is tested against a different but related state-of-the-art partitioner and shown to provide improved results.
In this paper, we present a new hypergraph-partitioning algorithm that is based on the multilevel paradigm. In the multilevel paradigm, a sequence of successively coarser hypergraphs is constructed, A bisection of the...
详细信息
In this paper, we present a new hypergraph-partitioning algorithm that is based on the multilevel paradigm. In the multilevel paradigm, a sequence of successively coarser hypergraphs is constructed, A bisection of the smallest hypergraph is computed and it is used to obtain a bisection of the original hypergraph by successively projecting and refining the bisection to the next level finer hypergraph. We have developed new hypergraph coarsening strategies within the multilevel framework. We evaluate their performance both in terms of the size of the hyperedge cut on the bisection, as well as on the run time for a number of very large scale integration circuits. Our experiments show that our multilevel hypergraph-partitioning algorithm produces high-quality partitioning in a relatively small amount of time. The quality of the partitionings produced by our scheme are on the average 6%-23% better than those produced by other state-of-the-art schemes. Furthermore, our partitioning algorithm is significantly faster, often requiring CIO times less time than that required by the other schemes. Our multilevel hypergraph-partitioning algorithm scales very well for large hypergraphs, Hypergraphs with over 100 000 vertices can be bisected in a few minutes on today's workstations. Also, on the large hypergraphs, our scheme outperforms other schemes (in hyperedge cut) quite consistently with larger margins (9%-30%).
暂无评论