SIMD Optimization of Linear Expressions for Programmable Graphics Hardware

The increased programmability of graphics hardware allows efficient graphical processing unit (GPU) implementations of a wide range of general computations on commodity PCs. An important factor in such implementations is how to fully exploit the SIMD computing capacities offered by modern graphics processors. Linear expressions in the form of , where A is a matrix, and and are vectors, constitute one of the most basic operations in many scientific computations. In this paper, we propose a SIMD code optimization technique that enables efficient shader codes to be generated for evaluating linear expressions. It is shown that performance can be improved considerably by efficiently packing arithmetic operations into four‐wide SIMD instructions through reordering of the operations in linear expressions. We demonstrate that the presented technique can be used effectively for programming both vertex and pixel shaders for a variety of mathematical applications, including integrating differential equations and solving a sparse linear system of equations using iterative methods.     

Hierarchical Structure Recovery of Point‐Sampled Surfaces

We focus on the class of ‘regular’ models defined by Várady et al. for reverse engineering purposes. Given a 3D surface represented through a dense set of points, we present a novel algorithm that converts to a hierarchical representation . In , the surface is encoded through patches of various shape and size, which form a hierarchical atlas. If belongs to the class of regular models, then captures the most significant features of at all the levels of detail. In this case, we show that can be exploited to interactively select regions of interest on and intuitively re‐design the model. Furthermore, intrinsically encodes a hierarchy of useful ‘segmentations’ of . We present a simple though efficient approach to extract and optimize such segmentations, and we show how they can be used to approximate the input point sets through idealized manifold meshes.     

Best analytic approximation of rational functions of degree 2

Let G be a rational function of degree 2. Explicit formulae are given for the distance from G to H in the L^∞ norm, k = 0, 1, and for the unique ? ? H at which the distance is attained.     

A Branch-and-Prune algorithm for the Molecular Distance Geometry Problem

The Molecular Distance Geometry Problem consists in finding the positions in of the atoms of a molecule, given some of the inter‐atomic distances. We show that under an additional requirement on the given distances this can be transformed to a combinatorial problem. We propose a Branch‐and‐Prune algorithm for the solution of this problem and report on very promising computational results.     

Revisiting bounded context block‐sorting transformations

The Burrows–Wheeler Transform (BWT ) produces a permutation of a string X, denoted X^?, by sorting the n cyclic rotations of X into full lexicographical order and taking the last column of the resulting n×n matrix to be X^?. The transformation is reversible in time. In this paper, we consider an alteration to the process, called k‐BWT , where rotations are only sorted to a depth k. We propose new approaches to the forward and reverse transform, and show that the methods are efficient in practice. More than a decade ago, two algorithms were independently discovered for reversing k‐BWT , both of which run in time. Two recent algorithms have lowered the bounds for the reverse transformation to and, respectively. We examine the practical performance for these reversal algorithms. We find that the original approach is most efficient in practice, and investigates new approaches, aimed at further speeding reversal, which store precomputed context boundaries in the compressed file. By explicitly encoding the context boundaries, we present an reversal technique that is both efficient and effective. Finally, our study elucidates an inherently cache‐friendly – and hitherto unobserved – behavior in the reverse k‐BWT , which could lead to new applications of the k‐BWT transform. In contrast to previous empirical studies, we show that the partial transform can be reversed significantly faster than the full transform, without significantly affecting compression effectiveness. Copyright © 2011 John Wiley & Sons, Ltd.     

Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs

