MUPHY: A parallel MUlti PHYsics/scale code for high performance bio-fluidic simulations

We present a parallel version of MUPHY, a multi-physics/scale code based upon the combination of microscopic Molecular Dynamics (MD) with a hydro-kinetic Lattice Boltzmann (LB) method. The features of the parallel version of MUPHY are hereby demonstrated for the case of translocation of biopolymers through nanometer-sized, multi-pore configurations, taking into explicit account the hydrodynamic interactions of the translocating molecules with the surrounding fluid. The parallel implementation exhibits excellent scalability on the IBM BlueGene platform and includes techniques which may improve the flexibility and efficiency of other complex multi-physics parallel applications, such as hemodynamics, targeted-drug delivery and others.     

Routing on Meshes with Buses

We consider the problem of routing packets on an MIMD mesh-connected array of processors augmented with row and column buses. We give lower bounds and randomized algorithms for the problem of routing k-permutations (where each processor is the source and destination of exactly k packets) on a d-dimensional mesh with buses, which we call the (k,d)-routing problem. We give a general class of ``hard' permutations which we use to prove lower bounds for the (k,d)-routing problem, for all k,d≥ 1. For the (1,1)- and (1,2)-routing problems the worst-case permutations from this class are identical to ones published by other authors, as are the resulting lower bounds. However, we further show that the (1,d)-routing problem requires 0.72 ... n steps for d=3, 0.76 ... n steps for d=4, and slightly more than steps for all d≥ 5. We also obtain new lower bounds for the (k,d)-routing problem for k,d > 1, which improve on the bisection lower bound in some cases. These lower bounds hold for off-line routing as well. We develop efficient algorithms for the (k,1)-routing problem and for the problem of routing k-randomizations (where each processor has k packets initially and each packet is routed to a random destination) on the one-dimensional mesh and use them in a general (k,d)-routing algorithm which improves considerably on previous results. In particular, the routing time for the (1,d)-routing problem is bounded by steps with high probability (whp), whenever for some constant ε > 0, and the routing time for the (k,d)-routing problem is steps whp whenever for some constant ε > 0 and k≥ 3.6 ... d, matching the bisection lower bound. We then present a simple algorithm for the (2,2)-routing problem running in 1.39 ... n+o(n) steps whp. Finally, for the important special case of routing permutations on two-dimensional meshes with buses, the (1,2)-routing problem, we give a more sophisticated algorithm that runs in 0.78 ... n+o(n) steps whp. Received May 18, 1994; revised June 23, 1995.     

Efficient Data Distribution Schemes for EKMR-Based Sparse Arrays on Distributed Memory Multicomputers

Multi-dimensional sparse array operations can be used in the atmosphere and ocean sciences, the image processing, and etc., and have been an extensively investigated problem. Therefore, it becomes an important issue to propose efficient data distribution schemes for multi-dimensional sparse arrays. In our previous work, we have proposed two data distribution schemes Compress Followed Send (CFS) and Encoding-Decoding (ED) for sparse arrays based on the traditional matrix representation (TMR) scheme. We have proposed another scheme, called extended Karnaugh map representation (EKMR), to represent sparse arrays. The EKMR scheme can obtain better performance than the TMR scheme for some sparse array operations. Hence, in this paper, we want to propose efficient data distribution schemes for EKMR-based sparse arrays. We extend the CFS and the ED schemes for TMR-based sparse arrays to EKMR-based sparse arrays first. Then, we compare the performance of these two schemes with that of the Send Followed Compress (SFC), which is an intuitive data distribution scheme for sparse arrays. Finally, we compare these three schemes for EKMR-based sparse arrays with those of TMR-based sparse arrays, respectively. Both the theoretical analysis and the experimental tests were conducted. From the theoretical analysis and the experimental results, we can see that the ED scheme is superior to the CFS scheme that is superior to the SFC scheme for most of testing EKMR-based sparse arrays; the performance of these three schemes for EKMR-based sparse arrays is better than that of TMR-based sparse arrays for all of testing cases, respectively.     

Star graph automorphisms and disjoint Hamilton cycles

The search for edge-disjoint Hamilton cycles in star graphs is important for the design of interconnection network topologies. We define automorphisms for star graphs St _n of degree n?1, for every positive odd integer n, which yield permutations of labels for the edges of St _n taken from the set of integers between 1 and ? n/2 ?. By decomposing these permutations into permutation cycles, we are able to identify edge-disjoint Hamilton cycles that are automorphic images of a known Hamilton cycle in St _n . Our method produces a better than two-fold improvement from ? ? (n)/10 ? to ? 2? (n)/9 ?, where ? is the Euler function, for the known number of edge-disjoint Hamilton cycles in St _n for all odd integers n. For prime n, the improvement is from ? n/8 ? to ? n/5 ?, and we can extend this result to the case when n is the power of a prime greater than 7.     

