Computing the partial conjugate of convex piecewise linear-quadratic bivariate functions

Piecewise linear-quadratic (PLQ) functions are an important class of functions in convex analysis since the result of most convex operators applied to a PLQ function is a PLQ function. We modify a recent algorithm for computing the convex (Legendre-Fenchel) conjugate of convex PLQ functions of two variables, to compute its partial conjugate i.e. the conjugate with respect to one of the variables. The structure of the original algorithm is preserved including its time complexity (linear time with some approximation and log-linear time without approximation). Applying twice the partial conjugate (and a variable switching operator) recovers the full conjugate. We present our partial conjugate algorithm, which is more flexible and simpler than the original full conjugate algorithm. We emphasize the difference with the full conjugate algorithm and illustrate results by computing partial conjugates, partial Moreau envelopes, and partial proximal averages.     

Computing the conjugate of convex piecewise linear-quadratic bivariate functions

We present a new algorithm to compute the Legendre–Fenchel conjugate of convex piecewise linear-quadratic (PLQ) bivariate functions. The algorithm stores a function using a (primal) planar arrangement. It then computes the (dual) arrangement associated with the conjugate by looping through vertices, edges, and faces in the primal arrangement and building associated dual vertices, edges, and faces. Using optimal computational geometry data structures, the algorithm has a linear time worst-case complexity. We present the algorithm, and illustrate it with numerical examples. We proceed to build a toolbox for convex bivariate PLQ functions by implementing the addition, and scalar multiplication operations. Finally, we compose these operators to compute classical convex analysis operators such as the Moreau envelope, and the proximal average.     

Convex Hull Algorithms for Piecewise Linear-Quadratic Functions in Computational Convex Analysis

Computing the convex envelope is a core operation in nonsmooth analysis that bridges the convex with the nonconvex world. Although efficient algorithms to compute fundamental transforms of convex analysis have been proposed over the years, they are limited to convex functions until an efficient algorithm becomes available to compute the convex envelope of a piecewise linear-quadratic function (of one variable) efficiently. We present two such algorithms, one based on maximum and conjugate computation that is easy to implement but has quadratic time complexity, and another based on direct computation that requires more work to implement but has optimal (linear time) complexity. We prove their time (and space) complexity, and compare their performances.     

Computation of the Epsilon-Subdifferential of Convex Piecewise Linear-Quadratic Functions in Optimal Worst-Case Time

Set-Valued and Variational Analysis - The epsilon-subdifferential of convex univariate piecewise linear-quadratic (PLQ) functions can be computed in linear worst-case time complexity as the...     

Computing Cartograms with Optimal Complexity

In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an area-universal rectangular layout in linear time. The exact cartogram can be computed from the area-universal layout with numerical iteration, or can be approximated with a hill-climbing heuristic. We also describe an alternative construction of cartograms for Hamiltonian maximal planar graphs, which allows us to directly compute the cartograms in linear time. Moreover, we prove that even for Hamiltonian graphs 8-sided rectilinear polygons are necessary, by constructing a non-trivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is one-legged, as in outer-planar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outer-planar graphs. Finally we address the problem of constructing small-complexity cartograms for 4-connected graphs (which are Hamiltonian). We first disprove a conjecture, posed by two set of authors, that any 4-connected maximal planar graph has a one-legged Hamiltonian cycle, thereby invalidating an attempt to achieve a polygonal complexity 6 in cartograms for this graph class. We also prove that it is NP-hard to decide whether a given 4-connected plane graph admits a cartogram with respect to a given weight function.     

Algorithm engineering for optimal alignment of protein structure distance matrices

Protein structural alignment is an important problem in computational biology. In this paper, we present first successes on provably optimal pairwise alignment of protein inter-residue distance matrices, using the popular dali scoring function. We introduce the structural alignment problem formally, which enables us to express a variety of scoring functions used in previous work as special cases in a unified framework. Further, we propose the first mathematical model for computing optimal structural alignments based on dense inter-residue distance matrices. We therefore reformulate the problem as a special graph problem and give a tight integer linear programming model. We then present algorithm engineering techniques to handle the huge integer linear programs of real-life distance matrix alignment problems. Applying these techniques, we can compute provably optimal dali alignments for the very first time.     

A Deterministic O(m \log {m}) Time Algorithm for the Reeb Graph