For an ordered subset W= w₁, w₂,?…?w_k of vertices and a vertex u in a connected graph G, the representation of u with respect to W is the ordered k-tuple r(u|W)=(d(u, w₁), d(u, w₂),?…?, d(u, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a local metric generator for G if every two adjacent vertices of G have distinct representations. A minimum local metric generator is called a local metric basis for G and its cardinality the local metric dimension of G. We show that the computation of the local metric dimension of a graph with cut vertices is reduced to the computation of the local metric dimension of the so-called primary subgraphs. The main results are applied to specific constructions including bouquets of graphs, rooted product graphs, corona product graphs, block graphs and chain of graphs.     

Computing median and antimedian sets in median graphs

The median (antimedian) set of a profile π=(u ₁,…,u _k ) of vertices of a graph G is the set of vertices x that minimize (maximize) the remoteness ∑ _i d(x,u _i ). Two algorithms for median graphs G of complexity O(n idim(G)) are designed, where n is the order and idim(G) the isometric dimension of G. The first algorithm computes median sets of profiles and will be in practice often faster than the other algorithm which in addition computes antimedian sets and remoteness functions and works in all partial cubes.     

On the locatic number of graphs

A vertex v of a connected graph G distinguishes a pair u, w of vertices of G if d(v, u)≠d(v, w), where d(·,·) denotes the length of a shortest path between two vertices in G. A k-partition Π={S ₁, S ₂, …, S _k } of the vertex set of G is said to be a locatic partition if for every pair of distinct vertices v and w of G, there exists a vertex s∈S _i for all 1≤i≤k that distinguishes v and w. The cardinality of a largest locatic partition is called the locatic number of G. In this paper, we study the locatic number of paths, cycles and characterize all the connected graphs of order n having locatic number n, n?1 and n?2. Some realizable results are also given in this paper.     

The super spanning connectivity and super spanning laceability of the enhanced hypercubes

A k -container C(u,v) of a graph G is a set of k disjoint paths between u and v. A k-container C(u,v) of G is a k ^* -container if it contains all vertices of G. A graph G is k ^* -connected if there exists a k ^*-container between any two distinct vertices of G. Therefore, a graph is 1^*-connected (respectively, 2^*-connected) if and only if it is Hamiltonian connected (respectively, Hamiltonian). A graph G is super spanning connected if there exists a k ^*-container between any two distinct vertices of G for every k with 1≤k≤κ(G) where κ(G) is the connectivity of G. A bipartite graph G is k ^* -laceable if there exists a k ^*-container between any two vertices from different partite set of G. A bipartite graph G is super spanning laceable if there exists a k ^*-container between any two vertices from different partite set of G for every k with 1≤k≤κ(G). In this paper, we prove that the enhanced hypercube Q _n,m is super spanning laceable if m is an odd integer and super spanning connected if otherwise.

The construction of mutually independent Hamiltonian cycles in bubble-sort graphs

A Hamiltonian cycle C=? u ₁, u ₂, …, u _n(G), u ₁ ? with n(G)=number of vertices of G, is a cycle C(u ₁; G), where u ₁ is the beginning and ending vertex and u _i is the ith vertex in C and u _i ≠u _j for any i≠j, 1≤i, j≤n(G). A set of Hamiltonian cycles {C ₁, C ₂, …, C _k } of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(B _n )=n?1 if n≥4, where B _n is the n-dimensional bubble-sort graph.     

A result on k-valent graphs and its application to a graph embedding problem

Summary It is proved that any n-vertex, k-valent undirected simple graph, G, contains a spanning tree with at least leaves. As a result of this it is shown that any such graph contains an independent set, of size at least n/5k, with the property that deleting the vertices in this set and their incident edges does not disconnect G. This latter result is applied by giving an improved upper bound on the area required to embed arbitrary graphs into grid graphs.     

Spline Based Pseudo‐Inversion of Sampled Data Non‐Minimum Phase Systems for an Almost Exact Output Tracking

This paper considers the problem of achieving a very accurate tracking of a pre‐specified desired output trajectory , for linear, multiple input multiple output, non‐minimum phase and/or non hyperbolic, sampled data, and closed loop control systems. The proposed approach is situated in the general framework of model stable inversion and introduces significant novelties with the purpose of reducing some theoretical and numerical limitations inherent in the methods usually proposed. In particular, the new method does not require either a preactuation or null initial conditions of the system. The desired and the corresponding sought input are partitioned in a transient component ( and u_t(k), respectively) and steady‐state ( and u_s(k), respectively). The desired transient component is freely assigned without requiring it to be null over an initial time interval. This drastically reduces the total settling time. The structure of u_t(k) is a priori assumed to be given by a sampled smoothing spline function. The spline coefficients are determined as the least‐squares solution of the over‐determined system of linear equations obtained imposing that the sampled spline function assumed as reference input yield the desired output over a properly defined transient interval. The steady‐state input u_s(k) is directly analytically computed exploiting the steady‐state output response expressions for inputs belonging to the same set of .     

Simplicial powers of graphs

In a graph, a vertex is simplicial if its neighborhood is a clique. For an integer k≥1, a graph G=(V_G,E_G) is the k-simplicial power of a graph H=(V_H,E_H) (H a root graph of G) if V_G is the set of all simplicial vertices of H, and for all distinct vertices x and y in V_G, xyE_G if and only if the distance in H between x and y is at most k. This concept generalizes k-leaf powers introduced by Nishimura, Ragde and Thilikos which were motivated by the search for underlying phylogenetic trees; k-leaf powers are the k-simplicial powers of trees. Recently, a lot of work has been done on k-leaf powers and their roots as well as on their variants phylogenetic roots and Steiner roots. For k≤5, k-leaf powers can be recognized in linear time, and for k≤4, structural characterizations are known. For k≥6, the recognition and characterization problems of k-leaf powers are still open. Since trees and block graphs (i.e., connected graphs whose blocks are cliques) have very similar metric properties, it is natural to study k-simplicial powers of block graphs. We show that leaf powers of trees and simplicial powers of block graphs are closely related, and we study simplicial powers of other graph classes containing all trees such as ptolemaic graphs and strongly chordal graphs.     

Bimagic Vertex Labelings

The notion of the equivalence of vertex labelings on a given graph is introduced. The equivalence of three bimagic labelings for regular graphs is proved. A particular solution is obtained for the problem of the existence of a 1-vertex bimagic vertex labeling of multipartite graphs, namely, for graphs isomorphic with K_{n, n, m}. It is proved that the sequence of bi-regular graphs K_n(ij)?=?((K_n???1???M)?+?K₁)???(u_nu_i)???(u_nu_j) admits 1-vertex bimagic vertex labeling, where u_i, u_j is any pair of non-adjacent vertices in the graph K_n???1???M, u_n is a vertex of K₁, M is perfect matching of the complete graph K_n???1. It is established that if an r-regular graph G of order n is distance magic, then graph G + G has a 1-vertex bimagic vertex labeling with magic constants (n?+?1)(n?+?r)/2?+?n² and (n?+?1)(n?+?r)/2?+?nr. Two new types of graphs that do not admit 1-vertex bimagic vertex labelings are defined.     

On edge connectivity of direct products of graphs

Let λ(G) be the edge connectivity of G. The direct product of graphs G and H is the graph with vertex set V(G×H)=V(G)×V(H), where two vertices (u₁,v₁) and (u₂,v₂) are adjacent in G×H if u₁u₂∈E(G) and v₁v₂∈E(H). We prove that λ(G×Kn)=min{n(n−1)λ(G),(n−1)δ(G)} for every nontrivial graph G and n?3. We also prove that for almost every pair of graphs G and H with n vertices and edge probability p, G×H is k-connected, where k=O(²(n/logn)).     

Conditional fault hamiltonian connectivity of the complete graph

A path in G is a hamiltonian path if it contains all vertices of G. A graph G is hamiltonian connected if there exists a hamiltonian path between any two distinct vertices of G. The degree of a vertex u in G is the number of vertices of G adjacent to u. We denote by δ(G) the minimum degree of vertices of G. A graph G is conditional k edge-fault tolerant hamiltonian connected if G−F is hamiltonian connected for every F⊂E(G) with |F|?k and δ(G−F)?3. The conditional edge-fault tolerant hamiltonian connectivity is defined as the maximum integer k such that G is k edge-fault tolerant conditional hamiltonian connected if G is hamiltonian connected and is undefined otherwise. Let n?4. We use Kn to denote the complete graph with n vertices. In this paper, we show that for n∉{4,5,8,10}, , , , and .     

Controllability of Semilinear Systems of Parabolic Equations with Delay on the State

In this paper we prove the approximate controllability of the following semilinear system parabolic equations with delay on the state variable where Ω is a bounded domain in is a n × n non diagonal matrix whose eigenvalues are semi‐simple with non negative real part, the control u belongs to and B is a n × m matrix. Here τ≥0 is the maximum delay, which is supposed to be finite. We assume that the operator L:L²([?τ,0];Z)→Z is linear and bounded with and the nonlinear function f:[0,r] × IRⁿ×IR^m→IRⁿ is smooth and bounded.     

Computational and structural analysis of the contour of graphs

Let be a finite, simple, and connected graph. The closed interval of a set is the set of all vertices lying on a shortest path between any pair of vertices of S. The set S is geodetic if . The eccentricity of a vertex v is the number of edges in the greatest shortest path between v and any vertex w of G. A vertex v is a contour vertex if no neighbor of v has eccentricity greater than v. The contour of G is the set formed by the contour vertices of G. We consider two problems: the problem of determining whether the contour of a graph class is geodetic; the problem of determining if there exists a graph such that is not geodetic. We obtain a sufficient condition that is useful for both problems; we prove a realization theorem related to problem and show two infinite families such that is not geodetic. Using computational tools, we establish the minimum graphs for which is not geodetic; and show that all graphs with , and all bipartite graphs with , are such that is geodetic.     

Triangulating multiply-connected polygons: A simple, yet efficient algorithm.

We present a new, simple, yet efficient algorithm for triangulating multiply-connected polygons. The algorithm requires sorting only local concave minima (sags). The order in which triangles are created mimics a flooding process of the interior of the polygon. At each stage, the algorithm analyses the positions and neighborhoods of two vertices only, and possibly checks for active sags, so as to determine which of five possible actions to take. Actions are based on a local decomposition of the polygon into monotonic regions, or gorges (raise the water level in the current gorge, spill into an adjacent gorge, jump to the other bank of a filled gorge, divide a gorge into two, and fill a gorge to its top). The implementation is extremely simple and numerically robust for a large class of polygons. It has been tested on millions of cases as a preprocessing step of a walkthrough and inspection program for complex mechanical and architectural scenes. Extensive experimental results indicate that the observed complexity in terms of the number of vertices, remains under in all cases.