Efficient algorithms for computing Reeb graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse function defined on a 3-manifold. Our algorithm maintains connected components of the two dimensional levels sets as a dynamic graph and constructs the Reeb graph in O(nlogn+nlogg(loglogg)3) time, where n is the number of triangles in the tetrahedral mesh representing the 3-manifold and g is the maximum genus over all level sets of the function. We extend this algorithm to construct Reeb graphs of d-manifolds in O(nlogn(loglogn)3) time, where n is the number of triangles in the simplicial complex that represents the d-manifold. Our result is a significant improvement over the previously known O(n2) algorithm. Finally, we present experimental results of our implementation and demonstrate that our algorithm for 3-manifolds performs efficiently in practice.

Towards formal specification of a distributed computing system

Onboard spacecraft computing system is a case of a functionally distributed system that requires continuous interaction among the nodes to control the operations at different nodes. A simple and reliable protocol is desired for such an application. This paper discusses a formal approach to specify the computing system with respect to some important issues encountered in the design and development of a protocol for the onboard distributed system. The issues considered in this paper are concurrency, exclusiveness and sequencing relationships among the various processes at different nodes. A 6-tuple model is developed for the precise specification of the system. The model also enables us to check the consistency of specification and deadlock caused due to improper specification. An example is given to illustrate the use of the proposed methodology for a typical spacecraft configuration. Although the theory is motivated by a specific application the same may be applied to other distributed computing system such as those encountered in process control industries, power plant control and other similar environments.

A new algorithm for parallel solution of linear equations

Abstract is not available.

Parallel processor scheduling for minimizing total weighted tardiness using ant colony optimization

In the modern business environment, meeting due dates and avoiding delay penalties are very important goals that can be accomplished by minimizing total weighted tardiness. We consider a scheduling problem in a system of parallel processors with the objective of minimizing total weighted tardiness. Our aim in the present work is to develop an efficient algorithm for solving the parallel processor problem as compared to the available heuristics in the literature and we propose the ant colony optimization approach for this problem. An extensive experimentation is conducted to evaluate the performance of the ACO approach on different problem sizes with the varied tardiness factors. Our experimentation shows that the proposed ant colony optimization algorithm is giving promising results compared to the best of the available heuristics.

