Noncirculant Toeplitz matrices all of whose powers are Toeplitz

Let a, b and c be fixed complex numbers. Let M _n (a, b, c) be the n × n Toeplitz matrix all of whose entries above the diagonal are a, all of whose entries below the diagonal are b, and all of whose entries on the diagonal are c. For 1 ⩽ k ⩽ n, each k × k principal minor of M _n (a, b, c) has the same value. We find explicit and recursive formulae for the principal minors and the characteristic polynomial of M _n (a, b, c). We also show that all complex polynomials in M _n (a, b, c) are Toeplitz matrices. In particular, the inverse of M _n (a, b, c) is a Toeplitz matrix when it exists.     

A Family of Wave-Mean Shear Interactions and Their Instability to Longitudinal Vortex Form

The inviscid instability of O(ε) two-dimensional periodic flows to spanwiseperiodic longitudinal vortex modes in parallel O(1) shear flows of the form ū = ± |z|^q is considered. Here the mean velocity ū is relative to the wave and q is a constant. Such shear flows admit neutral Rayleigh waves with amplitudes that either diminish or diverge with |αz|; both are considered. Of particular interest are streamwise α and spanwise l wavenumbers in the range l² ? α², α = O(1), as it is here that the most analytical progress can be made. A generalized Lagrangian-mean formulation is used to describe the effect of fluctuations upon the mean state and, because the developing mean flow acts to distort the waves, a further equation, the Rayleigh-Craik equation, is employed to complete the specification. It is shown that instability to longitudinal vortex form is likely for both classes of waves in many physically interesting situations, from simple mixing layers to atmospheric boundary layers over undulating surfaces.     

Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids

In a rectangular grid, given two sets of nodes, (sources) and (sinks), of size each, the disjoint paths (DP) problem is to connect as many nodes in to the nodes in using a set of “disjoint” paths. (Both edge-disjoint and vertex-disjoint cases are considered in this paper.) Note that in this DP problem, a node in can be connected to any node in . Although in general the sizes of and do not have to be the same, algorithms presented in this paper can also find the maximum number of disjoint paths pairing nodes in and . We use the network flow approach to solve this DP problem. By exploiting all the properties of the network, such as planarity and regularity of a grid, integral flow, and unit capacity source/sink/flow, we can optimally compress the size of the working grid (to be defined) from O(N²) to O(N^1.5) and solve the problem in O(N^2.5) time for both the edge-disjoint and vertex-disjoint cases, an improvement over the straightforward approach which takes O(N³) time.     

A Dijkstra-like shortest path algorithm for certain cases of negative arc lengths

If each negative length arc of a digraphG is acyclic, i.e., does not belong to any cycle, then we show that the shortest paths from a given node to all other nodes can be computed inO(V ²) time, whereV is the number of nodes inG.     

Direct algorithm for the solution of two‐sided obstacle problems with M‐matrix

A direct algorithm for the solution to the affine two‐sided obstacle problem with an M‐matrix is presented. The algorithm has the polynomial bounded computational complexity O(n³) and is more efficient than those in (Numer. Linear Algebra Appl. 2006; 13 :543–551). Copyright © 2010 John Wiley & Sons, Ltd.     

The Inertia Set of Nonnegative Symmetric Sign Pattern with Zero Diagonal

The inertia set of a symmetric sign pattern A is the set i(A) = {i(B) | B = B ^T ∈ Q(A)}, where i(B) denotes the inertia of real symmetric matrix B, and Q(A) denotes the sign pattern class of A. In this paper, a complete characterization on the inertia set of the nonnegative symmetric sign pattern A in which each diagonal entry is zero and all off-diagonal entries are positive is obtained. Further, we also consider the bound for the numbers of nonzero entries in the nonnegative symmetric sign patterns A with zero diagonal that require unique inertia.     

Enclosing a Set of Objects by Two Minimum Area Rectangles