We present a deterministic algorithm to compute the Reeb graph of a PL real-valued function on a simplicial complex in $O(m \log {m})$ O ( m log m ) time, where $m$ m is the size of the 2-skeleton. The problem can be solved using dynamic graph connectivity. We obtain the running time by using offline graph connectivity which assumes that the deletion time of every arc inserted is known at the time of insertion. The algorithm is implemented and experimental results are given. In addition, we reduce the offline graph connectivity problem to computing the Reeb graph.     

Entries of the group inverse of the Laplacian matrix for generalized Johnson graphs

In this paper, we use graph theoretic properties of generalized Johnson graphs to compute the entries of the group inverse of Laplacian matrices for generalized Johnson graphs. We then use these entries to compute the Zenger function for the group inverse of Laplacian matrices of generalized Johnson graphs.     

Finding a Simple Polytope from Its Graph in Polynomial Time

We show that one can compute the combinatorial facets of a simple polytope from its graph in polynomial time. Our proof relies on a primal-dual characterization (by Joswig, Kaibel, and Körner in Israel J. Math. 129:109–118, 2002) and a linear program, with an exponential number of constraints, which can be used to construct the solution and can be solved in polynomial time. We show that this allows one to characterize the face lattice of the polytope, via a simple face recognition algorithm. In addition, we use this linear program to construct several interesting polynomial-time computable sets of graphs which may be of independent interest.     

Coloring Fuzzy Circular Interval Graphs

Computing the weighted coloring number of graphs is a classical topic in combinatorics and graph theory. Recently these problems have again attracted a lot of attention for the class of quasi-line graphs and more specifically fuzzy circular interval graphs.The problem is NP-complete for quasi-line graphs. For the subclass of fuzzy circular interval graphs however, one can compute the weighted coloring number in polynomial time using recent results of Chudnovsky and Ovetsky and of King and Reed. Whether one could actually compute an optimal weighted coloring of a fuzzy circular interval graph in polynomial time however was still open.We provide a combinatorial algorithm that computes weighted colorings and the weighted coloring number for fuzzy circular interval graphs efficiently. The algorithm reduces the problem to the case of circular interval graphs, then making use of an algorithm by Gijswijt to compute integer decompositions.     

Graphs,Syzygies, and Multivariate Splines

The module of splines on a polyhedral complex can be viewed as the syzygy module of its dual graph with edges weighted by powers of linear forms. When the assignment of linear forms to edges meets certain conditions, we can decompose the graph into disjoint cycles without changing the isomorphism class of the syzygy module. Thus we can use this decomposition to compute the homological dimension and the Hilbert series of the module. We provide alternate proofs of some results of Schenck and Stillman, extending those results to the polyhedral case. We also provide examples which illustrate the role that geometry plays in determining the syzygy module.     

Augmented conjugate gradient. Application in an iterative process for the solution of scattering problems

We discuss the application of an augmented conjugate gradient to the solution of a sequence of linear systems of the same matrix appearing in an iterative process for the solution of scattering problems. The conjugate gradient method applied to the first system generates a Krylov subspace, then for the following systems, a modified conjugate gradient is applied using orthogonal projections on this subspace to compute an initial guess and modified descent directions leading to a better convergence. The scattering problem is treated via an Exact Controllability formulation and a preconditioned conjugate gradient algorithm is introduced. The set of linear systems to be solved are associated to this preconditioning. The efficiency of the method is tested on different 3D acoustic problems. This revised version was published online in August 2006 with corrections to the Cover Date.     

Automatic computation of partial derivatives and rounding error estimates with applications to large-scale systems of nonlinear equations

Recently, a new approach has been proposed to efficiently compute the accurate values of partial derivatives of a function or functions, and simultaneously to estimate the rounding errors in the computed function values. In this paper the use of the method in the solution of nonlinear equations is investigated.The method makes use of the computational graph and, when applied to the evaluation of a function, traverses it from the top ( = the function node) down to the bottom ( = the input variable nodes). A remarkable analogy is observed between the partial derivatives and the shortest paths on the computational graph. The top-down traversing on the computational graph has the following advantages over the existing algorithms using the bottom-up traversing: (1) The gradient of a function can be computed within the same complexity as that of the evaluation of the function alone (the complexity being independent of the number of input variables); (2) A fairly sharp estimate of the rounding error in the function evaluation is obtained, on the basis of which a computationally meaningful norm may be introduced in the space of residuals to afford a convergence criterion for an iterative method of solving the system of nonlinear equations. As an example, a system of nonlinear equations with 108 variables for a distillation tower of a chemical plant is numerically analyzed in detail. It is shown that by the use of the proposed method we could satisfactorily resolve two main problems encountered in computing a numerical solution of the system of nonlinear equations, i.e., how to compute the accurate Jacobian matrix and when we should stop the iteration.     