Parallel Construction of (a, b)-Trees

We present an optimal parallel algorithm for the construction of (a, b)-trees-a generalization of 2-3 trees, 2-3-4 trees, and B-trees. We show the existence of a canonical form for (a, b)-trees, with a very regular structure, which allows us to obtain a scalable parallel algorithm for the construction of a minimum-height (a, b)-tree with N keys in O(N/p + log log N) time using p ≤ N/log log N processors on the EREW-PRAM model, and in O(N/p) time using p ≤ N processors on the CREW model. We show that the average memory utilization for the canonical form is at least 50% better than that for the worst-case and is also better than that for a random (a, b)-tree. A significant feature of the proposed parallel algorithm is that its time-complexity depends neither on a nor on b, and hence our general algorithm is superior to earlier algorithms for parallel construction of B-trees.     

Exponential lower bounds for depth three Boolean circuits

We consider the class of unbounded fan-in depth three Boolean circuits, for which the bottom fan-in is limited by k and the top gate is an OR. It is known that the smallest such circuit computing the parity function has gates (for k = O(n ^1/2)) for some , and this was the best lower bound known for explicit (P-time computable) functions. In this paper, for k = 2, we exhibit functions in uniform NC ¹ that require size depth 3 circuits. The main tool is a theorem that shows that any circuit on n variables that accepts a inputs and has size s must be constant on a projection (subset defined by equations of the form x _i = 0, x _i = 1, x _i = x _j or x _i = ) of dimension at least log(a/s)log n. Received: April 1, 1997.     

Strong Minimax Lower Bounds for Learning

Minimax lower bounds for concept learning state, for example, that for each sample size n and learning rule g _n , there exists a distribution of the observation X and a concept C to be learnt such that the expected error of g _n is at least a constant times V/n, where V is the vc dimension of the concept class. However, these bounds do not tell anything about the rate of decrease of the error for a fixed distribution-concept pair.In this paper we investigate minimax lower bounds in such a (stronger) sense. We show that for several natural k-parameter concept classes, including the class of linear halfspaces, the class of balls, the class of polyhedra with a certain number of faces, and a class of neural networks, for any sequence of learning rules {g _n }, there exists a fixed distribution of X and a fixed conceptC such that the expected error is larger than a constant timesk/n for infinitely many n. We also obtain such strong minimax lower bounds for the tail distribution of the probability of error, which extend the corresponding minimax lower bounds.     

Labeling Schemes for Tree Representation

This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling ℒ _all gives each node v of G a label containing the port numbers of all the tree edges incident to v. The upward tree labeling ℒ _up labels each node v by the number of the port leading from v to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted M _up (T) and S _up (T) for ℒ _up and M _all (T) and S _all (T) for ℒ _all . The problem studied in this paper is the following: Given a graph G and a predefined port labeling for it, with the ports of each node v numbered by 0,…,deg (v)−1, select a rooted spanning tree for G minimizing (one of) these measures. We show that the problem is polynomial for M _up (T), S _up (T) and S _all (T) but NP-hard for M _all (T) (even for 3-regular planar graphs). We show that for every graph G and port labeling there exists a spanning tree T for which S _up (T)=O(nlog log n). We give a tight bound of O(n) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port labeling. We conclude by discussing some applications for our tree representation schemes. A preliminary version of this paper has appeared in the proceedings of the 7th International Workshop on Distributed Computing (IWDC), Kharagpur, India, December 27–30, 2005, as part of Cohen, R. et al.: Labeling schemes for tree representation. In: Proceedings of 7th International Workshop on Distributed Computing (IWDC), Lecture Notes of Computer Science, vol. 3741, pp. 13–24 (2005). R. Cohen supported by the Pacific Theaters Foundation. P. Fraigniaud and D. Ilcinkas supported by the project “PairAPair” of the ACI Masses de Données, the project “Fragile” of the ACI Sécurité et Informatique, and by the project “Grand Large” of INRIA. A. Korman supported in part by an Aly Kaufman fellowship. D. Peleg supported in part by a grant from the Israel Science Foundation.     

Parallel Algorithms for Maximum Matching in Complements of Interval Graphs and Related Problems

