Graph embeddings and simplicial maps

An undirected graph is viewed as a simplicial complex. The notion of a graph embedding of a guest graph in a host graph is generalized to the realm of simplicial maps. Dilation is redefined in this more general setting. Lower bounds on dilation for various guest and host graphs are considered. Of particular interest are graphs that have been proposed as communication networks for parallel architectures. Bhattet al. provide a lower bound on dilation for embedding a planar guest graph in a butterfly host graph. Here, this lower bound is extended in two directions. First, a lower bound that applies to arbitrary guest graphs is derived, using tools from algebraic topology. Second, this lower bound is shown to apply to arbitrary host graphs through a new graph-theoretic measure, called bidecomposability. Bounds on the bidecomposability of the butterfly graph and of thek-dimensional torus are determined. As corollaries to the main lower-bound theorem, lower bounds are derived for embedding arbitrary planar graphs, genusg graphs, andk-dimensional meshes in a butterfly host graph.     

New global optimization algorithms for model-based clustering

The Expectation-Maximization (EM) algorithm is a very popular optimization tool for mixture problems and in particular for model-based clustering problems. However, while the algorithm is convenient to implement and numerically very stable, it only produces local solutions. Thus, it may not achieve the globally optimal solution in problems that have a large number of local optima. This paper introduces several new algorithms designed to produce global solutions in model-based clustering. The building blocks for these algorithms are methods from the operations research literature, namely the Cross-Entropy (CE) method and Model Reference Adaptive Search (MRAS). One problem with applying these methods directly is the efficient simulation of positive definite covariance matrices. We propose several new solutions to this problem. One solution is to apply the principles of Expectation-Maximization updating, which leads to two new algorithms, CE-EM and MRAS-EM. We also propose two additional algorithms, CE-CD and MRAS-CD, which rely on the Cholesky decomposition. We conduct numerical experiments of varying complexity to evaluate the effectiveness of the proposed algorithms in comparison to classical EM. We find that although a single run of the new algorithms is slower than a single run of EM, all have the potential for producing significantly better solutions. We also find that although repeat application of EM may achieve similar results, our algorithms provide automated, data-driven decision rules which may significantly reduce the burden of searching for the global optimum.     

New results for the minimum weight triangulation problem

Given a finite set of points in a plane, a triangulation is a maximal set of nonintersecting line segments connecting the points. The weight of a triangulation is the sum of the Euclidean lengths of its line segments. No polynomial-time algorithm is known to find a triangulation of minimum weight, nor is the minimum weight triangulation problem known to be NP-hard. This paper proposes a new heuristic algorithm that triangulates a set ofn points inO(n ³⁾ time and that never produces a triangulation whose weight is greater than that of a greedy triangulation. The algorithm produces an optimal triangulation if the points are the vertices of a convex polygon. Experimental results indicate that this algorithm rarely produces a nonoptimal triangulation and performs much better than a seemingly similar heuristic of Lingas. In the direction of showing the minimum weight triangulation problem is NP-hard, two generalizations that are quite close to the minimum weight triangulation problem are shown to be NP-hard.This research was done while the second author was with the Department of Computer Science, Virginia Polytechnic Institute and State University.     

How Will We Interact with the Web of Data?

The Web is currently evolving from an information space of linked documents, to a Web of linked, machine-readable data. Perhaps counter-intuitively, this shift to publishing data for machine consumption raises many challenges for human-computer interaction. In this article I will discuss some of the implications of this trend for how we interact with the Web of data and consider how familiar tools such as the Web browser may need to develop.     

Collaborative Semantic Authoring

In the context of the semantic Web, notions of collaboration, interoperability, and reuse are intrinsically interrelated: interoperability implies reuse, which in turn is a form of collaboration. If we adopt this viewpoint, the semantic Web becomes essentially a medium for knowledge exchange, in which the knowledge produced by one agent is consumed by another agent, possibly to create new knowledge. A collaboration-centric perspective on the semantic Web introduces both challenges and interesting research directions. Clearly, it's no longer desirable that the process of authoring semantic content necessarily take place in a room full of experts and ontologists. Indeed, as we move from classic Web 2.0 technologies to scenarios in which semantic content is created, our technologies need to change so that it becomes possible to create and exchange knowledge transparently, in accordance with the medium's openness and the knowledge producers' various goals and skill levels. In this article, we examine three modalities for collaborative semantic authoring based on selecting and reusing external, open semantic resources. These three ways of creating semantic content correspond to three levels of interaction between the user and the created resources. We illustrate each level by describing a tool we designed in the context of our research on semantic Web applications at the Knowledge Media Institute.     

Solution of sparse positive definite systems on a shared-memory multiprocessor

Algorithms and software for solving sparse symmetric positive definite systems on serial computers have reached a high state of development. In this paper, we present algorithms for performing sparse Cholesky factorization and sparse triangular solutions on a shared-memory multiprocessor computer, along with some numerical experiments demonstrating their performance on a Sequent Balance 8000 system.Research was supported by the Applied Mathematical Sciences Research Program of the Office of Energy Research, U.S. Department of Energy under contract DE-AC05-84OR21400 with Martin Marieta Energy Systems, Inc., by the U.S. Air Force Office of Scientific Research under contract AFOSR-ISSA-85-00083 and by the Canadian Natural Sciences and Engineering Research Council under grants A8111 and A5509.     

The emerging landscape of bioinformatics software systems

Fusing computing and biology expertise, bioinformatics software provides a powerful tool for organizing and mining the vast amounts of data genetics researchers are accumulating. As life scientists and computational scientists interact to create useful bioinformatics software systems, several themes or lessons recur. We identify seven themes: the nature of biological data; data storage, analysis and retrieval; computational modeling and simulation; biologically meaningful information integration; data mining; image processing and visualization; and closing the loop     

Discriminating Conduct: Deploying Systems to Support Awareness in Organizations

Alongside the emergence of the use of fieldwork studies for design there has been a discussion on how best these studies can inform system development. Concerns have been expressed as to whether their most appropriate contribution is a list of requirements or design recommendations. This article explores a recurrent issue that has emerged from fieldwork studies in Computer-Supported Cooperative Work, awareness, and with respect to a particular system development project discusses some of the implications for the development and deployment of one particular kind of technology—image recognition systems—in particular, organizational settings. In the setting in question—surveillance centers or operations rooms—staff utilize a range of practices to maintain awareness. Rather than extending field studies so that they can better assist design, it may be considered how workplace studies can contribute to a respecification of key concepts, like awareness, that are critical to an understanding of how technologies are used and deployed in everyday environments.     

Factorization of multipliers in passivity and IQC analysis

Multipliers are often used to find conditions for the absolute stability of Lur’e systems. They can be used either in conjunction with passivity theory or within the more recent framework of integral quadratic constraints (IQCs). We compare the use of multipliers in both approaches. Passivity theory requires that the multipliers have a canonical factorization and it has been suggested in the literature that this represents an advantage of the IQC theory. We consider sufficient conditions on the nonlinearity class for the associated multipliers to have a canonical factorization.     

The visual display of parallel performance data

Several performance visualization tools have demonstrated that helpful insights into parallel performance can be gained through graphical displays. However, much of this work has been experimental, specialized, and ad hoc. Evolving performance visualization into an integral, productive tool for evaluating parallel performance requires a more systematic, formal methodology that relates behavior abstractions to visual representations in a more structured way. We propose a high-level abstract model for the performance visualization process, explain its relationship to the most important concepts and principles of effective visualization practice, and illustrate the relationship between these concepts and our abstract model through specific case studies. We also discuss the relationship of performance visualization to general scientific visualization