Construction and algebraic characterizations of a planar four-index transportation problem equivalent to a circularization network flow problem

In this study, a circularization network flow problem with m?+?n?+?2 nodes and (m?+?1)(n?+?1) arcs is described as a planar four-index transportation problem of order 1?×?m?×?n?×?1. Construction and several algebraic characterizations of the planar four-index transportation problem of order 1?×?m?×?n?×?1 are investigated using the generalized inverse and singular value decomposition of its coefficient matrix. The results are compared with some results we obtained on the transportation problem with m sources and n destinations. It is shown that these problems can be solved in terms of eigenvectors of the matrices J _m and J _n , where J _m is a m?×?m matrix whose entries are 1.     

Some new results on the algebraic characterizations of an equality constrained optimization problem equivalent to the transportation problem

An equality constrained optimization problem equivalent to the transportation problem with m sources and n destinations is described. The optimality condition and some algebraic characterizations of the problem are investigated using its Hessian matrix. In addition, several algebraic characterizations of an equivalent case of the transportation problem are given using the spectral decomposition and generalized inverses of its coefficient matrix. It is shown that the transportation problem and its equivalent case have common algebraic characterizations.     

Some consequences on the planar three-index transportation problem

In this study, some algebraic characterizations of the coefficient matrix A of the planar three-index transportation problem are derived and the equivalent formulation of this problem is obtained using the Kronecker product. It is shown that eigenvectors of the matrix G ⁺ G are characterized in terms of eigenvectors of the matrix A ⁺ A , where G ⁺ is the Moore–Penrose inverse of the coefficient matrix G of the equivalent problem.     

An effective approach to the optimal-control problem for time-varying linear systems via Taylor series

The Taylor series is used for the solution of the optimal-control problem for time-varying linear systems. Instead of solving the state transition matrix from the state equation with a terminal condition, the present approach first transforms the terminal condition into an initial condition, and then solves the initial-value problem to find the transition matrix. This approach leads lo a recursive algebraic formulation for the transition matrix, and only an inverse matrix of small dimension 2n × 2n appears in this formulation. Thus a closed-loop control law is obtained without solving the non-linear Riccati equation, and the matrix to be inverted has only small dimension 2n × 2n. The present approach is of great interest because of its simplicity and numerical stability.     

An efficient solution to the subset‐sum problem on GPU

We present an algorithm to solve the subset‐sum problem (SSP) of capacity c and n items with weights w_i,1≤i≤n, spending O(n(m − w_min)/p) time and O(n + m − w_min) space in the Concurrent Read/Concurrent Write (CRCW) PRAM model with 1≤p≤m − w_min processors, where w_min is the lowest weight and , improving both upper‐bounds. Thus, when n≤c, it is possible to solve the SSP in O(n) time in parallel environments with low memory. We also show OpenMP and CUDA implementations of this algorithm and, on Graphics Processing Unit, we obtained better performance than the best sequential and parallel algorithms known so far. Copyright © 2015 John Wiley & Sons, Ltd.     

Characterizing the solution set of polynomial systems in terms of homogeneous forms: an LMI approach

This paper considers the problem of determining the solution set of polynomial systems, a well‐known problem in control system analysis and design. A novel approach is developed as a viable alternative to the commonly employed algebraic geometry and homotopy methods. The first result of the paper shows that the solution set of the polynomial system belongs to the kernel of a suitable symmetric matrix. Such a matrix is obtained via the solution of a linear matrix inequality (LMI) involving the maximization of the minimum eigenvalue of an affine family of symmetric matrices. The second result concerns the computation of the solution set from the kernel of the obtained matrix. For polynomial systems of degree m in n variables, a basic procedure is available if the kernel dimension does not exceed m+1, while an extended procedure can be applied if the kernel dimension is less than n(m?1)+2. Finally, some application examples are illustrated to show the features of the approach and to make a brief comparison with polynomial resultant techniques. Copyright © 2003 John Wiley & Sons, Ltd.     