Given a set of n intervals representing an interval graph, the problem of finding a maximum matching between pairs of disjoint (nonintersecting) intervals has been considered in the sequential model. In this paper we present parallel algorithms for computing maximum cardinality matchings among pairs of disjoint intervals in interval graphs in the EREW PRAM and hypercube models. For the general case of the problem, our algorithms compute a maximum matching in O( log ³ n) time using O(n/ log ² n) processors on the EREW PRAM and using n processors on the hypercubes. For the case of proper interval graphs, our algorithm runs in O( log n ) time using O(n) processors if the input intervals are not given already sorted and using O(n/ log n ) processors otherwise, on the EREW PRAM. On n -processor hypercubes, our algorithm for the proper interval case takes O( log n log log n ) time for unsorted input and O( log n ) time for sorted input. Our parallel results also lead to optimal sequential algorithms for computing maximum matchings among disjoint intervals. In addition, we present an improved parallel algorithm for maximum matching between overlapping intervals in proper interval graphs. Received November 20, 1995; revised September 3, 1998.     

On the 1-fault hamiltonicity for graphs satisfying Ore's theorem and its generalization

Consider any undirected and simple graph G=(V, E), where V and E denote the vertex set and the edge set of G, respectively. Let |G|=|V|=n. The well-known Ore's theorem states that if deg_G(u)+deg_G(v)≥n+k holds for each pair of nonadjacent vertices u and v of G, then G is traceable for k=?1, hamiltonian for k=0, and hamiltonian-connected for k=1. Lin et al. generalized Ore's theorem and showed that under the same condition as above, G is r*-connected for 1≤r≤k+2 with k≥1. In this paper, we improve both theorems by showing that the hamiltonicity or r*-connectivity of any graph G satisfying the condition deg_G(u)+deg_G(v)≥n+k with k≥?1 is preserved even after one vertex or one edge is removed, unless G belongs to two exceptional families.     

Approximation Algorithms for the Fixed-Topology Phylogenetic Number Problem

In the l -phylogeny problem, one wishes to construct an evolutionary tree for a set of species represented by characters, in which each state of each character induces no more than l connected components. We consider the fixed-topology version of this problem for fixed-topologies of arbitrary degree. This version of the problem is known to be NP -complete for l ≥ 3 even for degree-3 trees in which no state labels more than l+1 leaves (and therefore there is a trivial l + 1 phylogeny). We give a 2 -approximation algorithm for all l ≥ 3 for arbitrary input topologies and we give an optimal approximation algorithm that constructs a 4 -phylogeny when a 3 -phylogeny exists. Dynamic programming techniques, which are typically used in fixed-topology problems, cannot be applied to l -phylogeny problems. Our 2 -approximation algorithm is the first application of linear programming to approximation algorithms for phylogeny problems. We extend our results to a related problem in which characters are polymorphic. Received June 9, 1997; revised March 13, 1998.     

Parallel algorithms for arrangements

We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds ofO (logn log^* n) time andn ²/logn processors. We generalize this to obtain anO (logn log^* n)-time algorithm usingn ^d /logn processors for solving the problem ind dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrangement ofn lines on-line, in which each insertion is done in optimalO (logn) time usingn/logn processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.This work was supported by the National Science Foundation, under Grants CCR-8657562 and CCR-8858799, NSF/DARPA under Grant CCR-8907960, and Digital Equipment Corporation. A preliminary version of this paper appeared at the Second Annual ACM Symposium on Parallel Algorithms and Architectures [3].     

On Restricted-Focus-of-Attention Learnability of Boolean Functions

In the k-Restricted-Focus-of-Attention (k-RFA) model, only k of the n attributes of each example are revealed to the learner, although the set of visible attributes in each example is determined by the learner. While thek -RFA model is a natural extension of the PAC model, there are also significant differences. For example, it was previously known that learnability in this model is not characterized by the VC-dimension and that many PAC learning algorithms are not applicable in the k-RFA setting.In this paper we further explore the relationship between the PAC and k -RFA models, with several interesting results. First, we develop an information-theoretic characterization of k-RFA learnability upon which we build a general tool for proving hardness results. We then apply this and other new techniques for studying RFA learning to two particularly expressive function classes,k -decision-lists (k-DL) and k-TOP, the class of thresholds of parity functions in which each parity function takes at most k inputs. Among other results, we prove a hardness result for k-RFA learnability of k-DL,k n-2 . In sharp contrast, an (n-1)-RFA algorithm for learning (n-1)-DL is presented. Similarly, we prove that 1-DL is learnable if and only if at least half of the inputs are visible in each instance. In addition, we show that there is a uniform-distribution k-RFA learning algorithm for the class of k -DL. For k-TOP we show weak learnability by ak -RFA algorithm (with efficient time and sample complexity for constant k) and strong uniform-distribution k-RFA learnability of k-TOP with efficient sample complexity for constant k. Finally, by combining some of our k-DL and k-TOP results, we show that, unlike the PAC model, weak learning does not imply strong learning in the k -RFA model.     

