Search

The characterization of all the constraint satisfaction problems solvable by local consistency checking (also known as CSPs of bounded width) was proposed by Feder and Vardi [SIAM J. Comput., 28 (1998), pp. 57104]. It was confirmed by two independent proofs by Bulatov [Bounded Relational Width, manuscript, 2009] and Barto and Kozik [L. Barto and M. Kozik, 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, pp. 595 603], [L. Barto and M. Kozik, J. ACM, 61 (2014), 3]. Later Barto [J. Logic Comput., 26 (2014), pp. 923 943] proved a collapse of the hierarchy of local consistency notions by showing that (2; 3) minimality solves all the CSPs of bounded width. In this paper we present a new consistency notion, jpq consistency, which also solves all the CSPs of bounded width. Our notion is strictly weaker than (2; 3) consistency, (2; 3) minimality, path consistency, and singleton arc consistency (SAC). This last fact allows us to answer the question of Chen, Dalmau, and Gruien [J. Logic Comput., 23 (2013), pp. 87 108] by confirming that SAC solves all the CSPs of bounded width. Moreover, as known algorithms work faster for SAC, the result implies that CSPs of bounded width can be, in practice, solved more efficiently. The definition of jpq consistency is closely related to a consistency condition obtained from the rounding of an SDP relaxation of a CSP instance. In fact, the main result of this paper is used by Dalmau et al. [Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, ACM, New York, 2017, pp. 340{357] to show that CSPs with near unanimity polymorphisms admit robust approximation algorithms with polynomial loss. Finally, an algebraic characterization of some term conditions satisfied in algebras associated with templates of bounded width, first proved by Brady, is a direct consequence of our result. [ABSTRACT FROM AUTHOR]

This paper introduces the notion of a weighted complementarity problem (wCP), which consists of finding a pair of vectors (x, s) belonging to the intersection of a manifold with a cone such that their product in a certain algebra, x o s, equals a given weight vector w. When w is the zero vector, then wCP reduces to a complementarity problem. The motivation for introducing the more general notion of a wCP lies in the fact that several equilibrium problems in economics can be formulated in a natural way as wCPs. Moreover, those formulations lend themselves to the development of highly efficient algorithms for solving the corresponding equilibrium problems. For example, Fisher's competitive market equilibrium model can be formulated as a wCP that can be efficiently solved by interior-point methods. Moreover, it is shown that the quadratic programming and weighted centering problem, which generalizes the notion of a linear programming and weighted centering problem recently proposed by Anstreicher, can be formulated as a special linear monotone wCP. The main contribution of the paper is to introduce and analyze two interior-point methods for solving general monotone linear wCPs. [ABSTRACT FROM AUTHOR]

A common thread in all of the recent results concerning the testing of dense graphs is the use of Szemerédi's regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first result is that the property defined by having any given Szemerédi-partition is testable with a constant number of queries. Our second and main result is a purely combinatorial characterization of the graph properties that are testable with a constant number of queries. This characterization (roughly) says that a graph property P can be tested with a constant number of queries if and only if testing P can be reduced to testing the property of satisfying one of finitely many Szemerédi-partitions. This means that in some sense, testing for Szemerédi-partitions is as hard as testing any testable graph property. We thus resolve one of the main open problems in the area of property-testing, which was first raised by Goldreich, Goldwasser, and Ron [J. ACM, 45 (1998), pp. 653-750] in the paper that initiated the study of graph property-testing. This characterization also gives an intuitive explanation as to what makes a graph property testable. [ABSTRACT FROM AUTHOR]

In this paper we describe a method for continuing periodic solution bifurcations in periodic delay-differential equations. First, the notion of characteristic matrices of periodic orbits is introduced and equivalence with the monodromy operator is demonstrated. An alternative formulation of the characteristic matrix is given, which can be computed efficiently. Defining systems of bifurcations are constructed in a standard way, including the characteristic matrix and its derivatives. For following bifurcation curves in two parameters, the pseudo-arclength method is used combined with Newton iteration. Two test examples (an interrupted machining model and a traffic model with driver reaction time) conclude the paper. The algorithm has been implemented in the software tool PDDE-CONT. [ABSTRACT FROM AUTHOR]

We consider approximation algorithms for the metric labeling problem. This problem was introduced in a paper by Kleinberg and Tardos [J. ACM, 49 (2002), pp. 616630] and captures many classification problems that arise in computer vision and related fields. They gave an O(log k log log k) approximation for the general case, where k is the number of labels, and a 2-approximation for the uniform metric case. (In fact, the bound for general metrics can be improved to O(log k) by the work of Fakcheroenphol, Rao, and Talwar [Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 448455].) Subsequently, Gupta and Tardos [Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, 2000, pp. 652658] gave a 4-approximation for the truncated linear metric, a metric motivated by practical applications to image restoration and visual correspondence. In this paper we introduce an integer programming formulation and show that the integrality gap of its linear relaxation either matches or improves the ratios known for several cases of the metric labeling problem studied until now, providing a unified approach to solving them. In particular, we show that the integrality gap of our linear programming (LP) formulation is bounded by O(log k) for a general k-point metric and 2 for the uniform metric,thus matching the known ratios. We also develop an algorithm based on our LP formulation that achieves a ratio of 2 + √2≅ 3.414 for the truncated linear metric improving the earlier known ratio of 4. Our algorithm uses the fact that the integrality gap of the LP formulation is 1 on a linear metric. [ABSTRACT FROM AUTHOR]

This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming (SDP) obtained from centrality equations of the form X½ SX½ = vW, where W is a fixed positive definite matrix and v>0 is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. It is shown that a weighted central path as a function of √v can be extended analytically beyond 0 and hence that the path converges as v↓0. Characterization of the limit points of the path and its normalized first-order derivatives are also provided. As a consequence, it is shown that a weighted central path can have two types of behavior: it converges either as &Tetha;(v) or asT &Tetha;(√v) depending on whether the matrix W on a certain scaled space is block diagonal or not, respectively. We also derive an error bound on the distance between a point lying in a certain neighborhood of the central path and the set of primal-dual optimal solutions. Finally, in light of the results of this paper, we give a characterization of a sufficient condition proposed by Potra and Sheng which guarantees the superlinear convergence of a class of primal-dual interior-point SDP algorithms. [ABSTRACT FROM AUTHOR]

Let M be a 2 × 2 matrix of Laurent polynomials with real coefficients and symmetry. In this paper, we obtain a necessary and sufficient condition for the existence of four Laurent polynomials (or finite-impulse-response filters) u1, u2, v1, v2 with real coefficients and symmetry such that [This symbol cannot be presented in ASCII format] and [Su1](z)[Sv2](z) = [Su2](z)[Sv1](z), where [Sp](z) = p(z)/p(1/z) for a nonzero Laurent polynomial p. Our criterion can be easily checked and a step-by-step algorithm will be given to construct the symmetric filters u1, u2, v1, v2. As an application of this result to symmetric framelet filter banks, we present a necessary and sufficient condition for the construction of a symmetric multiresolution analysis tight wavelet frame with two compactly supported generators derived from a given symmetric refinable function. Once such a necessary and sufficient condition is satisfied, an algorithm will be used to construct a symmetric framelet filter bank with two high-pass filters which is of interest in applications such as signal denoising and image processing. As an illustration of our results and algorithms in this paper, we give several examples of symmetric framelet filter banks with two highpass filters which have good vanishing moments and are derived from various symmetric low-pass filters including some B-spline filters. [ABSTRACT FROM AUTHOR]

In (SIAM J. Matrix Anal. Appl., 23 (2002), pp. 706–727, we developed numerical algorithms for computing sparse low-rank approximations of matrices, and we also provided a detailed error analysis of the proposed algorithms together with some numerical experiments. The low-rank approximations are constructed in a certain factored form with the degree of sparsity of the factors controlled by some user-specified parameters. In this paper, we cast the sparse low-rank approximation problem in the framework of penalized optimization problems. We discuss various approximation schemes for the penalized optimization problem which are more amenable to numerical computations. We also include some analysis to show the relations between the original optimization problem and the reduced one. We then develop a globally convergent discrete Newton-like iterative method for solving the approximate penalized optimization problems. We also compare the reconstruction errors of the sparse low-rank approximations computed by our new methods with those obtained using the methods in the earlier paper and several other existing methods for computing sparse low-rank approximations. Numerical examples show that the penalized methods are more robust and produce approximations with factors which have fewer columns and are sparser. [ABSTRACT FROM AUTHOR]

A new fully variational approach is studied for elliptic grid generation (EGG). It is based on a general algorithm developed in a companion paper [A. L. Codd, T. A. Manteuffel, and S. F. McCormick, SIAM I Numer. Anal., 41 (2003), pp. 2197-2209] that involves using Newton's method to linearize an appropriate equivalent first-order system, first-order system least squares (FOSLS) to formulate and discretize the Newton step, and algebraic multigrid (AMG) to solve the resulting matrix equation. The approach is coupled with nested iteration to provide an accurate initial guess for finer levels using coarse-level computation. The present paper verifies the assumptions of the companion work and confirms the overall efficiency of the scheme with numerical experiments. [ABSTRACT FROM AUTHOR]

In the ring loading problem, traffic demands are given for each pair of nodes in an undirected ring network and a flow is routed in either of two directions, clockwise and counterclockwise. The load of an edge is the sum of the flows routed through the edge and the objective of the problem is to minimize the maximum load on the ring. Myung [J. Korean OR and MS Society, 23 (1998), pp. 49–62 (in Korean)] has presented an efficient algorithm for solving a problem where flow is restricted to integers. However, the proof for the validity of the algorithm in their paper is long and complicated and as the paper is written in Korean, its accessibility is very limited. In this paper, we slightly modify their algorithm and provide a simple proof for the correctness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper we study the inversion of an analytic matrix valued function A(z). This problem can also be viewed as an analytic perturbation of the matrix A0 = A(0). We are mainly interested in the case where A0 is singular but A(z) has an inverse in some punctured disc around z = 0. It is known that A-1 (z) can be expanded as a Laurent series at the origin. The main purpose of this paper is to provide efficient computational procedures for the coefficients of this series. We demonstrate that the proposed algorithms are computationally superior to symbolic algebra when the order of the pole is small. [ABSTRACT FROM AUTHOR]

The implicitly shifted (bulge-chasing) QZ algorithm is the most popular method for solving the generalized eigenvalue problem Av = λBv. This paper explains why the QZ algorithm functions well even in the presence of infinite eigenvalues. The key to rapid convergence of QZ (and QR) algorithms is the effective transmission of shifts during the bulge chase. In this paper the mechanism of transmission of shifts is identified, and it is shown that this mechanism is not disrupted by the presence of infinite eigenvalues. Both the QZ algorithm and the preliminary reduction to Hessenberg-triangular form tend to push the infinite eigenvalues toward the top of the pencil. Thus they should be deflated at the top. [ABSTRACT FROM AUTHOR]

This paper discusses convergence behavior of the nonlinear inexact Uzawa algorithm for solving saddle-point problems presented in a recent paper of Bramble, Pasciak, and Vassilev (SIAM J. Numer. Anal., 34 (1997), pp. 1072­1092). It is shown that this algorithm converges under a condition weaker than that stated in their paper. Key words: saddle-point problems; nonlinear inexact Uzawa algorithm; convergence behavior [ABSTRACT FROM AUTHOR]

In an earlier paper, we developed a new formulation of the shallow-water equations on the sphere, based on the semi-Lagrangian advection of potential vorticity. An important feature of our two-time-level model is that forward extrapolation of the nonlinear terms is avoided. In this paper, we develop a multigrid algorithm for solving the resulting system of three coupled nonlinear equations. We include a discussion of basic multigrid methods, along with some more advanced techniques required for the development of the multigrid scheme for this system. Results are presented showing that usual optimal multigrid efficiency is obtained. [ABSTRACT FROM AUTHOR]

This paper considers an implicitly restarted Krylov subspace method that approximates a stable, linear transfer function f(s) of order n by one of order m, where n >> m. It is well known that oblique projections onto a Krylov subspace may generate unstable partial realizations. To remedy this situation, the oblique projectors obtained via classical Krylov subspace methods are supplemented with further projectors which enable the formation of stable partial realizations directly from f(s). A key feature of this process is that it may be incorporated into an implicit restart scheme. A second difficulty arises from the fact that Krylov subspace methods often generate partial realizations that contain nonessential modes. To this end, balanced truncation may be employed to discard the unwanted part of the reduced-order model. This paper proposes oblique projection methods for large-scale model reduction that simultaneously compute stable reduced-order models while discarding all nonessential modes. It is shown that both of these tasks may be effected by a single oblique projection process. Furthermore, the process is shown to naturally fit into an implicit restart framework. The theoretical properties of these methods are thoroughly investigated, and exact low-dimensional expressions for the L∞-norm of the residual errors are derived. Finally, the behavior of the algorithm is illustrated on two large-scale examples. [ABSTRACT FROM AUTHOR]

For a queueing system with a low traffic intensity, the expected number of customers in the queue is small. However, with a bursty input process, long queues may build up in a short time. In this paper, we study light traffic queueing systems with bursty input processes. We study the distributions of queue lengths, waiting times, busy and active periods, and their corresponding expansions when the traffic intensity is small. Special attention goes to some conditional distributions of queue lengths, waiting times, and system-active periods. The expansions given in this paper provide a potential asymptotic approach to the computation of various descriptors of queueing sys- tems. The coefficients of those expansions reflect some important features of episodic queues. We also report numerical results which give a graphic view of our approximations and of the effect of the burstiness of the input and service processes on the queues. [ABSTRACT FROM AUTHOR]

Teaching linear algebra routines for computing eigenvalues of a matrix can be well motivated for students by using interesting examples. We propose in this paper to use vibrating plates for two reasons: First, they have many interesting applications, from which we chose the Chladni figures, representing sand ornaments which form on a vibrating plate, and the Tacoma Bridge, one of the most spectacular bridge failures. Second, the partial differential operator that arises from vibrating plates is the biharmonic operator, which one does not encounter often in a first course on numerical partial differential equations, and which is more challenging to discretize than the standard Laplacian seen in most textbooks. In addition, the history of vibrating plates is interesting, and we will show both spectral discretizations, leading to small dense matrix eigenvalue problems, and a finite difference discretization, leading to large scale sparse matrix eigenvalue problems. Hence both the QR-algorithm and Lanczos can be well illustrated. [ABSTRACT FROM AUTHOR]

In this paper we propose an efficient method for solving the spherically constrained homogeneous polynomial optimization problem. The new approach has the following three main ingredients. First, we establish a block coordinate descent type search method for nonlinear optimization, with the novelty being that we accept only a block update that achieves the maximum improvement, hence the name of our new search method: maximum block improvement (MBI). Convergence of the sequence produced by the MBI method to a stationary point is proved. Second, we establish that maximizing a homogeneous polynomial over a sphere is equivalent to its tensor relaxation problem; thus we can maximize a homogeneous polynomial function over a sphere by its tensor relaxation via the MBI approach. Third, we propose a scheme to reach a KKT point of the polynomial optimization, provided that a stationary solution for the relaxed tensor problem is available. Numerical experiments have shown that our new method works very efficiently: for a majority of the test instances that we have experimented with, the method finds the global optimal solution at a low computational cost. [ABSTRACT FROM AUTHOR]

Amit, Linial, and Matoušek [Random Struct. Algorithms, 20 (2001), pp. 1-22] have raised the following question: Is the chromatic number of random h-lifts of K5 asymptotically (for h→∞) almost surely (a.a.s.) equal to a single number? In this paper, we offer the following partial result: The chromatic number of a random lift of K5\e is a.a.s. 3. [ABSTRACT FROM AUTHOR]

In this paper we propose two modifications to Nesterov's algorithms for minimizing convex functions in relative scale. The first is based on a bisection technique and leads to improved theoretical iteration complexity, and the second is a heuristic for avoiding restarting behavior. The fastest of our algorithms produces a solution within relative error O(1/k) of the optimum, with k being the iteration counter. [ABSTRACT FROM AUTHOR]

A polynomial transform is the multiplication of an input vector x ∈ ℂn by a matrix Pb, α ∈ ℂn x n, whose (k, l)th element is defined as pl(αk) for polynomials pl(x) ∈ ℂ[x] from a list b = {p0(x), …, pn-1(x)} and sample points αk ∈ ℂ from a list α = {α0, …, αn-1}. Such transforms find applications in the areas of signal processing, data compression, and function interpolation. An important example includes the discrete Fourier transform. In this paper we introduce a novel technique to derive fast algorithms for polynomial transforms. The technique uses the relationship between polynomial transforms and the representation theory of polynomial algebras. Specifically, we derive algorithms by decomposing the regular modules of these algebras as a stepwise induction. As an application, we derive novel O(n log n) general-radix algoritlims for the discrete Fourier transform and the discrete cosine transform of type 4. [ABSTRACT FROM AUTHOR]

We show that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are W[1]-hard parameterized by clique-width. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, that is, solvable in time g(k) · nO(1) on n-vertex graphs of clique-width k, where g is some function of k only. Our results imply that the running time O(nf(k)) of many clique-widthbased algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely FPT ≠ W[1]). [ABSTRACT FROM AUTHOR]

We study the maximum edge-disjoint paths problem in undirected planar graphs: given a graph G and node pairs (demands) s1t1, s2t2, … , sktk, the goal is to maximize the number of demands that can be connected (routed) by edge-disjoint paths. The natural multicommodity flow relaxation has an Ω(√n) integrality gap, where n is the number of nodes in G. Motivated by this, we consider solutions with small constant congestion c > 1, that is, solutions in which up to c paths are allowed to use an edge (alternatively, each edge has a capacity of c). In previous work we obtained an O(log n) approximation with congestion 2 via the flow relaxation. This was based on a method of decomposing into well-linked subproblems. In this paper we obtain an O(1) approximation with congestion 4. To obtain this improvement we develop an alternative decomposition that is specific to planar graphs. The decomposition produces instances that we call Okamura-Seymour (OS) instances. These have the property that all terminals lie on a single face. Another ingredient we develop is a constant factor approximation for the all-or-nothing flow problem on OS instances via the flow relaxation. [ABSTRACT FROM AUTHOR]

Suffix trees and suffix arrays are the most prominent full-text indices, and their construction algorithms are well studied. In the literature, the fastest algorithm runs in O(n) time, while it requires O(n log n)-bit working space, where n denotes the length of the text. On the other hand, the most space-efficient algorithm requires O(n)-bit working space while it runs in O(n log n) time. It was open whether these indices can be constructed in both o(n log n) time and o(n log n)- bit working space. This paper breaks the above time-and-space barrier under the unit-cost word RAM. We give an algorithm for constructing the suffix array, which takes O(n) time and O(n)-bit working space, for texts with constant-size alphabets. Note that both the time and the space bounds are optimal. For constructing the suffix tree, our algorithm requires O(n logϵ n) time and O(n)-bit working space for any 0 < ϵ < 1. Apart from that, our algorithm can also be adopted to build other existing full-text indices, such as compressed suffix tree, compressed suffix arrays, and FM-index. We also study the general case where the size of the alphabet Σ is not constant. Our algorithm can construct a suffix array and a suffix tree using optimal O(n log ∣Σ∣)-bit working space while running in O(n log log ∣Σ∣) time and O(n(logϵ n + log ∣Σ∣)) time, respectively. These are the first algorithms that achieve o(n log n) time with optimal working space. Moreover, for the special case where log ∣Σ∣ = O((log log n)1-ϵ), we can speed up our suffix array construction algorithm to the optimal O(n). [ABSTRACT FROM AUTHOR]

In this paper, an optimal linear-time algorithm is presented to solve the haplotype inference problem for pedigree data when there are no recombinations and the pedigree has no mating loops. The approach is based on the use of graphs to capture SNP, Mendelian, and parity constraints of the given pedigree. This representation allows us to capture the constraints as the edges in a graph, rather than as a system of linear equations as in previous approaches. Graph traversals are then used to resolve the parity of these edges, resulting in an optimal running time. [ABSTRACT FROM AUTHOR]

A glued matrix can be obtained from a direct sum of p copies of an unreduced symmetric tridiagonal matrix T by modifying the junctions by a glue ?, in one of two ways, so that the new tridiagonal matrix has no zero off-diagonal entries. Despite being unreduced, a glued matrix can have some eigenvalues agreeing to hundreds of decimal places. This makes glued matrices practically useful as test matrices for tridiagonal eigensolvers such as inverse iteration and the MRRR algorithm. However, the eigenvalue distribution of a glued matrix is a fascinating subject of theoretical interest in its own right. By means of secular equations, this paper studies how width and placement of the eigenvalue clusters of a glued matrix depend on T, on p, and on γ. Interlacing properties and the question of eigenvalue repetition between T and a glued matrix are also investigated. [ABSTRACT FROM AUTHOR]

Real nonsymmetric tridiagonal matrices arise in various applications. When one is asked to find the eigenvalues of such a matrix, the QR algorithm is used, but this destroys tridiagonal form by converting the matrix to Hessenberg form, resulting in increased storage requirements and numerical operations. The HR algorithm, based on the HR factorization of the matrix into a (Δ,Δ1)-orthogonal part H, where HTΔH = Δ1, and an upper triangular part R, solves this problem. In a result proved by Hongguo Xu, two steps of the LR algorithm are equivalent to one step of the QR algorithm for symmetric matrices. The first object of this paper is to use the HR algorithm to extend Hongguo Xu's result to the nonsymmetric case. Since an HR factorization does not always exist, so we also consider an extension to it called XHR factorization. We then prove a similar result about it. [ABSTRACT FROM AUTHOR]

Minimal elimination orderings were introduced by Rose, Tarjan, and Lueker in 1976, and during the last decade they have received increasing attention. Such orderings have important applications in several different fields, and they were first studied in connection with minimizing fill in sparse matrix computations. Rather than computing any minimal ordering, which might result in fill that is far from minimum, it is more desirable for practical applications to start from an ordering produced by a fill-reducing heuristic and then compute a minimal fill that is a subset of the fill produced by the given heuristic. This problem has been addressed previously, and there are several algorithms for solving it. The drawback of these algorithms is that either there is no theoretical bound given on their running time, although they might run fast in practice, or they have a good theoretical running time, but they have never been implemented, or they require a large machinery of complicated data structures to achieve the good theoretical time bound. In this paper, we present an algorithm called MCS-ETree for solving the mentioned problem in O(nm A(m, n)) time, where m and n are, respectively, the number of edges and vertices of the graph corresponding to the input sparse matrix and A(m, n) is the very slowly growing inverse of Ackerman's function. A primary strength of MCS-ETree is its simplicity and its straightforward implementation details. We present run time test results to show that our algorithm is fast in practice. Thus our algorithm is the first that both has a provably good running time with easy implementation details and is fast in practice. [ABSTRACT FROM AUTHOR]

In an orthogonal drawing of a planar graph G, each vertex is drawn as a point, each edge is drawn as a sequence of alternate horizontal and vertical line segments, and any two edges do not cross except at their common end. A bend is a point where an edge changes its direction. A drawing of G is called an optimal orthogonal drawing if the number of bends is minimum among all orthogonal drawings of G. In this paper we give an algorithm to find an optimal orthogonal drawing of any given series-parallel graph of the maximum degree at most three. Our algorithm takes linear time, while the previously known best algorithm takes cubic time. Furthermore, our algorithm is much simpler than the previous one. We also obtain a best possible upper bound on the number of bends in an optimal drawing. [ABSTRACT FROM AUTHOR]

Graph searching is perhaps one of the simplest and most widely used tools in graph algorithms. Despite this, few theoretical results are known about the vertex orderings that can be produced by a specific search algorithm. A simple characterizing property, such as is known for LexBFS, can aid greatly in devising algorithms, writing proofs of correctness, and showing impossibility results. This paper unifies our view of graph search algorithms by showing simple, closely related characterizations of various well-known search paradigms, including BFS and DFS. Furthermore, these characterizations naturally lead to other search paradigms, namely, maximal neighborhood search and LexDFS. [ABSTRACT FROM AUTHOR]

In this paper we develop a posteriori error estimates for finite element discretization of elliptic optimization problems with pointwise inequality constraints on the control variable. We derive error estimators for assessing the discretization error with respect to the cost functional as well as with respect to a given quantity of interest. These error estimators provide quantitative information about the discretization error and guide an adaptive mesh refinement algorithm allowing for substantial saving in degrees of freedom. The behavior of the method is demonstrated on numerical examples. [ABSTRACT FROM AUTHOR]

It is well known that the nonlinear filtering problem has important applications in both military and commercial industries. The central problem of nonlinear filtering is to solve the Duncan-Mortensen-Zakai (DMZ) equation in real time and in a memoryless manner. The purpose of this paper is to show that, under very mild conditions (which essentially say that the growth of the observation ∣h∣ is greater than the growth of the drift ∣f∣), the DMZ equation admits a unique nonnegative weak solution u which can be approximated by a solution uR of the DMZ equation on the ball BR with uR ∣ θBR = 0. The error of this approximation is bounded by a function of R which tends to zero as R goes to infinity. The solution uR can in turn be approximated efficiently by an algorithm depending only on solving the observation-independent Kolmogorov equation on BR. In theory, our algorithm can solve basically all engineering problems in real time. Specifically, we show that the solution obtained from our algorithms converges to the solution of the DMZ equation in the L1 sense. Equally important, we have a precise error estimate of this convergence, which is important in numerical computation. [ABSTRACT FROM AUTHOR]

Abstract. We consider the problem of embedding weighted hyperedges of a hypergraph as paths in a cycle on the same number of vertices, such that the maximum congestion of any physical link of the cycle is minimized. The problem, called weighted hypergraph embedding in a cycle (WHEC), is known to be NP-complete even when each hyperedge is unweighted or each weighted hyperedge contains exactly two vertices. In this paper, we propose an improved rounding algorithm for the WHEC problem to provide a solution with an approximation bound of 1.5{opt +Wmax), where opt represents the optimal value of the problem and Wmax denotes the largest weight of hyperedges. For any fixed ∈ > 0, we also present a polynomial time algorithm to provide an embedding whose congestion is at most {1.5 + ∈) times the optimum. This improves previous results for the general WHEC problem. [ABSTRACT FROM AUTHOR]

This paper investigates the Kronecker canonical form of matrix pencils under the genericity assumption that the set of nonzero entries is algebraically independent. We provide a combinatorial characterization of the sums of the row/column indices supported by efficient bipartite matching algorithms. We also give a simple alternative proof for a theorem of Poljak on the generic ranks of matrix powers. [ABSTRACT FROM AUTHOR]

This paper considers the problem of reconstructing a piecewise smooth model function from given, measured data. The data are compared to a field which is given as a possibly nonlinear function of the model. A regularization functional is added which incorporates the a priori knowledge that the model function is piecewise smooth and may contain jump discontinuities. Regularization operators related to total variation (TV) are therefore employed. Two popular methods are modified TV and Huber's function. Both contain a parameter which must be selected. The Huber variant provides a more natural approach for selecting its parameter, and we use this to propose a scheme for both methods. Our selected parameter depends both on the resolution and on the model average roughness; thus, it is determined adaptively. Its variation from one iteration to the next yields additional information about the progress of the regularization process. The modified TV operator has a smoother generating function; nonetheless we obtain a Huber variant with comparable, and occasionally better, performance. For large problems (e.g., high resolution) the resulting reconstruction algorithms can be tediously slow. We propose two mechanisms to improve efficiency. The first is a multilevel continuation approach aimed mainly at obtaining a cheap yet good estimate for the regularization parameter and the solution. The second is a special multigrid preconditioner for the conjugate gradient algorithm used to solve the linearized systems encountered in the procedures for recovering the model function. [ABSTRACT FROM AUTHOR]

This paper presents a multigrid method for solving variable coefficient Maxwell's equations. The novelty in this method is the use of interpolation operators that do not produce multilevel commutativity complexes that lead to multilevel exactness. Rather, the effects of multilevel exactness are built into the level equations themselves—on the finest level using a discrete T – V formulation and on the coarser grids through the Galerkin coarsening procedure of a T – V formulation. These built-in structures permit the levelwise use of an effective hybrid smoother on the curl-free near-nullspace components and permit the development of interpolation operators for handling the curl-free and divergence-free error components separately. The resulting block-diagonal interpolation operator does not satisfy multilevel commutativity but has good approximation properties for both of these error components. Applying operator-dependent interpolation for each of these error components leads to an effective multigrid scheme for variable coefficient Maxwell's equations, where multilevel commutativity-based methods can degrade. Numerical results are presented to verify the effectiveness of this new scheme. [ABSTRACT FROM AUTHOR]

We propose a new algebraic multigrid (AMG) method for solving the eddy current approximations to Maxwell's equations. This AMG method has its roots in an algorithm proposed by Reitzinger and Schöberl. The main focus in the Reitzinger and Schöberl method is to maintain null-space properties of the weak ∇ × ∇ × operator on coarse grids. While these null-space properties are critical, they are not enough to guarantee h-independent convergence rates of the overall multigrid scheme. We present a new strategy for choosing intergrid transfers that not only maintains the important null-space properties on coarse grids but also yields significantly improved multigrid convergence rates. This improvement is related to those we explored in a previous paper, but is fundamentally simpler, easier to compute, and performs better with respect to both multigrid operator complexity and convergence rates. The new strategy builds on ideas in smoothed aggregation to improve the approximation property of an existing interpolation operator. By carefully choosing the smoothing operators, we show how it is sometimes possible to achieve h-independent convergence rates with a modest increase in multigrid operator complexity. Though this ideal case is not always possible, the overall algorithm performs significantly better than the original scheme in both iterations and run time. Finally, the Reitzinger and Schöberl method, as well as our previous smoothed method, are shown to be special cases of this new algorithm. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of testing whether a large matrix X has a prescribed structure by looking at the magnitude of a displacement matrix D(X) associated with the structure. We provide parameters on the basis of which one can judge whether the problem is well-conditioned or ill-conditioned. It turns out that even for very general structures it is the minimal eigenvalues of positive definite and banded Toeplitz matrices that are the most important of these parameters. [ABSTRACT FROM AUTHOR]

In the early eighties Lojasiewicz [in Seminari di Geometria 1982-1983, Università di Bologna, Istituto di Geometria, Dipartimento di Matematica, 1984, pp. 115--117] proved that a bounded solution of a gradient flow for an analytic cost function converges to a well-defined limit point. In this paper, we show that the iterates of numerical descent algorithms, for an analytic cost function, share this convergence property if they satisfy certain natural descent conditions. The results obtained are applicable to a broad class of optimization schemes and strengthen classical "weak convergence" results for descent methods to "strong limit-point convergence" for a large class of cost functions of practical interest. The result does not require that the cost has isolated critical points and requires no assumptions on the convexity of the cost nor any nondegeneracy conditions on the Hessian of the cost at critical points. [ABSTRACT FROM AUTHOR]

In this paper we propose a new class of primal-dual path-following interior point algorithms for solving monotone linear complementarity problems. At each iteration, the method would select a target on the central path with a large update from the current iterate, and then the Newton method is used to get the search directions, followed by adaptively choosing the step sizes, which are, e.g., the largest possible steps before leaving a neighborhood that is as wide as the given ${\cal N}^-_{\infty}$ neighborhood. The only deviation from the classical approach is that we treat the classical Newton direction as the sum of two other directions, corresponding to, respectively, the negative part and the positive part of the right-hand side. We show that if these two directions are equipped with different and appropriate step sizes, then the method enjoys the low iteration bound of $O(\sqrt{n}\log L)$, where $n$ is the dimension of the problem and $L=\frac{(x^0)^Ts^0}{\ep}$ with $\ep$ the required precision and $(x^0,s^0)$ the initial interior solution. For a predictor-corrector variant of the method, we further prove that, besides the predictor steps, each corrector step also reduces the duality gap by a rate of $1-1/O(\sqrt{n})$. Additionally, if the problem has a strict complementary solution, then the predictor steps converge Q-quadratically. [ABSTRACT FROM AUTHOR]

During the last ten years, Dhillon and Parlett devised a new algorithm (multiple relatively robust representations (MRRR)) for computing numerically orthogonal eigenvectors of a symmetric tridiagonal matrix $T$ with $\mathcal{O}(n^2)$ cost. It has been incorporated into LAPACK version 3.0 as routine {\sc stegr}. We have discovered that the MRRR algorithm can fail in extreme cases. Sometimes eigenvalues agree to working accuracy and MRRR cannot compute orthogonal eigenvectors for them. In this paper, we describe and analyze these failures and various remedies. [ABSTRACT FROM AUTHOR]

Kernel-based linear-threshold algorithms, such as support vector machines and Perceptron-like algorithms, are among the best available techniques for solving pattern classification problems. In this paper, we describe an extension of the classical Perceptron algorithm, called second-order Perceptron, and analyze its performance within the mistake bound model of on-line learning. The bound achieved by our algorithm depends on the sensitivity to second-order data information and is the best known mistake bound for (efficient) kernel-based linear-threshold classifiers to date. This mistake bound, which strictly generalizes the well-known Perceptron bound, is expressed in terms of the eigenvalues of the empirical data correlation matrix and depends on a parameter controlling the sensitivity of the algorithm to the distribution of these eigenvalues. Since the optimal setting of this parameter is not known a priori, we also analyze two variants of the second-order Perceptron algorithm: one that adaptively sets the value of the parameter in terms of the number of mistakes made so far, and one that is parameterless, based on pseudoinverses. [ABSTRACT FROM AUTHOR]

Property testing is a relaxation of classical decision problems which aims at distinguishing between functions having a predetermined property and functions being far from any function having the property. In this paper we present a novel framework for analyzing property testing algorithms. Our framework is based on a connection of property testing and a new class of problems which we call abstract combinatorial programs. We show that if the problem of testing a property can be reduced to an abstract combinatorial program of small dimension, then the property has an efficient tester. We apply our framework to a variety of problems. We present efficient property testing algorithms for geometric clustering problems, for the reversal distance problem, and for graph and hypergraph coloring problems. We also prove that, informally, any hereditary graph property can be efficiently tested if and only if it can be reduced to an abstract combinatorial program of small size. Our framework allows us to analyze all our testers in a unified way, and the obtained complexity bounds either match or improve the previously known bounds. Furthermore, even if the asymptotic complexity of the testers is not improved, the obtained proofs are significantly simpler than the previous ones. We believe that our framework will help to understand the structure of efficiently testable properties. [ABSTRACT FROM AUTHOR]

Many eigenvalue problems are most naturally viewed as product eigenvalue problems. The eigenvalues of a matrix A are wanted, but A is not given explicitly. Instead it is presented as a product of several factors: A = Ak Ak-1 ... A1. Usually more accurate results are obtained by working with the factors rather than forming A explicitly. For example, if we want eigenvalues/vectors of BT B, it is better to work directly with B and not compute the product. The intent of this paper is to demonstrate that the product eigenvalue problem is a powerful unifying concept. Diverse examples of eigenvalue problems are discussed and formulated as product eigenvalue problems. For all but a couple of these examples it is shown that the standard algorithms for solving them are instances of a generic GR algorithm applied to a related cyclic matrix. [ABSTRACT FROM AUTHOR]

This paper is concerned with the classification of families of graphs T with the following property: For any graph G, the subsets of vertices of G that can be saturated by packing copies of graphs from T form a collection of independent sets of a matroid. From this point of view, we present a characterization of so-called EHP-families of graphs (i.e., families consisting of K2, hypomatchable graphs, and propellers). The main result is the following: For a matroid-inducing EHP-family T , we characterize connected graphs H such that the family T U {H} is also matroidinducing. [ABSTRACT FROM AUTHOR]

Recently, D. Corneil found a simple 3-sweep lexicographic breadth first search (LexBFS) algorithm for the recognition of proper interval graphs. We point out how to modify Corneil's algorithm to make it a certifying algorithm, and then describe a similar certifying 3-sweep LexBFS algorithm for the recognition of proper interval bigraphs. It follows from an earlier paper that the class of proper interval bigraphs is equal to the better known class of bipartite permutation graphs, and so we have a certifying algorithm for that class as well. All our algorithms run in time O(m+n), including the certification phase. The certificates of representability (the intervals) can be authenticated in time O(m + n). The certificates of nonrepresentability (the forbidden subgraphs) can be authenticated in time O(n). [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of testing bipartiteness of general graphs. The problem has previously been studied in two models, one most suitable for dense graphs and one most suitable for bounded-degree graphs. Roughly speaking, dense graphs can be tested for bipartiteness with constant complexity, while the complexity of testing bounded-degree graphs is [This symbol cannot be presented in ASCII format](√n), where n is the number of vertices in the graph (and [This symbol cannot be presented in ASCII format](f(n)) means Θ(f(n) · polylog(f(n)))). Thus there is a large gap between the complexity of testing in the two cases. In this work we bridge the gap described above. In particular, we study the problem of testing bipartiteness in a model that is suitable for all densities. We present an algorithm whose complexity is [This symbol cannot be presented in ASCII format](min(√n, n²/m)), where m is the number of edges in the graph, and we match it with an almost tight lower bound. [ABSTRACT FROM AUTHOR]

In this paper we derive bounds on the eigenvalues of the preconditioned matrix that arises in the solution of saddle point problems when the Hermitian and skew-Hermitian splitting preconditioner is employed. We also give sufficient conditions for the eigenvalues to be real. A few numerical experiments are used to illustrate the quality of the bounds. [ABSTRACT FROM AUTHOR]

The multipeg Towers of Hanoi problem consists of k pegs mounted on a board together with n disks of different sizes. Initially these disks are placed on one peg in the order of their size, with the largest at the bottom. The rules of the problem allow disks to be moved one at a time from one peg to another as long as a disk is never placed on top of a smaller disk. The goal of the problem is to transfer all the disks to another peg with the minimum number of moves, denoted by H(n, k). An easy recursive argument shows that H(n, 3) = 2n-1. However, the problem of computing the exact value of H(n, k) for k ≥ 4 has been open since 1939, and in particular, the special case of H(n, 4) has been open since 1907. In 1941, Frame and Stewart each gave an algorithm to solve the Towers of Hanoi problem based on an unproved assumption. The Frame-Stewart number, denoted by FS(n, k), is the number of moves needed to solve the Towers of Hanoi problem using the "presumed optimal" Frame-Stewart algorithm. Since then, proving the Frame-Stewart conjecture FS(n, k) = H(n,k) has become a notorious open problem. In this paper, we prove that FS(n, k) and H(n, k) both have the same order of magnitude of 2(1±o(1))(n(k-2)1)1/(k-2) . This provides the strongest evidence so far to support the Frame-Stewart conjecture. [ABSTRACT FROM AUTHOR]

An (α,β)-spanner of a graph G is a subgraph H such that distH(u,w) ≤ α disttG (u, w) + β for every pair of vertices u, w, where distG', (u, w) denotes the distance between two vertices u and v in G'. It is known that every graph G has a polynomially constructible (2κ - 1,0)- spanner (also known as multiplicative (2κ - 1)-spanner) of size O(n1+1/κ) for every integer it κ ≥ 1, and a polynomially constructible (1,2)-spanner (also known as additive 2-spanner) of size O(n&frac32;). This paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to O(n), at the cost of allowing the additive term to be a sufficiently large constant. More formally, we show that for any constant &epsiv;, λ > 0 there exists a constant β = β(&epsiv;, λ) such that for every n-vertex graph G there is an efficiently constructible (1 + &epsiv;, β)-spanner of size O(n1+λ). [ABSTRACT FROM AUTHOR]