Bounds for the infinity norm of the inverse for certain M- and H-matrices

The paper presents new two-sided bounds for the infinity norm of the inverse for the so-called PM-matrices, which form a subclass of the class of nonsingular M-matrices and contain the class of strictly diagonally dominant matrices. These bounds are shown to be monotone with respect to the underlying partitioning of the index set, and the equality cases are analyzed. Also an upper bound for the infinity norm of the inverse of a PH-matrix (whose comparison matrix is a PM-matrix) is derived. The known Ostrowski, Ahlberg–Nilson–Varah, and Mora?a bounds are shown to be special cases of the upper bound obtained.     

On diagonal dominance arguments for bounding 6A-16∞

In a recent paper by J.M. Varah, an upper bound for 6A^-16_∞ was determined, under the assumption that A is strictly diagonally dominant, and this bound was then used to obtain a lower bound for the smallest singular value for A. In this note, this upper bound for 6A^-16_∞ is sharpened, and extended to a wider class of matrices. This bound is then used to obtain an improved lower bound for the smallest singular value of a matrix.     

A parallel interior point algorithm for linear programming on a network of transputers

Interior Point algorithms have become a very successful tool for solving large-scale linear programming problems. The Dual Affine algorithm is one of the Interior Point algorithms implemented in the computer program OB1. It is a good candidate for implementation on a parallel computer because it is very computing-intensive. A parallel Dual Affine algorithm is presented which is suitable for a parallel computer with a distributed memory. The algorithm obtains its speedup from parallel sparse linear algebra computations such as Cholesky factorisation, matrix multiplication, and triangular system solving, which form the bulk of the computing work. Efficient algorithms based on the grid distribution of matrices are presented for each of these computations. The algorithm is implemented in occam 2 on a square mesh of transputers. The resulting parallel program is connected to the sequentialFortran 77 program OB1, which performs the preprocessing and the postprocessing. Experimental results on a mesh of 400 transputers are given for a test set of seven realistic planning and scheduling problems from Shell and seven problems from the NETLIB LP collection; the results show a speedup of 88 for the largest problem.     

Solving Hankel matrix approximation problem using semidefinite programming

Positive semidefinite Hankel matrices arise in many important applications. Some of their properties may be lost due to rounding or truncation errors incurred during evaluation. The problem is to find the nearest matrix to a given matrix to retrieve these properties. The problem is converted into a semidefinite programming problem as well as a problem comprising a semidefined program and second-order cone problem. The duality and optimality conditions are obtained and the primal–dual algorithm is outlined. Explicit expressions for a diagonal preconditioned and crossover criteria have been presented. Computational results are presented. A possibility for further improvement is indicated.     

Estimation of the Separation of Two Matrices

The estimation of the solution to the matrix equation AX-XB=C is primarily dependent on the quantity sep(A,B) introduced by Stewart. Varah has given some examples to show that $sep_F(A,B)$ can be very small even though the eigenvalues of A and B are well separated. In this paper we give some lower bounds of $sep_F(A,B)$.     

Factoring symmetric totally nonpositive matrices and inverses with a diagonal pivoting method

In this paper, we consider how to factor symmetric totally nonpositive matrices and their inverses by taking advantage of the symmetric property. It is well-known that the Bunch-Kaufman algorithm is the most commonly used pivoting strategy which can, however, produce arbitrarily large entries in the lower triangular factor for such matrices as illustrated by our example. Therefore, it is interesting to show that when the Bunch-Parlett algorithm is simplified for these matrices, it only requires O(n ²) comparisons with the growth factor being nicely bounded by 4. These facts, together with a nicely bounded lower triangular factor and a pleasantly small relative backward error, show that the Bunch-Parlett algorithm is more preferable than the Bunch-Kaufman algorithm when dealing with these matrices.     

IIS branch-and-cut for joint chance-constrained stochastic programs and application to optimal vaccine allocation