Strongly (J,J′)‐lossless rational matrices and ℋ∞ problem

We strengthen the existing definition of (J,J′)‐lossless rational matrices (RMs) and find an algebraic characterization of the newly defined class of strongly (J,J′)‐lossless RMs. The algebraic characterization is given for possibly improper RMs. A connection is presented to a rational ? _∞ problem, known as the Leech problem, which is elaborated on with necessary and sufficient conditions, given in terms of the strongly (J,J′)‐lossless property, as an alternative of the Leech conditions, which can be expressed with positivity of a kernel. An algorithm for solving the Leech problem is given and illustrated by examples.     

Least-squares problem for the quaternion matrix equation AXB+CYD=E over different constrained matrices

For any A=A ₁+A ₂ j∈Q ^n×n and η∈<texlscub>i, j, k</texlscub>, denote A ^{η H} =?η A ^H η. If A ^{η H} =A, A is called an $\eta$-Hermitian matrix. If A ^{η H} =?A, A is called an η-anti-Hermitian matrix. Denote η-Hermitian matrices and η-anti-Hermitian matrices by η HQ ^n×n and η AQ ^n×n , respectively.

By using the complex representation of quaternion matrices, the Moore–Penrose generalized inverse and the Kronecker product of matrices, we derive the expressions of the least-squares solution with the least norm for the quaternion matrix equation AXB+CYD=E over X∈η HQ ^n×n and Y∈η AQ ^n×n .     

Some results on the genericity of the pole placement problem

In this note, the pole placement problem for a linear MIMO systems with p outputs and m inputs is studied from the algebraic point of view. A formulation is proposed, that allows to analyze both theoretical and numerical aspects of the case min(m,p)=2 with more sharpness. Moreover, here it is shown that arbitrary pole placement by static output feedback of unitary rank is generically not possible even if m+p>n holds true.     

Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic

