Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbations

In this paper we address the problem of efficiently computing all the eigenvalues of a large N×N Hermitian matrix modified by a possibly non Hermitian perturbation of low rank. Previously proposed fast adaptations of the QR algorithm are considerably simplified by performing a preliminary transformation of the matrix by similarity into an upper Hessenberg form. The transformed matrix can be specified by a small set of parameters which are easily updated during the QR process. The resulting structured QR iteration can be carried out in linear time using linear memory storage. Moreover, it is proved to be backward stable. Numerical experiments show that the novel algorithm outperforms available implementations of the Hessenberg QR algorithm already for small values of N.      

Some issues on interpolation matrices of locally scaled radial basis functions

Radial basis function interpolation on a set of scattered data is constructed from the corresponding translates of a basis function, which is conditionally positive definite of order m ? 0, with the possible addition of a polynomial term. In many applications, the translates of a basis function are scaled differently, in order to match the local features of the data such as the flat region and the data density. Then, a fundamental question is the non-singularity of the perturbed interpolation (N × N) matrix. In this paper, we provide some counter examples of the matrices which become singular for N ? 3, although the matrix is always non-singular when N = 2. One interesting feature is that a perturbed matrix can be singular with rather small perturbation of the scaling parameter.     

On the sensitivity of generators for the QR factorization of quasiseparable matrices with total nonpositivity

In this paper, we provide a relatively robust representation for the QR factorization of quasiseparable matrices with total nonpositivity. This representation allows us to develop a structure-preserving perturbation analysis. Consequently, stronger perturbation bounds are obtained to show that its generators determine the factors Q and R to high relative accuracy, independent of any conventional condition number. This means that it is possible to accurately compute the QR factorization by operating on these generators.     

On single and double Soules matrices

Until now the concept of a Soules basis matrix of sign patternN consisted of an orthogonal matrix R∈R^n,n, generated in a certain way from a positive n-vector, which has the property that for any diagonal matrix Λ = diag(λ₁, … , λ_n), with λ₁ ? ? ? λ_n ? 0, the symmetric matrix A = RΛR^T has nonnegative entries only. In the present paper we introduce the notion of a pair of double Soules basis matrices of sign patternN which is a pair of matrices (P, Q), each in R^n,n, which are not necessarily orthogonal and which are generated in a certain way from two positive vectors, but such that PQ^T = I and such that for any of the aforementioned diagonal matrices Λ, the matrix A = PΛQ^T (also) has nonnegative entries only. We investigate the interesting properties which such matrices A have.As a preamble to the above investigation we show that the iterates, , generated in the course of the QR-algorithm when it is applied to A = RΛR^T, where R is a Soules basis matrix of sign pattern N, are again symmetric matrices generated by the Soules basis matrices R_k of sign pattern N which are themselves modified as the algorithm progresses.Our work here extends earlier works by Soules and Elsner et al.     

A note on the perturbation of positive matrices by normal and unitary matrices

In a recent paper, Neumann and Sze considered for an n × n nonnegative matrix A, the minimization and maximization of ρ(A + S), the spectral radius of (A + S), as S ranges over all the doubly stochastic matrices. They showed that both extremal values are always attained at an n × n permutation matrix. As a permutation matrix is a particular case of a normal matrix whose spectral radius is 1, we consider here, for positive matrices A such that (A + N) is a nonnegative matrix, for all normal matrices N whose spectral radius is 1, the minimization and maximization problems of ρ(A + N) as N ranges over all such matrices. We show that the extremal values always occur at an n × n real unitary matrix. We compare our results with a less recent work of Han, Neumann, and Tastsomeros in which the maximum value of ρ(A + X) over all n × n real matrices X of Frobenius norm was sought.     

The fast Fourier transform method and ill-conditioned matrices

We study the problem of finding numerical solutions of the linear algebraic equation, a*x=b, where a denotes an N × N ill-conditioned coefficient matrix. It is well-known that Gaussian elimination methods coupled with pivoting strategies are ineffective in this setting due to round-off error. We propose a new and simple application of the fast Fourier transform (FFT) method. Other viable methods, such as the QR method (QRM) or the singular value decomposition method (SVDM), have been proposed in the literature. The goal of this paper is to investigate the performance of the proposed method and compare it to other popular methods. The comparison is illustrated by computer simulation results using MATLAB.     

On the security analysis of an image scrambling encryption of pixel bit and its improved scheme based on self-correlation encryption