We present a new method for solving stochastic programs with joint chance constraints with random technology matrices and discretely distributed random data. The problem can be reformulated as a large-scale mixed 0–1 integer program. We derive a new class of optimality cuts called IIS cuts and apply them to our problem. The cuts are based on irreducibly infeasible subsystems (IIS) of an LP defined by requiring that all scenarios be satisfied. We propose a method for improving the upper bound of the problem when no cut can be found. We derive and implement a branch-and-cut algorithm based on IIS cuts, and refer to this algorithm as the IIS branch-and-cut algorithm. We report on computational results with several test instances from optimal vaccine allocation. The computational results are promising as the IIS branch-and-cut algorithm gives better results than a state-of-the-art commercial solver on one class of problems.     

An efficient algorithm for the multivariable Adomian polynomials

In this article the sum of the series of multivariable Adomian polynomials is demonstrated to be identical to a rearrangement of the multivariable Taylor expansion of an analytic function of the decomposition series of solutions u₁, u₂, … , u_m about the initial solution components u_1,0, u_2,0, … , u_m,0; of course the multivariable Adomian polynomials were developed and are eminently practical for the solution of coupled nonlinear differential equations. The index matrices and their simplified forms of the multivariable Adomian polynomials are introduced. We obtain the recurrence relations for the simplified index matrices, which provide a convenient algorithm for rapid generation of the multivariable Adomian polynomials. Another alternative algorithm for term recurrence is established. In these algorithms recurrence processes do not require complicated operations such as parametrization, expanding and regrouping, derivatives, etc. as practiced in prior art. The MATHEMATICA program generating the Adomian polynomials based on the algorithm in this article is designed.     

Inversion of band matrices

In this paper, a formula for inverting general band matrices is established. It takes a simple form when the matrices are tridiagonal, and as a special case it includes the Bukhberger-Emel'yanenko algorithm for symmetric tridiagonal matrices.     

Fast computation of eigenvalues of companion,comrade, and related matrices

The class of eigenvalue problems for upper Hessenberg matrices of banded-plus-spike form includes companion and comrade matrices as special cases. For this class of matrices a factored form is developed in which the matrix is represented as a product of essentially 2×2 matrices and a banded upper-triangular matrix. A non-unitary analogue of Francis’s implicitly-shifted QR algorithm that preserves the factored form and consequently computes the eigenvalues in O(n ²) time and O(n) space is developed. Inexpensive a posteriori tests for stability and accuracy are performed as part of the algorithm. The results of numerical experiments are mixed but promising in certain areas. The single-shift version of the code applied to companion matrices is much faster than the nearest competitor.     

Convergence of the shifted QR algorithm on 3×3 normal matrices

Summary This paper concerns the convergence properties of the shifted QR algorithm on 3×3 normal, Hessenberg matrices. The algorithm is viewed as an iteration on one dimensional subspaces. A class of matrices is characterized for which HQR2 is unable to approximate a solution.The author was partially supported by the NSF     

实规范矩阵的特征值问题

实对称矩阵的特征值问题,无论是低阶稠密矩阵的全部特征值问题,或高阶稀疏矩阵的部分特征值问题,都已有许多有效的计算方法,迄今最重要的一些成果已总结在[5]中。本文利用规范矩阵的一些重要性质将对于Hermite矩阵(特别是对弥矩阵)特征值问题的一些有效算法推广到规范矩阵的特征值问题,由于对复规范阵的推广是简单的,而且实际上常遇到的是实矩阵(这时常要求只用实运算),因此我们着重讨论实规范矩阵的特征值问题。     

基于交替投影算法求解单变量线性约束矩阵方程问题

研究如下线性约束矩阵方程求解问题:给定A∈R~(m×n),B∈R~(n×p)和C∈R~(m×p),求矩阵X∈R(?)R~(n×n)"使得A×B=C以及相应的最佳逼近问题,其中集合R为如对称阵,Toeplitz阵等构成的线性子空间,或者对称半(ε)正定阵,(对称)非负阵等构成的闭凸集.给出了在相容条件下求解该问题的交替投影算法及算法收敛性分析.通过大量数值算例说明该算法的可行性和高效性,以及该算法较传统的矩阵形式的Krylov子空间方法(可行前提下)在迭代效率上的明显优势,本文也通过寻求加速技巧进一步提高算法的收敛速度.     