An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V, E). The expected running time of our algorithm is (O) over tilde (mc) where vertical bar E vertical bar = m and c is the maximum u-v edge connectivity, where u, v is an element of V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n - 1; so the expected run-ning time of our algorithm for simple unweighted graphs is (O) over tilde (mn). All the algorithms currently known for constructing a Gomory-Hu tree [8, 9] use n - 1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest (O) over tilde (n(20/9)) max flow algorithm due to Karger and Levine[11] yields the current best running time of (O) over tilde (n(20/9)n) for Gomory-Hu tree construction on simple unweighted graphs with m edges and n vertices. Thus we present the first (O) over tilde (mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs. We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S subset of V can be reused for computing a minimum Steiner cut for certain Steiner sets S' subset of S.

Note On The Stability Of Parallel Magnetic-Fields - Comment

It is shown that the conclusions arrived at regarding the instability of an incompressible fluid cylinder in the presence of the magnetic field and the streaming velocity in a recent communication easily follow from the study of propagation characteristics of Alfvén surface waves along cylindrical plasma columns made earlier.

Topochemical dimerization of non-parallel double bonds: 7-methoxycoumarin

X-ray crystal structure analysis of 7-methoxycoumarin reveals that the reactive double bonds are rotated by about 65° with respect to each other, the centre-to-centre distance between the double bonds being 3.83 Å. In spite of this unfavourable arrangement, photodimerization occurs in the crystalline state yielding the syn-head-tail dimer as the only product. Lattice energy calculations on ground-state molecules in crystals throw light on the mechanism of the reaction.

Parallel polygon scan conversion algorithms: Performance evaluation on a shared bus architecture

In this paper, three parallel polygon scan conversion algorithms have been proposed, and their performance when executed on a shared bus architecture has been compared. It has been shown that the parallel algorithm that does not use edge coherence performs better than those that use edge coherence. Further, a multiprocessing architecture has been proposed to execute the parallel polygon scan conversion algorithms more efficiently than a single shared bus architecture.

A parallel-serial binary arbitration scheme for collision-free multi-access techniques

Multi-access techniques are widely used in computer networking and distributed multiprocessor systems. On-the-fly arbitration schemes permit one of the many contenders to access the medium without collisions. Serial arbitration is cost effective but is slow and hence unsuitable for high-speed multiprocessor environments supporting very high data transfer rates. A fully parallel arbitration scheme takes less time but is not practically realisable for large numbers of contenders. In this paper, a generalised parallel-serial scheme is proposed which significantly reduces the arbitration time and is practically realisable.

Parallel packing of alpha-helices in crystals of the zervamicin IIA analog Boc-Trp-Ile-Ala-Aib-Ile-Val-Aib-Leu-Aib-Pro-OMe.2H2O.

An apolar synthetic analog of the first 10 residues at the NH2-terminal end of zervamicin IIA crystallizes in the triclinic space group P1 with cell dimensions a = 10.206 +/- 0.002 A, b = 12.244 +/- 0.002 A, c = 15.049 +/- 0.002 A, alpha = 93.94 +/- 0.01 degrees, beta = 95.10 +/- 0.01 degrees, gamma = 104.56 +/- 0.01 degrees, Z = 1, C60H97N11O13 X 2H2O. Despite the relatively few alpha-aminoisobutyric acid residues, the peptide maintains a helical form. The first intrahelical hydrogen bond is of the 3(10) type between N(3) and O(0), followed by five alpha-helix-type hydrogen bonds. Solution 1H NMR studies in chloroform also favor a helical conformation, with seven solvent-shielded NH groups. Continuous columns are formed by head-to-tail hydrogen bonds between the helical molecules along the helix axis. The absence of polar side chains precludes any lateral hydrogen bonds. Since the peptide crystallizes with one molecule in a triclinic space group, aggregation of the helical columns must necessarily be parallel rather than antiparallel. The packing of the columns is rather inefficient, as indicated by very few good van der Waals' contacts and the occurrence of voids between the molecules.

BSDD-2.0: Biomolecules Segment Display Device - An updated web accessible computing resource

The existing internet computing resource, Biomolecules Segment Display Device (BSDD), has been updated with several additional useful features. An advanced option is provided to superpose the structural motifs obtained from a search on the Protein Data Bank (PDB) in order to see if the three-dimensional structures adopted by identical or similar sequence motifs are the same. Furthermore, the options to display structural aspects like inter- and intra-molecular interactions, ion-pairs, disulphide bonds, etc. have been provided.The updated resource is interfaced with an up-to-date copy of the public domain PDB as well as 25 and 90% non-redundant protein structures. Further, users can upload the three-dimensional atomic coordinates (PDB format) from the client machine. A free molecular graphics program, JMol, is interfaced with it to display the three-dimensional structures.

Phased-Mission Analysis for Evaluating the Effectiveness of Aerospace Computing-Systems

Effectiveness evaluation of aerospace fault-tolerant computing systems used in a phased-mission environment is rather tricky and difficult because of the interaction of its several degraded performance levels with the multiple objectives of the mission and the use environment. Part I uses an approach based on multiobjective phased-mission analysis to evaluate the effectiveness of a distributed avionics architecture used in a transport aircraft. Part II views the computing system as a multistate s-coherent structure. Lower bounds on the probabilities of accomplishing various levels of performance are evaluated.

Note on the stability of parallel magnetic fields

The stability characteristics of parallel magnetic fields when fluid motions are present along the lines of force is studied. The stability criterion for both symmetric (m=0) and asymmetric (m=1) modes are discussed and the results obtained by Trehan and Singh (1978) are amended in the present study. The results obtained for the cylindrical geometry are shown to play an important role forka<4, wherek is the wave number,a is the radius of the cylinder, compared to the results obtained by Geronicolas (1977) for the slab geometry.

Natural frequencies of rectangular orthotropic plates with a pair of parallel edges simply supported

Solutions of the exact characteristic equations for the title problem derived earlier by an extension of Bolotin's asymptotic method are considered. These solutions, which correspond to flexural modes with frequency factor, R, greater than unity, are expressed in convenient forms for all combinations of clamped, simply supported and free conditions at the remaining pair of parallel edges. As in the case of uniform beams, the eigenvalues in the CC case are found to be equal to those of elastic modes in the FF case provided that the Kirchoff's shear condition at a free edge is replaced by the condition. The flexural modes with frequency factor less than unity are also investigated in detail by introducing a suitable modification in the procedure. When Poisson's ratios are not zero, it is shown that the frequency factor corresponding to the first symmetric mode in the free-free case is less than unity for all values of side ratio and rigidity ratios. In the case of one edge clamped and the other free it is found that modes with frequency factor less than unity exist for certain dimensions of the plate—a fact hitherto unrecognized in the literature.

Data distribution and task scheduling for distributed computing of all-to-all comparison problems

This research studied distributed computing of all-to-all comparison problems with big data sets. The thesis formalised the problem, and developed a high-performance and scalable computing framework with a programming model, data distribution strategies and task scheduling policies to solve the problem. The study considered storage usage, data locality and load balancing for performance improvement in solving the problem. The research outcomes can be applied in bioinformatics, biometrics and data mining and other domains in which all-to-all comparisons are a typical computing pattern.