An image scrambling encryption scheme for pixel bits was presented by Ye [Ye GD. Image scrambling encryption algorithm of pixel bit based on chaos map. Pattern Recognit Lett 2010;31:347-54], which can be seen as one kind of typical binary image scrambling encryption considering from the bit-plain of size M × (8N). However, recently, some defects existing in the original image encryption scheme, i.e., Ye’s scheme, have been observed by Li and Lo [Li CQ, Lo KT. Optimal quantitative cryptanalysis of permutation-only multimedia ciphers against plaintext attacks. Signal Process 2011;91:949-54]. In the attack proposed by Li and Lo at least 3 + ⌈log₂(MN)⌉ plain images of size M × N are used to reveal the permutation matrix W = [w(i, k)] (i ∈ {1, 2, … , M}; k ∈ {1, 2, … , 8N}) which can be applied to recover the exact plain image. In the current paper, at first, one type of special plain image/cipher image is used to analyze the security weakness of the original image scrambling scheme under study. The final encryption vectors TM and TN or the decryption vectors TM′ and TN′ are revealed completely according to our attack. To demonstrate the performance of our attack, a quantified comparison is drawn between our attack and the attack proposed by Li and Lo. Compared with Li and Lo’s attack, our attack is more efficient in the general conditions. In particular, when the sizes of images satisfy the condition M = N or M ? 8N, the number of the used plain images/cipher images is at most 9, which is sharply less than 3 + ⌈log₂(MN)⌉ when M and N are of large size. To overcome the weaknesses of the original scheme, in this paper, an improved image scrambling encryption scheme is proposed. In the improved scheme, the idea of the “self-correlation” method is used to resist the chosen-plaintext attack/known-plaintext attack. The corresponding simulations and analyses illustrate that the improved encryption method has good cryptographic properties, and can overcome the weakness of the original image encryption scheme. Finally, farther improvement is briefly presented for the future work.     

A recursive algorithm for constructing complicated Dixon matrices

Whether the determinant of the Dixon matrix equals zero or not is used for determining if a system of n + 1 polynomial equations in n variables has a common root, and is a very efficient quantifier elimination approach too. But for a complicated polynomial system, it is not easy to construct the Dixon matrix. In this paper, a recursive algorithm to construct the Dixon matrix is proposed by which some problems that cannot be tackled by other methods can be solved on the same computer platform. A dynamic programming algorithm based on the recursive formula is developed and compared for speed and efficiency to the recursive algorithm.     

A geometric process maintenance model with preventive repair

In this paper, a geometric process maintenance model with preventive repair is studied. A maintenance policy (T, N) is applied by which the system will be repaired whenever it fails or its operating time reaches T whichever occurs first, and the system will be replaced by a new and identical one following the Nth failure. The long-run average cost per unit time is determined. An optimal policy (T^∗, N^∗) could be determined numerically or analytically for minimizing the average cost. A new class of lifetime distribution which takes into account the effect of preventive repair is studied that is applied to determine the optimal policy (T^∗, N^∗).     

Krylov type subspace methods for matrix polynomials

We consider solving eigenvalue problems or model reduction problems for a quadratic matrix polynomial Iλ² − Aλ − B with large and sparse A and B. We propose new Arnoldi and Lanczos type processes which operate on the same space as A and B live and construct projections of A and B to produce a quadratic matrix polynomial with the coefficient matrices of much smaller size, which is used to approximate the original problem. We shall apply the new processes to solve eigenvalue problems and model reductions of a second order linear input-output system and discuss convergence properties. Our new processes are also extendable to cover a general matrix polynomial of any degree.     

A multi-round generalization of the traveling tournament problem and its application to Japanese baseball

In a double round-robin tournament involving n teams, every team plays 2(n − 1) games, with one home game and one away game against each of the other n − 1 teams. Given a symmetric n by n matrix representing the distances between each pair of home cities, the traveling tournament problem (TTP) seeks to construct an optimal schedule that minimizes the sum total of distances traveled by the n teams as they move from city to city, subject to several natural constraints to ensure balance and fairness. In the TTP, the number of rounds is set at r = 2. In this paper, we generalize the TTP to multiple rounds (r = 2k, for any k ? 1) and present an algorithm that converts the problem to finding the shortest path in a directed graph, enabling us to apply Dijkstra’s Algorithm to generate the optimal multi-round schedule. We apply our shortest-path algorithm to optimize the league schedules for Nippon Professional Baseball (NPB) in Japan, where two leagues of n = 6 teams play 40 sets of three intra-league games over r = 8 rounds. Our optimal schedules for the Pacific and Central Leagues achieve a 25% reduction in total traveling distance compared to the 2010 NPB schedule, implying the potential for considerable savings in terms of time, money, and greenhouse gas emissions.     

Alexandrov’s inequality and conjectures on some Toeplitz matrices

