A fast algorithm for computing a longest common increasing subsequence

Let A=〈a₁,a₂,…,am〉 and B=〈b₁,b₂,…,bn〉 be two sequences, where each pair of elements in the sequences is comparable. A common increasing subsequence of A and B is a subsequence 〈ai₁=bj₁,ai₂=bj₂,…,ail=bjl〉, where i₁<i₂<?<il and j₁<j₂<?<jl, such that for all 1?k<l, we have aik<aik+1. A longest common increasing subsequence of A and B is a common increasing subsequence of the maximum length. This paper presents an algorithm for delivering a longest common increasing subsequence in O(mn) time and O(mn) space.     

Sturm sequences or law of inertia of quadratic forms?

In obtaining the number of eigenvalues greater than a given constant λ₀ of the eigenvalue problem [A]{x} = λ[B]{x} with [A] and [B] real, symmetric, and [B] positive definite, one usually refers to the Sturm sequence established by the leading principal minors of [A–λ₀B], the proof of which is given basically when the associated special eigenvalue problem is tridiagonal. In this work, using the law of inertia of quadratic forms, it is shown that the number of eigenvalues of [A]{x}] = λ[B]{x} greater than a given constant λ₀ (not an eigenvalue) is the number of positive entries of the diagonal matrix [d] in the identity [A–λ₀B] = [u]^T[d][u] where [u] is the upper triangular matrix associated with Crout-Banachievicz type decomposition of [A –λ₀B], without the help of the separation theorem and the Sturm sequence.     

Structural controllability and matrix nets†

We establish structural controllability results for matrix pairs [A, B] where A = A ₀ + Σ μ _iA_i , B = B ₀ + σ μ _i, B_i , with the A_i , B_i , fixed, and the μ _i , free scalar parameters. The results characterize structural controllability in several ways, via tests involving the checking of the rank or the evaluation of the determinant of various constant matrices formed from the A_i , B_i . A number of the results used as intermediate results tests for a full rank property of matrix nets, i.e. tests that check if M = M₀+ Σμ_iM_i prescribed, μ _i variable, has full rank for almost all μ _i .     

On the problem of general structural assignments of linear systems through sensor/actuator selection

A systematic method is developed for determining an output matrix C for a given matrix pair (A,B) such that the resulting linear system characterized by the matrix triple (A,B,C) has the pre-specified system structural properties, such as the finite and infinite zero structure and the invertibility structures. Since the matrix C describes the locations of the sensors, the procedure of choosing C is often referred to as sensor selection. The method developed in this paper for sensor selection can be applied to the dual problem of actuator selection, where, for a given matrix pair (A,C), a matrix B is to be determined such that the resulting matrix triple (A,B,C) has the pre-specified structural properties.     

Approximation algorithms for covering/packing integer programs

Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing . We give a bicriteria-approximation algorithm that, given ε∈(0,1], finds a solution of cost O(ln(m)/ε²) times optimal, meeting the covering constraints (Ax?a) and multiplicity constraints (x?d), and satisfying Bx?(1+ε)b+β, where β is the vector of row sums β_i=∑_jB_ij. Here m denotes the number of rows of A.This gives an O(lnm)-approximation algorithm for CIP—minimum-cost covering integer programs with multiplicity constraints, i.e., the special case when there are no packing constraints Bx?b. The previous best approximation ratio has been O(ln(max_j∑_iA_ij)) since 1982. CIP contains the set cover problem as a special case, so O(lnm)-approximation is the best possible unless P=NP.     

A numerical method for deadbeat control of generalized state-space systems

In this paper we give a new numerical method for constructing a rank m correction BF to an n × n matrix A, such that the generalized eigenvalues of λE−(A+BF) are all at λ = 0. In the control literature, this problem is known as ‘deadbeat control’ of a generalized state-space system Ex_i+1 = Ax_i + Bu_i, whereby the matrix F is the ‘feedback matrix’ to be constructed.     

Gleichheit von Produkt und Formalprodukt bei Intervallpolynomen

The paper gives necessary and sufficient conditions for the product of two interval polynomials being equal to their formally defined product. For this purpose criteria must be deduced for which intervalsA _i, B _j the equality(A ₁+...+A _m ) (B ₁ +...+B _n )=A ₁ B ₁ +A ₁ B ₂ +...+A _m B _n (relation of distributivity) holds.     

A sixth-order extrapolation method for special nonlinear fourth-order boundary value problems