Solving some NP-complete problems using split decomposition

We show how to use the split decomposition to solve some NP-hard optimization problems on graphs. We give algorithms for clique problem and domination-type problems. Our main result is an algorithm to compute a coloration of a graph using its split decomposition. Finally we show that the clique-width of a graph is bounded if and only if the clique-width of each representative graph in its split decomposition is bounded.     

Multiple edges in M. Kontsevich's graph complexes and computations of the dimensions and Euler characteristics

We provide a generating function for the (graded) dimensions of M. Kontsevich's graph complexes of ordinary graphs. This generating function can be used to compute the Euler characteristic in each loop order. Furthermore, we show that graphs with multiple edges can be omitted from these graph complexes.     

A linear time algorithm to list the minimal separators of chordal graphs

Kumar and Madhavan [Minimal vertex separators of chordal graphs, Discrete Appl. Math. 89 (1998) 155-168] gave a linear time algorithm to list all the minimal separators of a chordal graph. In this paper we give another linear time algorithm for the same purpose. While the algorithm of Kumar and Madhavan requires that a specific type of PEO, namely the MCS PEO is computed first, our algorithm works with any PEO. This is interesting when we consider the fact that there are other popular methods such as Lex BFS to compute a PEO for a given chordal graph.     

Linear flows and Morse graphs: Topological consequences in low dimensions

The main aim of this paper is to show some specific connections between linear dynamic and graphs. Precisely, the Morse decomposition of a linear flow on the Grassmannians induces a directed graph. We apply the results appearing in Ayala et al. (2006, 2005)  and  and Colonius et al. (2002) [4] and compute the associated graphs for linear flows in dimensions two and three.     

t-Pebbling and Extensions

Graph pebbling is the study of moving discrete pebbles from certain initial distributions on the vertices of a graph to various target distributions via pebbling moves. A pebbling move removes two pebbles from a vertex and places one pebble on one of its neighbors (losing the other as a toll). For t ≥ 1 the t-pebbling number of a graph is the minimum number of pebbles necessary so that from any initial distribution of them it is possible to move t pebbles to any vertex. We provide the best possible upper bound on the t-pebbling number of a diameter two graph, proving a conjecture of Curtis et al., in the process. We also give a linear time (in the number of edges) algorithm to t-pebble such graphs, as well as a quartic time (in the number of vertices) algorithm to compute the pebbling number of such graphs, improving the best known result of Bekmetjev and Cusack. Furthermore, we show that, for complete graphs, cycles, trees, and cubes, we can allow the target to be any distribution of t pebbles without increasing the corresponding t-pebbling numbers; we conjecture that this behavior holds for all graphs. Finally, we explore fractional and optimal fractional versions of pebbling, proving the fractional pebbling number conjecture of Hurlbert and using linear optimization to reveal results on the optimal fractional pebbling number of vertex-transitive graphs.     

Numerical computation of the finite-genus solutions of the Korteweg–de Vries equation via Riemann–Hilbert problems

In this letter we describe how to compute the finite-genus solutions of the Korteweg–de Vries equation using a Riemann–Hilbert problem that is satisfied by the Baker–Akhiezer function corresponding to a Schrödinger operator with finite-gap spectrum. The recovery of the corresponding finite-genus solution is performed using the asymptotics of the Baker–Akhiezer function. This method has the benefit that the space and time dependence of the Baker–Akhiezer function appear in an explicit, linear and computable way. We make use of recent advances in the numerical solution of Riemann–Hilbert problems to produce an efficient and uniformly accurate numerical method for computing all finite-genus solutions of the KdV equation.     

Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation

We generalize the linear-time shortest-paths algorithm for planar graphs with nonnegative edge-weights of Henzinger et al. (1994) to work for any proper minor-closed class of graphs. We argue that their algorithm can not be adapted by standard methods to all proper minor-closed classes. By using recent deep results in graph minor theory, we show how to construct an appropriate recursive division in linear time for any graph excluding a fixed minor and how to transform the graph and its division afterwards, so that it has maximum degree three. Based on such a division, the original framework of Henzinger et al. can be applied. Afterwards, we show that using this algorithm, one can implement Mehlhorn’s (1988) 2-approximation algorithm for the Steiner tree problem in linear time on these graph classes.