We study determinant inequalities for certain Toeplitz-like matrices over C. For fixed n and N ? 1, let Q be the n × (n + N − 1) zero-one Toeplitz matrix with Q_ij = 1 for 0 ? j − i ? N − 1 and Q_ij = 0 otherwise. We prove that det(QQ^∗) is the minimum of det(RR^∗) over all complex matrices R with the same dimensions as Q satisfying ∣R_ij∣ ? 1 whenever Q_ij = 1 and R_ij = 0 otherwise. Although R has a Toeplitz-like band structure, it is not required to be actually Toeplitz. Our proof involves Alexandrov’s inequality for polarized determinants and its generalizations. This problem is motivated by Littlewood’s conjecture on the minimum 1-norm of N-term exponential sums on the unit circle. We also discuss polarized Bazin-Reiss-Picquet identities, some connections with k-tree enumeration, and analogous conjectured inequalities for the elementary symmetric functions of QQ^∗.     

Implicit QR algorithms for palindromic and even eigenvalue problems

In the spirit of the Hamiltonian QR algorithm and other bidirectional chasing algorithms, a structure-preserving variant of the implicit QR algorithm for palindromic eigenvalue problems is proposed. This new palindromic QR algorithm is strongly backward stable and requires less operations than the standard QZ algorithm, but is restricted to matrix classes where a preliminary reduction to structured Hessenberg form can be performed. By an extension of the implicit Q theorem, the palindromic QR algorithm is shown to be equivalent to a previously developed explicit version. Also, the classical convergence theory for the QR algorithm can be extended to prove local quadratic convergence. We briefly demonstrate how even eigenvalue problems can be addressed by similar techniques. D. S. Watkins partly supported by Deutsche Forschungsgemeinschaft through Matheon, the DFG Research Center Mathematics for key technologies in Berlin.     

A dynamic adaptive local search algorithm for the circular packing problem

This paper studies the circular packing problem (CPP) which consists of packing n non-identical circles C_i of known radius r_i, i ∈ N = {1, … , n}, into the smallest containing circle C. The objective is to determine the coordinates (x_i, y_i) of the center of C_i, i ∈ N, as well as the radius r and center (x, y) of C. This problem, which is a variant of the two-dimensional open dimension problem, is solved using a two-step, dynamic, adaptive, local search algorithm. At each iteration, the algorithm identifies the set of potential “best local positions” of a circle C_i, i ∈ N, given the positions of the previously packed circles, and determines for each of these positions the coordinates and radius of the smallest containing circle. The “best local position” minimizes the radius of the current containing circle. That is, every time an additional circle is packed, both the center and the radius of the containing circle are dynamically updated, and the smallest containing circle is known. The experimental results reflect the good performance of the algorithm.     

Inverse minimum cost flow problems under the weighted Hamming distance

Given a network N(V, A, u, c) and a feasible flow x⁰, an inverse minimum cost flow problem is to modify the cost vector as little as possible to make x⁰ form a minimum cost flow of the network. The modification can be measured by different norms. In this paper, we consider the inverse minimum cost flow problems, where the modification of the arcs is measured by the weighted Hamming distance. Both the sum-type and the bottleneck-type cases are considered. For the former, it is shown to be APX-hard due to the weighted feedback arc set problem. For the latter, we present a strongly polynomial algorithm which can be done in O(n · m²).     

A smoothing self-adaptive Levenberg-Marquardt algorithm for solving system of nonlinear inequalities

In this paper, we consider the smoothing self-adaptive Levenberg-Marquardt algorithm for the system of nonlinear inequalities. By constructing a new smoothing function, the problem is approximated via a family of parameterized smooth equations H(x) = 0. A smoothing self-adaptive Levenberg-Marquardt algorithm is proposed for solving the system of nonlinear inequalities based on the new smoothing function. The Levenberg-Marquardt parameter μ_k is chosen as the product of μ_k = ∥H^k∥^δ with δ ∈ (0, 2] being a positive constant. We will show that if ∥H^k∥^δ provides a local error bound, which is weaker than the non-singularity, the proposed method converges superlinearly to the solution for δ ∈ (0, 1), while quadratically for δ ∈ [1, 2]. Numerical results show that the new method performs very well for system of inequalities.     

Simulation and evaluation of dual fully fuzzy linear systems by fuzzy neural network

In this paper, a novel hybrid method based on fuzzy neural network for approximate solution of fuzzy linear systems of the form Ax = Bx + d, where A and B are two square matrices of fuzzy coefficients, x and d are two fuzzy number vectors, is presented. Here a neural network is considered as a part of a large field called neural computing or soft computing. Moreover, in order to find the approximate solution, a simple and fast algorithm from the cost function of the fuzzy neural network is proposed. Finally, we illustrate our approach by some numerical examples.     

On the completion of a partial integral matrix to a unimodular matrix

We prove that if a partial integral matrix has a free diagonal then this matrix can be completed to a unimodular matrix. Such a condition is necessary in a general sense. Consequently if an n × n (n ? 2) partial integral matrix has 2n − 3 prescribed entries and any n entries of these do not constitute a row or a column then it can be completed to a unimodular matrix. This improves a recent result of Zhan.