Improving the panconnectedness property of locally twisted cubes

The n-dimensional locally twisted cube LTQ_n is a promising alternative to the hypercube because of its great properties. Not only is LTQ_n n-connected, but also meshes, torus, and edge-disjoint Hamiltonian cycles can embed in it. Ma and Xu [Panconnectivity of locally twisted cubes, Appl. Math. Lett. 19 (2006), pp. 681–685] investigated the panconnectivity of LTQ_n for flexible routing. In this paper, we combine panconnectivity with Hamiltonian connectedness to define Hamiltonian r-panconnectedness: a graph G of m vertices, m≥3, is Hamiltonian r-panconnected if for any three distinct vertices x, y, and z of G there exists a Hamiltonian path P of G such that P(1)=x, P(l+1)=y, and P(m)=z for every r≤l≤m?1?r, where P(i) denotes the ith vertex of P for 1≤i≤m. Then, we show that LTQ_n is Hamiltonian n-panconnected for n≥5. This property admits the path embedding via an intermediate node at any prescribed position, and our result achieves an improvement over that of Ma and Xu.     

Linear Time Algorithms for Generalized Edge Dominating Set Problems

We prove that a generalization of the edge dominating set problem, in which each edge e needs to be covered b _e times for all e∈E, admits a linear time 2-approximation for general unweighted graphs and that it can be solved optimally for weighted trees. We show how to solve it optimally in linear time for unweighted trees and for weighted trees in which b _e ∈{0,1} for all e∈E. Moreover, we show that it solves generalizations of weighted matching, vertex cover, and edge cover in trees.     

随机可满足实例集上警示传播算法的收敛性

信息传播算法在求解随机kSAT问题时有惊人的效果,难解区域变窄.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,为有效分析WP算法在随机kCNF公式上的收敛性,给出了随机kCNF公式因子图上圈存在的相变点.在随机kCNF公式产生模型G(n,k,p)中,取k=3,p=d/n2,因子图中圈存在的相变点为p=1/8n2.当d＜1/8时,因子图中开始出现圈,且每个连通分支至多有一个圈,因子图中含圈的连通分支的数目以及圈的长度均与n无关.因此,因子图是由森林和一些含有唯一圈的连通分支构成.证明了WP算法在这些实例集上高概率收敛,并且给出了算法的迭代步数为O(logn+s),其中,s为连通分支的大小.     

On bounds for the existence of a bistable controller

By we shall denote the set of polynomials nonzero on the closed disk {z: |z|r}. The problem to be studied is given as follows.Avoidance Problem. Given polynomials A and B, nonnegative integers n, m, and positive numbers r₁, r₂, r₃, determine if there exist , with degrees n and m, respectively, such that AP+BQ is in .It is shown that the Avoidance Problem for r₁=r₂=r₃=1 is equivalent to the well-known Bistable Stabilization Problem for a large class of control systems.Also, a general class of optimization problems for solving the Avoidance Problem is introduced. The class of optimization problems includes problems with sets more general than disks . In addition, an algorithm is proposed for solving these optimization problems, and numerical experience is reported.As an application, bistable controllers for the plant are shown to exist for values of β as low as 0.0246, thus improving on previously reported results by Blondel et al. for this difficult case.Furthermore, it is shown how in some cases it is possible to find optimal controllers by using a combination of numerical and algebraic techniques, and a variant of the algorithm already introduced. As an example, a low order controller is found for for the case when .This method could be applied to other problems where the plant depends on a parameter.     

On approximation behavior of the greedy triangulation for convex polygons

We prove that the greedy triangulation heuristic for minimum weight triangulation of convex polygons yields solutions within a constant factor from the optimum. For interesting classes of convex polygons, we derive small upper bounds on the constant approximation factor. Our results contrast with Kirkpatrick's (n) bound on the approximation factor of the Delaunay triangulation heuristic for minimum weight triangulation of convexn-vertex polygons. On the other hand, we present a straightforward implementation of the greedy triangulation heuristic for ann-vertex convex point set or a convex polygon takingO(n ²) time andO(n) space. To derive the latter result, we show that given a convex polygonP, one can find for all verticesv ofP a shortest diagonal ofP incident tov in linear time. Finally, we observe that the greedy triangulation for convex polygons having so-called semicircular property can be constructed in timeO(n logn).