In this paper, we face the problem of computing an enclosing pair of axis-parallel rectangles of a set of polygonal objects in the plane, serving as a simple container. We propose anO(nα(n)log n) worst-case time algorithm, where α( ) is the inverse Ackermann's function, for finding, given a setMof points, segments and polygons defined bynvertices, a pair of axis-parallel rectangles (s, t) such thats∪tencloses all objects inMand area(s)+area(t) is minimum. The algorithm works inO(nα(n) log log n) worst-case space. Moreover, we prove an Ω(n log n) lower bound for the one-dimensional version of the problem. We also show that for the special case of enclosing a set of polygons with axis-parallel sides, our algorithm runs in optimal worst-case timeO(n log n), using worst-case spaceO(n log log n).     

A Faster Deterministic Maximum Flow Algorithm

Cheriyan and Hagerup developed a randomized algorithm to compute the maximum flow in a graph with n nodes and m edges in O(mn + n² log²n) expected time. The randomization is used to efficiently play a certain combinatorial game that arises during the computation. We give a version of their algorithm where a general version of their game arises. Then we give a strategy for the game that yields a deterministic algorithm for computing the maximum flow in a directed graph with n nodes and m edges that runs in time O(mn(log_{m/n log n}n)). Our algorithm gives an O(mn) deterministic algorithm for all m/n = Ω(n^ε) for any positive constant ε, and is currently the fastest deterministic algorithm for computing maximum flow as long as m/n = ω(log n).     

Planar Graphs, via Well-Orderly Maps and Trees

The family of well-orderly maps is a family of planar maps with the property that every connected planar graph has at least one plane embedding which is a well-orderly map. We show that the number of well-orderly maps with n nodes is at most 2^αn+O(logn), where α≈4.91. A direct consequence of this is a new upper bound on the number p(n) of unlabeled planar graphs with n nodes, log₂p(n)≤4.91n. The result is then used to show that asymptotically almost all (labeled or unlabeled), (connected or not) planar graphs with n nodes have between 1.85n and 2.44n edges. Finally we obtain as an outcome of our combinatorial analysis an explicit linear-time encoding algorithm for unlabeled planar graphs using, in the worst-case, a rate of 4.91 bits per node and of 2.82 bits per edge.     

The critical behavior of random digraphs

We study the critical behavior of the random digraph D(n,p) for np = 1 + ε, where ε = ε(n) = o(1). We show that if ε³n →—∞, then a.a.s. D(n,p) consists of components which are either isolated vertices or directed cycles, each of size O_p(|ε|^?1). On the other hand, if ε³n →∞, then a.a.s. the structure of D(n,p) is dominated by the unique complex component of size (4 + o(1))ε²n, whereas all other components are of size O_p(ε^?1). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Approximation Algorithms for Min–Max Tree Partition

We consider the problem of partitioning the node set of a graph intopequal sized subsets. The objective is to minimize the maximum length, over these subsets, of a minimum spanning tree. We show that no polynomial algorithm with bounded error ratio can be given for the problem unless P = NP. We present anO(n²) time algorithm for the problem, wherenis the number of nodes in the graph. Assuming that the edge lengths satisfy the triangle inequality, its error ratio is at most 2p − 1. We also present an improved algorithm that obtains as an input a positive integerx. It runs inO(2^{(p + x)p}n²) time, and its error ratio is at most (2 − x/(x + p − 1))p.     

Bounds for the Entries of Matrix Functions with Applications to Preconditioning

Let A be a symmetric matrix and let f be a smooth function defined on an interval containing the spectrum of A. Generalizing a well-known result of Demko, Moss and Smith on the decay of the inverse we show that when A is banded, the entries of f(A)are bounded in an exponentially decaying manner away from the main diagonal. Bounds obtained by representing the entries of f(A)in terms of Riemann-Stieltjes integrals and by approximating such integrals by Gaussian quadrature rules are also considered. Applications of these bounds to preconditioning are suggested and illustrated by a few numerical examples.     

An implicit QR algorithm for symmetric semiseparable matrices

The QR algorithm is one of the classical methods to compute the eigendecomposition of a matrix. If it is applied on a dense n × n matrix, this algorithm requires O(n³) operations per iteration step. To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal similarity transformations. In the report (Report TW360, May 2003) a reduction from a symmetric matrix into a similar semiseparable one is described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step requires O(n) operations. Hence, combined with the reduction to semiseparable form, the eigenvalues of symmetric matrices can be computed via intermediate semiseparable matrices, instead of tridiagonal ones. The eigenvectors of the intermediate semiseparable matrix will be computed by applying inverse iteration to this matrix. This will be achieved by using an O(n) system solver, for semiseparable matrices. A combination of the previous steps leads to an algorithm for computing the eigenvalue decompositions of semiseparable matrices. Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd.     