Convex quadratic programming with one constraint and bounded variables

In this paper we propose an iterative algorithm for solving a convex quadratic program with one equality constraint and bounded variables. At each iteration, a separable convex quadratic program with the same constraint set is solved. Two variants are analyzed: one that uses an exact line search, and the other a unit step size. Preliminary testing suggests that this approach is efficient for problems with diagonally dominant matrices. This work was supported by a research grant from the France-Quebec exchange program and also by NSERC Grant No. A8312. The first author was supported by a scholarship from Transport Canada while doing this research.     

A bandwidth reduction algorithm for L-shaped and Z-shaped grid structured graphs

In this paper, a viable bandwidth reduction algorithm based on graphs for reducing the bandwidth of sparse symmetric matrices, arising from standard L-structured and Z-structured graphs, is presented. Bandwidth results for these matrices are obtained using this algorithm and compared with that of existing algorithms. This algorithm can easily be applied to these matrices while the bandwidths obtained are as good as those obtained with the existing algorithms.     

Solution of the eigenvalue problem for a regular pencil λA0−A1 with singular matrices

One considers the generalized eigenvalue problem (A₀λ?A₁)x=0, (1) when one or both matrices A₀,A₁ are singular and ker A₀ ∩ ker A₁=φ is the empty set. With the aid of the normalized process, the solving of problem (1) reduces to the solving of the eigenvalue problem of a constant matrix of order r=min (r₀,r₁), where r₀,r₁ are the ranks of the matrices A₀,A₁, which are determined at the normalized decomposition of the matrices. One gives an Algol program which performs the presented algorithm and testing examples.     

Conley's spectral sequence via the sweeping algorithm

In this article we consider a spectral sequence (Er,dr) associated to a filtered Morse-Conley chain complex (C,Δ), where Δ is a connection matrix. The underlying motivation is to understand connection matrices under continuation. We show how the spectral sequence is completely determined by a family of connection matrices. This family is obtained by a sweeping algorithm for Δ over fields F as well as over Z. This algorithm constructs a sequence of similar matrices Δ⁰=Δ,Δ¹,… , where each matrix is related to the others via a change-of-basis matrix. Each matrix Δr over F (resp., over Z) determines the vector space (resp., Z-module) Er and the differential dr. We also prove the integrality of the final matrix ΔR produced by the sweeping algorithm over Z which is quite surprising, mainly because the intermediate matrices in the process may not have this property. Several other properties of the change-of-basis matrices as well as the intermediate matrices Δr are obtained.     

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.     

A norm-reducing Jacobi-like algorithm for the eigenvalues of non-normal matrices

A new norm decreasing Jacobi-like method for reducing a non-normal matrix to a normal one is described. The method is an improved version of the Huang-Gregory's procedure [6], in which certain norm reducing non-optimal steps are replaced by the optimal ones, which correspond no more to regular matrix transformations. The method renders itself particularly effective in dealing with defective matrices of special forms. Theory and experiments alike indicate that this algorithm is in all computational aspects — accuracy, convergence rate, computing time, complexity of the computer program — better or at least as good as the original one.Both procedures, the original and the improved one, end in all of the authors computed examples with the diagonal matrix containing the eigenvalues of the non-normal initial matrix.     

On the solution of the symmetric eigenvalue complementarity problem by the spectral projected gradient algorithm

This paper is devoted to the eigenvalue complementarity problem (EiCP) with symmetric real matrices. This problem is equivalent to finding a stationary point of a differentiable optimization program involving the Rayleigh quotient on a simplex (Queiroz et al., Math. Comput. 73, 1849–1863, 2004). We discuss a logarithmic function and a quadratic programming formulation to find a complementarity eigenvalue by computing a stationary point of an appropriate merit function on a special convex set. A variant of the spectral projected gradient algorithm with a specially designed line search is introduced to solve the EiCP. Computational experience shows that the application of this algorithm to the logarithmic function formulation is a quite efficient way to find a solution to the symmetric EiCP.