In Valiant’s theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning these classes is the Permanent and Determinant Problem: Given a field \mathbbF{\mathbb{F}} of characteristic ≠ 2, and an integer n, what is the minimum m such that the permanent of an n × n matrix X = (x_ij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of x_ij ’s, and the equality is in \mathbbF[X]{\mathbb{F}}[{\bf X}]. Mignon and Ressayre (2004) proved a quadratic lower bound m = W(n²)m = \Omega(n^{2}) for fields of characteristic 0. We extend the Mignon–Ressayre quadratic lower bound to all fields of characteristic ≠ 2.     

Systolic algorithm for the solution of dense linear equations

For arbitrary n×n matrix A and n×m matrix B, a systolic algorithm to solve the linear systems AX=B is presented. The cmputational model used consists of n(n+1) PEs. The number of PEs used is independent of m. This algorithm requires 4n+m–2 time steps to solve the linear systems. Since the structure of PE is simple and the PE with same type executes the identical program, it is very suitable for VLSI implementation. Moreover, if m is a singular matrix, it can be detected during the execution of the systolic algorithm.     

Improved Controller Design for Uncertain Positive Systems and its Extension to Uncertain Positive Switched Systems

This paper is concerned with the controller design of uncertain positive systems. First, we decompose the feedback gain matrix K_m×n into m×n non‐negative components and m×n non‐positive components. For the non‐negative components, each component contains only one positive element and the other elements are zero. Similarly, each non‐positive component contains only one negative element and the other ones are zero. Then, a simple and effective controller design approach of uncertain positive systems is proposed by incorporating the decomposed feedback gain matrix into the resulting closed‐loop systems and further applied to uncertain positive switched systems. It is shown that the designed controller is less conservative compared with those in the literature. Finally, a numerical example is provided to verify the validity of the proposed design.     

A TENSOR-THEORETIC ENHANCEMENT TO THE HILL CIPHER SYSTEM

The Hill matrix algorithm[3], published in 1929, is known for being the first purely algebraic cryptographic system and for starting the entire field of algebraic cryptology. In this paper, an operator derived from ring isomorphism theory is adapted for use in the Hill system which greatly increases the block size that a matrix can encrypt; specifically, a k×k invertible matrix over Z _n represents an invertible matrix of order k ³, which produces ciphertext blocks k ²-times as long as the original matrix could. This enhancement increases the Hill system's security considerably.     

Algorithms of constructing a stabilizing solution of the algebraic Riccati equation based on its linear reduction in the problems of analytical construction of controllers

In the problem of the stabilizing solution of the algebraic Riccati equation, the resolvent Θ(s) = (s I _2n ? H)^?1 of the Hamilton 2n × 2n-matrix H of the algebraic Riccati equation allows us to reduce the problem to a linear matrix equation. In [1], the constructions necessary for this and the theorem of existence and representation of the stabilized solutions to an algebraic Riccati equation was proposed. In this paper, the methods of constructing the resolvent and the linear reduction matrix defined by it necessary for the application of the theorem, and in addition, the algorithms of constructing stabilizing solution of the algebraic Riccati equation are proposed.     

Solving the Euclidean bottleneck matching problem byk-relative neighborhood graphs

Given a set of pointsV in the plane, the Euclidean bottleneck matching problem is to match each point with some other point such that the longest Euclidean distance between matched points, resulting from this matching, is minimized. To solve this problem, we definek-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are calledk-relative neighbors if and only if there are less thank points ofV which are closer to both of the two points than the two points are to each other. AkRNG is an undirected graph (V,E _r ^k ) whereE _r ^k is the set of pairs of points ofV which arek-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset ofE _r ¹⁷ . We also prove that ¦E _r ^k ¦ < 18kn wheren is the number of points in setV. Our algorithm would construct a 17RNG first. This takesO(n ²) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity isO((n logn)^0.5 m), wherem is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takesO(n ^1.5 log^0.5 n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem isO(n ² +n ^1.5 log^0.5 n).This research was partially supported by a grant from the National Science Council of the Republic of China under Grant NSC-78-0408-E-007-05.     

Faster Two Dimensional Scaled Matching

The rapidly growing need for analysis of digitized images in multimedia systems has lead to a variety of interesting problems in multidimensional pattern matching. One of the problems is that of scaled matching, finding all appearances of a pattern, proportionally enlarged according to an arbitrary real-sized scale, in a given text. The currently fastest known algorithm for this problem uses techniques from dictionary matching to solve the problem in O(nm ³+n ² mlog m) time using O(nm ³+n ²) space, where T is a two-dimensional n×n text array and P is a two-dimensional m×m pattern array.     

Characterizations of J-lossless time-varying systems via the chain scattering approach

In this paper, via the chain scattering formalism, we derive the inequality condition for a bounded I/O operator which is associated with a finite-dimensional linear time-varying system to be lossless or J-lossless. The characterizations for J-losslessness apply to a J-lossless time-varying system which is either exponentially stable, anti-stable or one with a uniform stable/anti-stable decomposition of its state space. Uniform time-varying realizations are considered as they are required for the proof of the necessity of the state space characterizations. The results provide an extension to the state space characterizations of linear time-invariant J-lossless systems which belong to RL _∞. The characterizations for (J,J′)-lossless LTV systems are also derived. © 1998 John Wiley & Sons, Ltd.     

Polynomial algorithms for finding the asymptotically optimum plan of the multiindex axial assignment problem

To construct the asymptotically optimum plan of the p-index axial assignment problem of order n, p algorithms α₀, α₁, ..., α _p−1 with complexities equal to O(n^p+1), O(n^p), ..., O(n²) operations, respectively, are proposed and substantiated under some additional conditions imposed on the coefficients of the objective function. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 176–181, November–December 2005.     

A polynomial algorithm for the multiple knapsack problem with divisible item sizes

A polynomial algorithm for the multiple bounded knapsack problem with divisible item sizes is presented. The complexity of the algorithm is O(n²+nm), where n and m are the number of different item sizes and knapsacks, respectively. It is also shown that the algorithm complexity reduces to O(nlogn+nm) when a single copy exists of each item.