Approximation Algorithms for Steiner and Directed Multicuts

In this paper we consider theSteiner multicutproblem. This is a generalization of the minimum multicut problem where instead of separating nodepairs, the goal is to find a minimum weight set of edges that separates all givensetsof nodes. A set is considered separated if it is not contained in a single connected component. We show anO(log³(kt)) approximation algorithm for the Steiner multicut problem, wherekis the number of sets andtis the maximum cardinality of a set. This improves theO(t log k) bound that easily follows from the previously known multicut results. We also consider an extension of multicuts to directed case, namely the problem of finding a minimum-weight set of edges whose removal ensures that none of the strongly connected components includes one of the prespecifiedknode pairs. In this paper we describe anO(log² k) approximation algorithm for this directed multicut problem. Ifk ? n, this represents an improvement over theO(log n log log n) approximation algorithm that is implied by the technique of Seymour.     

Efficient algorithms for a constrained k-tree core problem in a tree network

Let T=(V,E) be a free tree in which each vertex has a weight and each edge has a length. Let n=|V|. Given T and parameters k and l, a (k,l)-tree core is a subtree X of T with diameter l, having k leaves, which minimizes the sum of the weighted distances from all vertices in T to X. In this paper, two efficient algorithms are presented for finding a (k,l)-tree core of T. The first algorithm has O(n²) time complexity for the case that each edge has an arbitrary length. The second algorithm has O(lkn) time complexity for the case that the lengths of all edges are 1. The (k,l)-tree core problem has an application in distributed database systems.     

Optimal recovery of 3D X-ray tomographic data via shearlet decomposition

This paper introduces a new decomposition of the 3D X-ray transform based on the shearlet representation, a multiscale directional representation which is optimally efficient in handling 3D data containing edge singularities. Using this decomposition, we derive a highly effective reconstruction algorithm yielding a near-optimal rate of convergence in estimating piecewise smooth objects from 3D X-ray tomographic data which are corrupted by white Gaussian noise. This algorithm is achieved by applying a thresholding scheme on the 3D shearlet transform coefficients of the noisy data which, for a given noise level ε, can be tuned so that the estimator attains the essentially optimal mean square error rate O(log(ε ^???1)ε ^2/3), as ε→0. This is the first published result to achieve this type of error estimate, outperforming methods based on Wavelet-Vaguelettes decomposition and on SVD, which can only achieve MSE rates of O(ε ^1/2) and O(ε ^1/3), respectively.     

Essentially optimal computation of the inverse of generic polynomial matrices

We present an inversion algorithm for nonsingular n×n matrices whose entries are degree d polynomials over a field. The algorithm is deterministic and, when n is a power of two, requires O^∼(n³d) field operations for a generic input; the soft-O notation O^∼ indicates some missing log(nd) factors. Up to such logarithmic factors, this asymptotic complexity is of the same order as the number of distinct field elements necessary to represent the inverse matrix.     

A fast algorithm for coloring Meyniel graphs

We color the nodes of a graph by first applying successive contractions to non-adjacent nodes until we get a clique; then we color the clique and decontract the graph. We show that this algorithm provides a minimum coloring and a maximum clique for any Meyniel graph by using a simple rule for choosing which nodes are to be contracted. This O(n³) algorithm is much simpler than those already existing for Meyniel graphs. Moreover, the optimality of this algorithm for Meyniel graphs provides an alternate nice proof of the following result of Hoàng: a graph G is Meyniel if and only if, for any induced subgraph of G, each node belongs to a stable set that meets all maximal cliques. Finally we give a new characterization for Meyniel graphs.     

Primitive non-powerful sign pattern matrices with base 2

A sign pattern matrix M with zero trace is primitive non-powerful if for some positive integer k, M ^k ?=?J _#. The base l(M) of the primitive non-powerful matrix M is the smallest integer k. By considering the signed digraph S whose adjacent matrix is the primitive non-powerful matrix M, we will show that if l(M)?=?2, the minimum number of non-zero entries of M is 5n???8 or 5n???7 depending on whether n is even or odd.