A sixth-order convergent finite difference method is developed for the numerical solution of the special nonlinear fourth-order boundary value problem y^(iv)(x) = f(x, y), a < x < b, y(a) = A₀, y″(a) = B₀, y(b) = A₁ y′(b) = B₁, the simple-simple beam problem.The method is based on a second-order convergent method which is used on three grids, sixth-order convergence being obtained by taking a linear combination of the (second-order) numerical results calculated using the three individual grids.Special formulas are proposed for application to points of the discretization adjacent to the boundaries x = a and x= b, the first two terms of the local truncation errors of these formulas being the same as those of the second-order method used at the other points of each grid.Modifications to these two formulas are obtained for problems with boundary conditions of the form y(a) = A₀, y′(a) = C₀, y(b) = A₁, y′(b) = C₁, the clamped-clamped beam problem.The general boundary value problem, for which the differential equation is y^(iv)(x) = f(x, y, y′, y″, y‴), is also considered.     

On the cubicity of bipartite graphs

A unit cube in k-dimension (or a k-cube) is defined as the Cartesian product R₁×R₂×?×Rk, where each Ri is a closed interval on the real line of the form [ai,ai+1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. Many NP-complete graph problems can be solved efficiently or have good approximation ratios in graphs of low cubicity. In most of these cases the first step is to get a low dimensional cube representation of the given graph.It is known that for a graph G, . Recently it has been shown that for a graph G, cub(G)?4(Δ+1)lnn, where n and Δ are the number of vertices and maximum degree of G, respectively. In this paper, we show that for a bipartite graph G=(A∪B,E) with |A|=n₁, |B|=n₂, n₁?n₂, and Δ^′=min{ΔA,ΔB}, where ΔA=maxa∈Ad(a) and ΔB=maxb∈Bd(b), d(a) and d(b) being the degree of a and b in G, respectively, cub(G)?2(Δ^′+2)⌈lnn₂⌉. We also give an efficient randomized algorithm to construct the cube representation of G in 3(Δ^′+2)⌈lnn₂⌉ dimensions. The reader may note that in general Δ^′ can be much smaller than Δ.     

Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood

LetA=(a _ij ) be the distance matrix of an arbitrary (asymmetric) traveling salesman problem and let τ=τ₁τ₂...τ _m be the optimal solution of the corresponding assignment problem with the subtours τ=τ₁τ₂...τ _m . By choosing (m?1) transpositions (k, l) withk ∈ τ _i?1,l ∈ τ _i (i=2, ...,m) and patching the subtours by using these transpositions in any order, we get a set of cyclic permutations. It will be shown that within this set of cyclic permutations a tour with minimum distance can be found by O(n ²|τ|* operations, where |τ|* is the maximum number of nodes in a subtour of τ. Moreover, applying this result to the case whenA=(a _ij ) is a permuted distribution matrix (Monge-matrix) and thepatching graph G _τ is a multipath, a result of Gaikov can be improved: By combining the above theory with a result of Park alinear algorithm for finding an optimal TSP solution can be derived, provided τ is already known.     

Border Correlations of Partial Words

Partial words are finite sequences over a finite alphabet A that may contain a number of “do not know” symbols denoted by ?’s. Setting $A_{\diamond}=A\cup\lbrace{\diamond}\rbracePartial words are finite sequences over a finite alphabet A that may contain a number of “do not know” symbols denoted by ⋄’s. Setting A_à=Aè{à}A_{\diamond}=A\cup\lbrace{\diamond}\rbrace , A _⋄ ^* denotes the set of all partial words over A. In this paper, we investigate the border correlation function b:A_à^*?{a,b}^*\beta:A_{\diamond}^{*}\rightarrow\lbrace a,b\rbrace^{*} that specifies which conjugates (cyclic shifts) of a given partial word w of length n are bordered, that is, β(w)=c ₀ c ₁…c _n−1 where c _i =a or c _i =b according to whether the ith cyclic shift σ ⁱ (w) of w is unbordered or bordered. A partial word w is bordered if a proper prefix x ₁ of w is compatible with a proper suffix x ₂ of w, in which case any partial word x containing both x ₁ and x ₂ is called a border of w. In addition to β, we investigate an extension β′:A _⋄ ^*→ℕ^* that maps a partial word w of length n to m ₀ m ₁…m _n−1 where m _i is the length of a shortest border of σ ⁱ (w). Our results extend those of Harju and Nowotka.     

A program generator for the incomplete cholesky conjugate gradient (ICCG) method with a symmetrizing preprocessor

This paper is an extension of our previous paper “A program generator for the Incomplete LU-decomposition-Conjugate Gradient (ILUCG) method” which appeared in Computer Physics Communications. In that paper we presented a generator program which produced a code package to solve the system of equations Ax = bb, where A is an arbitrary nonsingular matrix, by the ILUCG method. In the present paper we offer an alternative generator program which produces a code package applicable to the case where A is symmetric and positive definite. The numerical algorithm used is the Incomplete Cholesky Conjugate Gradient (ICCG) method of Meijerink and Van der Vorst which executes approximately twice as fast per iteration as the ILUCG method. In addition, we provide an optional preprocessor to treat the case of a not diagonally dominant nonsymmetric and nonsingular matrix A by solving the equation A^TAx = A^Tb.     

Controllability for Discrete Systems with a Finite Control Set

In this paper we consider the problem of controllability for a discrete linear control system x _k+1=Ax _k+Bu _k, u _k∈U, where (A,B) is controllable and U is a finite set. We prove the existence of a finite set U ensuring density for the reachable set from the origin under the necessary assumptions that the pair (A,B) is controllable and A has eigenvalues with modulus greater than or equal to 1. In the case of A only invertible we obtain density on compact sets. We also provide uniformity results with respect to the matrix A and the initial condition. In the one-dimensional case the matrix A reduces to a scalar λ and for λ>1 the reachable set R(0,U) from the origin is?

Speeding up transposition-invariant string matching

Finding the longest common subsequence (LCS) of two given sequences A=a₀a₁…am−1 and B=b₀b₁…bn−1 is an important and well studied problem. We consider its generalization, transposition-invariant LCS (LCTS), which has recently arisen in the field of music information retrieval. In LCTS, we look for the LCS between the sequences A+t=(a₀+t)(a₁+t)…(am−1+t) and B where t is any integer. We introduce a family of algorithms (motivated by the Hunt-Szymanski scheme for LCS), improving the currently best known complexity from O(mnloglogσ) to O(Dloglogσ+mn), where σ is the alphabet size and D?mn is the total number of dominant matches for all transpositions. Then, we demonstrate experimentally that some of our algorithms outperform the best ones from literature.     

Constructing symmetric nonnegative matrices via the fast fourier transform

We derive an algorithm based on the fast Fourier transform to construct a real symmetric matrix S with eigenvalues λ₁≥λ₂≥⋯≥λ_n, with eigenvector e = [1, 1, … ,1]^T belonging to the eigenvalue λ₁.We find simple conditions on the eigenvalues such that the algorithm constructs an irreducible matrix S = λ₁E, where E is a symmetric doubly stochastic matrix.     

The periodic nature of the positive solutions of a nonlinear fuzzy max-difference equation

We investigate the periodic nature of the positive solutions of the fuzzy difference equation , where k, m are positive integers, A₀, A₁, are positive fuzzy numbers and the initial values x_i, i = −d, −d + 1, … , −1, d = max{k, m}, are positive fuzzy numbers. In addition, we give conditions so that the solutions of this equation are unbounded.     

Spurious solutions for discrete superlinear boundary value problems

We consider finite dimensional nonlinear eigenvalue problems of the typeAu=λFu whereA is a matrix and(Fu) _i =f(u _i ),i=1, ...,m. These may be thought of as discretizations of a corresponding boundary value problem. We show that positive, spurious solution branches of the discrete equations (which have been observed in some cases in [1, 7]) typically arise iff increases sufficiently strong and ifA ^?1 has at least two positive columns of a certain type. We treat in more detail the casesf(u)=e ^u andf(u)=u ^α where also discrete bifurcation diagrams are given.     

On the RAS-algorithm

Given a nonnegative real (m, n) matrixA and positive vectorsu, v, then the biproportional constrained matrix problem is to find a nonnegative (m, n) matrixB such thatB=diag (x) A diag (y) holds for some vectorsx ∈ ? ^m andy ∈ ? ⁿ and the row (column) sums ofB equalu _i (v _j )i=1,...,m(j=1,..., n). A solution procedure (called the RAS-method) was proposed by Bacharach [1] to solve this problem. The main disadvantage of this algorithm is, that round-off errors slow down the convergence. Here we present a modified RAS-method which together with several other improvements overcomes this disadvantage.     

Finite element patch approximations and alternating-direction methods

Numerical results using two modified Crank-Nicolson time discretizations are presented for finite element approximations to the nonlinear parabolic equation in 1R^d, c(x,u) ? (a_ij (x,u)u_,j)_,i + b_i (x,u)u_,i = f(x,t,u), where the summation convection on repeated indices is assumed. Both procedures use a local approximation to the coefficients which is based on patches of finite elements. With the first method, the coefficients are updated at each time step; however, only one matrix decomposition is required per problem. This method can exploit efficient direct methods for solving the resulting matrix problem. The second method is an alternating-direction variation which is valid for certain nonrectangular regions. With the alternating-direction method the resulting matrix problem can be solved as a series of one-dimensional problems, which results in a significant savings of time and storage over traditional techniques.