Reflections on the evolution of implicit Navier–Stokes algorithms

This article gives a historical perspective on the evolution of implicit algorithms for the Navier–Stokes equations that utilize time or Newton linearizations and various forms of approximate factorization including alternating-direction, lower/upper, and symmetric relaxation schemes. A theme of the paper is how progress in implicit Navier–Stokes algorithms has been influenced and enabled by the introduction of characteristic-based upwind approximations, unstructured-grid discretizations, parallelization, and by advances in computer performance and architecture. Historical examples of runtime, problem size, and estimated cost are given for actual and hypothetical Navier–Stokes flow cases from the past 40 years.     

3D model alignment based on minimum projection area

3D model alignment is an important step for applications such as 3D model retrieval and 3D model recognition. In this paper, we propose a novel Minimum Projection Area-based (MPA) alignment method for pose normalization. Our method finds three principal axes to align a model: the first principal axis gives the minimum projection area when we perform an orthographic projection of the model in the direction parallel to this axis, the second axis is perpendicular to the first axis and gives the minimum projection area, and the third axis is the cross product of the first two axes. We devise an optimization method based on Particle Swarm Optimization to efficiently find the axis with minimum projection area. For application in retrieval, we further perform axis ordering and orientation in order to align similar models in similar poses. We have tested MPA on several standard databases which include rigid/non-rigid and open/watertight models. Experimental results demonstrate that MPA has a good performance in finding alignment axes which are parallel to the ideal canonical coordinate frame of models and aligning similar models in similar poses under different conditions such as model variations, noise, and initial poses. In addition, it achieves a better 3D model retrieval performance than several commonly used approaches such as CPCA, NPCA, and PCA.     

A Stronger Model of Dynamic Programming Algorithms

We define a formal model of dynamic programming algorithms which we call Prioritized Branching Programs (pBP). Our model is a generalization of the BT model of Alekhnovich et al. (IEEE Conference on Computational Complexity, pp. 308–322, 2005), which is in turn a generalization of the priority algorithms model of Borodin, Nielson and Rackoff. One of the distinguishing features of these models is that they not only capture large classes of algorithms generally considered to be greedy, backtracking or dynamic programming algorithms, but they also allow characterizations of their limitations. Hence they give meaning to the statement that a given problem can or cannot be solved by dynamic programming. After defining the model, we prove three main results: (i) that certain types of natural restrictions of our seemingly more powerful model can be simulated by the BT model; (ii) that in general our model is stronger than the BT model—a fact which is witnessed by the classical shortest paths problem; (iii) that our model has very real limitations, namely that bipartite matching cannot be efficiently computed in it, hence suggesting that there are problems that can be solved efficiently by network flow algorithms and by simple linear programming that cannot be solved by natural dynamic programming approaches.     

Dynamic visualization of coexpression in systems genetics data

Biologists hope to address grand scientific challenges by exploring the abundance of data made available through modern microarray technology and other high-throughput techniques. The impact of this data, however, is limited unless researchers can effectively assimilate such complex information and integrate it into their daily research; interactive visualization tools are called for to support the effort. Specifically, typical studies of gene co-expression require novel visualization tools that enable the dynamic formulation and fine-tuning of hypotheses to aid the process of evaluating sensitivity of key parameters. These tools should allow biologists to develop an intuitive understanding of the structure of biological networks and discover genes residing in critical positions in networks and pathways. By using a graph as a universal representation of correlation in gene expression, our system employs several techniques that when used in an integrated manner provide innovative analytical capabilities. Our tool for interacting with gene co-expression data integrates techniques such as: graph layout, qualitative subgraph extraction through a novel 2D user interface, quantitative subgraph extraction using graph-theoretic algorithms or by compound queries, dynamic level-of-detail abstraction, and template-based fuzzy classification. We demonstrate our system using a real-world workflow from a large-scale, systems genetics study of mammalian gene co-expression.     

Learning to Be Thoughtless: Social Norms and Individual Computation

This paper extends the literature on the evolution of norms with anagent-based modelcapturing a phenomenon that has been essentially ignored, namely thatindividual thought – orcomputing – is often inversely related to the strength of a social norm.Once a norm isentrenched, we conform thoughtlessly. In this model, agents learn how tobehave (what normto adopt), but – under a strategy I term Best Reply to Adaptive SampleEvidence – they also learnhow much to think about how to behave. How much they are thinking affects howthey behave,which – given how others behave – affects how much they think. Inshort, there is feedbackbetween the social (inter-agent) and internal (intra-agent) dynamics. Inaddition, we generate thestylized facts regarding the spatio-temporal evolution of norms: localconformity, global diversity,and punctuated equilibria.     

Parametric embedding for class visualization

We propose a new method, parametric embedding (PE), that embeds objects with the class structure into a low-dimensional visualization space. PE takes as input a set of class conditional probabilities for given data points and tries to preserve the structure in an embedding space by minimizing a sum of Kullback-Leibler divergences, under the assumption that samples are generated by a gaussian mixture with equal covariances in the embedding space. PE has many potential uses depending on the source of the input data, providing insight into the classifier's behavior in supervised, semisupervised, and unsupervised settings. The PE algorithm has a computational advantage over conventional embedding methods based on pairwise object relations since its complexity scales with the product of the number of objects and the number of classes. We demonstrate PE by visualizing supervised categorization of Web pages, semisupervised categorization of digits, and the relations of words and latent topics found by an unsupervised algorithm, latent Dirichlet allocation.     

NodeTrix: a hybrid visualization of social networks

The need to visualize large social networks is growing as hardware capabilities make analyzing large networks feasible and many new data sets become available. Unfortunately, the visualizations in existing systems do not satisfactorily resolve the basic dilemma of being readable both for the global structure of the network and also for detailed analysis of local communities. To address this problem, we present NodeTrix, a hybrid representation for networks that combines the advantages of two traditional representations: node-link diagrams are used to show the global structure of a network, while arbitrary portions of the network can be shown as adjacency matrices to better support the analysis of communities. A key contribution is a set of interaction techniques. These allow analysts to create a NodeTrix visualization by dragging selections to and from node-link and matrix forms, and to flexibly manipulate the NodeTrix representation to explore the dataset and create meaningful summary visualizations of their findings. Finally, we present a case study applying NodeTrix to the analysis of the InfoVis 2004 coauthorship dataset to illustrate the capabilities of NodeTrix as both an exploration tool and an effective means of communicating results.     

Observations of shadow bands at the total solar eclipse of 16 February 1980

Photoelectric observations of short term light variations (shadow bands) at the 16 Feb. 1980 total solar eclipse have been made using a set of spatially separated PIN diodes. Light variations in a bandpass of 1-500 Hz were detected during the half-minutes preceding and following the total phase. Fourier analysis of the noise spectrum of the variations reveals a sharp drop-off for frequencies above 50 Hz and an overall spectrum quite similar to previously reported power spectra of stellar scintillation. This is consistent with an atmospheric origin for the shadow bands. Cross-correlations between the detector outputs are low, suggesting a short persistence time for the turbulent elements causing the patterns.