Search

Let Pbe an $n \times n$ nonnegative matrix. In this paper the authors introduce a method called the SCANBAS algorithm for computing a union of (Jordan) chains $\mathcal{C}$ corresponding to the Perron eigenvalue of P, such that $\mathcal{C}$ consists of nonnegative vectors only and such that at each height, $\mathcal{C}$ contains the maximal number of nonnegative vectors of that height possible in a height basis for the Perron eigenspace of P. It is further shown that $\mathcal{C}$ can be extended to a height basis for the Perron eigenspace of P. The chains are extracted from transform components of Pthat are, in turn, polynomials in P. When the Perron eigenspace has a Jordan basis consisting of nonnegative vectors only, this algorithm computes such a basis. The paper concludes with various examples computed by the algorithm using MATLAB. The work here continues and deepens work on computing nonnegative bases for the Perron eigenspace from polynomials in the matrix already begun by Hartwig, Neumann, and Rose and by Neumann and Schneider.

This paper discusses multimatrix generalizations of two well-known orthogonal rank factorizations of a matrix: the generalized singular value decomposition and the generalized QR-(or URV-) decomposition. These generalizations can be obtained for any number of matrices of compatible dimensions. This paper discusses in detail the structure of these generalizations and their mutual relations and gives a constructive proof for the generalized QR-decompositions.

In a previous paper [SIAM J. Matrix Anal. Appl., 10 (1989), pp. 446–456], Cox and Moss proved that the pole assignment algorithm of Petkov, Christov, and Konstantinov [IEEE Trans. Automat. Control, AC-29 (1984), pp. 1045–1048] is numerically stable for the real case. In this paper, a modified version of the algorithm of Petkov, Christov, and Konstantinov for the complex case is analyzed and the full algorithm (real and complex) is shown to be numerically stable.

In recent papers, numerous authors studied the solutions of symmetric positive definite Toeplitz systems $Tx = b$ by the conjugate gradient method for different families of circulant preconditioners C. In this paper new circulant / skewcirculant approximations are introduced to Tand their properties are studied. The main interest is directed to the skewcirculant case. Furthermore, algorithms for computing the eigenvalues of Tare formulated, based on the Lanczos algorithm and Rayleigh quotient iteration. For some numerical examples the spectra of $C^{ - 1} T$ are compared and the behaviour of the introduced eigenvalue algorithms is displayed.

One of the significant problems in modal analysis, that of extracting modal parameters from experimental data, can be written as a separable nonlinear least-squares problem in which a linear combination of nonlinear functions is fit to data in many data sets. The linear parameters are to be specific to each data set but the nonlinear parameters have to minimize the least-squares function for all the data sets. Golub and LeVeque have devised a method for problems like the modal analysis problem where there are multiple data sets. For determining the Jacobian Jof the problem, their algorithm essentially computes a decomposition as if there were only one data set and then uses this decomposition for all the data sets. Many general nonlinear least-squares solvers compute an orthogonal decomposition of the Jacobian and after the Golub–LeVeque algorithm has been applied, this decomposition is the most time-consuming portion of the method. This paper proposes using the orthogonal decomposition of a specific derivative matrix for one data set to reduce the work in determining the orthogonal decomposition of the Jacobian for all the data sets. For general minimizers which require $J^T J$, rather than Jitself, the paper shows how to compute $J^T J$ quickly to take advantage of the structure of the Jacobian in the multiple data set case. For the modal analysis problem, the nonlinear variables in the model also separate, which gives the model additional structure that is exploited to further reduce the construction time. We find that with the economies of speed and storage described below, nonlinear parameter fitting to extract modal parameters from large data sets becomes computationally feasible.

In this paper, the successive overrelaxation (SOR) method for the solution of a linear system whose matrix coefficient Ais block p-cyclic consistently ordered is discussed. In recent works, many researchers considered some “natural” assumptions on the spectrum $\sigma (J_p )$ of the block Jacobi matrix $J_p $ associated with Aand answered the following question: What is the repartitioning of Ainto a block q-cyclic form $(2\leqq q\leqq p)$ which yields the best optimal SOR method for the solution of the given system? In this paper, the same question is answered in the most general case considered so far, that is, under the assumption $\sigma (J_p^p ) \subset [ - \alpha ^p ,\beta ^p ] \subset \mathbb{R}\backslash \{ [1,\infty )\} ,\alpha ,\beta \geqq 0$. It is also shown that the results in all previous works are recovered as particular subcases of the case considered here.

The class of row sufficient linear complementarity problems was introduced in a recent paper by Cottle, Pang, and Venkateswaran [Linear Algebra Appl., 114/115 (1989), pp. 231–249]. In the present paper, two iterative descent algorithms for solving such a linear complementarity problem are developed. One of the algorithms is based on a symmetric variational inequality formulation of the problem, and the other algorithm is an interior-point method which requires a strict feasibility assumption on the problem. Convergence of both algorithms is established. As a by-product of the investigation, a certain property of a column sufficient matrix is uncovered which leads to a constructive way of determining the solvability of a column sufficient linear complementarity problem.

This paper contains a thorough investigation of a family of symmetric “predictor polynomials” associated with a nonnegative-definite Toeplitz matrix. These polynomials are constructed from the classical predictors and from the values assumed by some dual predictors in a fixed point of unit modulus; the appropriate duality is induced by changing the sequence of reflection coefficients into its conjugate mirror image, within a unit modulus factor. The central theme of the paper is a well-defined three-term recurrence relation satisfied by these symmetric polynomials; it motivates the “tridiagonal” terminology. The properties of the recurrence are studied in detail; special attention is paid to the important issue of computing the recurrence coefficients from the reflection coefficients. It is shown how this three-term recurrence formula produces an efficient solution method, called the split Levinson algorithm, for the linear prediction problem.

For a given asymptotically stable linear dynamic system it is often of interest to determine whether stability is preserved as the system varies within a specified class of uncertainties. If, in addition, there also exist associated performance measures (such as the steady-state variances of selected state variables), it is desirable to assess the worst-case performance over a class of plant variations. These are problems of robust stability and performance analysis. In the present paper, quadratic Lyapunov bounds used to obtain a simultaneous treatment of both robust stability and performance are considered. The approach is based on the construction of modified Lyapunov equations, which provide sufficient conditions for robust stability along with robust performance bounds. In this paper, a wide variety of quadratic Lyapunov bounds are systematically developed and a unified treatment of several bounds developed previously for feedback control design is provided.

In this paper, the structure of nonnegative $m \times n$ matrices Asatisfying $AXA = A$, for some nonnegative $n \times m$ matrix X, is obtained. Several equivalent characterizations of such matrices Ahave been given earlier by Plemmons [Proc. Amer. Math. Soc., 39 (1973), pp. 26–32] and Berman–Plemmons [Linear and Multlinear Algebra, 2 (1974), pp. 161–172]. The structure of matrices given in this paper unifies all the previous known results on $\lambda $-monotone matrices where $1 \in \lambda $. The importance of $\lambda $-monotonicity to problems in mathematical economics, in probability and statistics, and in numerical linear algebra, is documented in a recent book by Berman and Plemmons [Nonnegative Matrices in the Mathematical Sciences, Academic Press, New York, 1979].

In this paper, we study the decompositions of a graph Ginto edge-disjoint subgraphs all of which belong to a specified class of graphs $\mathcal{H}$. Let $\alpha (G;\mathcal{H})$ denote the minimum value of the total sum of the sizes of subgraphs in $\mathcal{H}$ into which Gcan be decomposed, taken over all such decompositions of G. Let $\alpha (n;\mathcal{H})$ denote the maximum value of $\alpha (G;\mathcal{H})$ over all graphs Gwith nvertices.In this paper, we settle a conjecture of Katona and Tarján by showing \[ \alpha (n;\mathcal{K}) = \left\lfloor {n^2 /2} \right\rfloor ,\] where $\mathcal{K}$ denotes the set of all complete graphs. Moreover, we show that the complete bipartite graph Gon $\lfloor n/2 \rfloor $ and $\lceil n/2 \rceil $ vertices is the only graph with $\alpha (G;\mathcal{K}) = \alpha (n;\mathcal{K})$.

In this paper we define and discuss the following problem which we call the maximum coverage location problem. A transportation network is given together with the locations of customers and facilities. Thus, for each customer i, a radius $r_i $ is known such that customer ican currently be served by a facility which is located within a distance of $r_i $ from the location of customer i. We consider the problem from the point of view of a new company which is interested in establishing new facilities on the network so as to maximize the company’s “share of the market.” Specifically, assume that the company gains an amount of $w_i $ in case customer idecides to switch over to one of the new facilities. Moreover, we assume that the decision to switch over is based on proximity only, i.e., customer iswitches over to a new facility only if the latter is located at a distance less than $r_i $ from i. The problem is to locate pnew facilities so as to maximize the total gain.The maximum coverage problem is a relatively complicated one even on tree-networks. This is because one aspect of the problem is the selection of the subset of customers to be taken over. Nevertheless, we present an $O ( n^2 p )$ algorithm for this problem on a tree. Our approach can be applied to other similar problems which are discussed in the paper.

This paper extends the theory of graphs associated with real rectangular matrices to include information about the signs of the elements. We show when signed row and column graphs can be defined for the matrix A. We also deduce conditions under which these graphs are balanced. This leads to a definition of the class of quasi-Morishima rectangular matrices A. It is shown that the Perron–Frobenius theorem applies to the matrices $AA^T $ and $A^T A$ when Ais a quasi-Morishima matrix. Finally we examine the applications of our results to several classes of matrices occurring in energy economic models. All results in this paper are purely qualitative in character.

This paper follows as a natural extension of the ideas in a previous paper where we showed that any connected graph may be transformed by a sequence of switchings to any other connected graph of the same degree sequence, in such a way that all the intermediate graphs formed are connected. This was done for simple graphs, multigraphs and pseudographs. Here we show that the corresponding result is true for 2-connected simple graphs. The result for multigraphs and pseudographs will appear elsewhere. We also note that for k-connected graphs where $k\geqq 3$, this transformation theorem seems much more difficult to prove and in the last section of this paper we mention these difficulties.

The subject of this paper is the bounded path tree (BPT) problem: An undirected graph $G ( V,E )$ is given whose edges have nonnegative lengths; two subsets Iand Jof Vare also given, and nonnegative constants $U_i $, $W_i $ are associated with each $i \in I$, $j \in J$. The BPT problem asks for a tree of Gwhose vertex set contains $I \cup J$ and whose path joining vertices iand jis not longer than $U_i + W_j $, for each $i \in I$, $j \in J$. This problem generalizes the shortest path and the minimum longest path spanning tree problem. It complements standard min–max location problems, as it asks for a tree given the facility locations, instead of locating facilities in a given network. In this paper we propose some applications of the BPT problem for the design of emergency and communication networks, show its equivalence to an extension of the absolute center location problem and give an algorithm for its solution. This algorithm requires time $O( k| E | + k | V | \log k )$, where $k = | I \cup J |$, plus time for finding in Gall shortest path lengths between a vertex in $I \cup J$ and a vertex in V. We also consider a few simple extensions of the BPT problem, such as those admitting negative or multiple edge lengths, lower (as well as upper) bounds to path lengths, constants $Z_{ij} $ instead of $U_i + W_i $. We show that all these extensions are NP-complete.

The focus of the present paper is on the relations between the set Dof optimal solutions of a maximum weighted stable set problem, and the set Cof optimal solutions of its continuous relaxation. The main result is that if a variable takes a constant binary value in all$\hat X \in C$, then it takes the same value in all$\hat X \in D$ (this may be contrasted with a well-known result of Nemhauser and Trotter, stating that if a variable takes a binary value in some$\hat X \in C$, then it takes the same value in some$X \in D$). For any graph G, the set Pof the vertices jsuch that $\hat X_j $ has a constant binary value in all$\hat X \in C$, can be efficiently detected; moreover, the results in this paper imply that in the unweighted case, the subgraph induced by Phas the “strong” König–Egerváry property and that the subgraph induced by the complement of Phas a perfect 2-matching: actually, the maximum stable sets of Gare in a 1-to-1 correspondence with those of the latter subgraph.

This paper examines the problem of recognizing competition graphs (niche overlap graphs), a notion introduced and studied extensively by Cohen [Food Webs and Niche Space, Princeton Univ. Press, Princeton, NJ, 1978]. Beginning with an acyclic digraph $F = ( V,A )$, define its competition graph $K (F ) = ( V,E)$ by $( x,y ) \in E$ if and only if there exists a wsuch that $( x,w ) \in A$ and $( y,w ) \in A$. A graph, G, is a competition graph if there exists an Fsuch that $G = K ( F )$. Roberts [Lecture Notes in Mathematics 642, Springer-Verlag, New York, 1978, pp. 477–490] studied recognizing competition graphs and, equivalently, computing an arbitrary graphs competition number, $k( G )$. The competition number, which he showed to be well defined, is the smallest ksuch that $G \cup I_k $ is a competition graph. In this paper we settle a question posed by Roberts and show that recognizing competition graphs is NP-complete by reducing it to R-CONTENT as defined by Orlin [Nederl. Akad. Wetensch. Proc. Ser. A, 80 (1977), pp. 406–424]. We also give bounds on $k ( G )$ in terms of R-Content $( G )$ and compute $k ( G )$ for the class of line graphs using a technique similar to that in Roberts.

The decade ahead will be one of heightened concern for costs versus benefits to end users of electric energy. More than in the past, the distribution planner will be concerned about investment costs, operating efficiency and reliability of service. The advent of new dispersed generation, storage and control technologies for distribution systems will change not only the alternatives available to the planner, but also the planning methods themselves.This paper summarizes the development of new distribution planning methods. In particular, methods have been developed for both expansion planning and operations planning of radial distribution systems. A particular application of distribution automation and control will be for temporary distribution system reconfiguration during either forced outages or maintenance/construction-related outages. Remotely controlled switches can be used to transfer load among radial feeders during construction, maintenance or other service interruptions—thereby reducing or preventing outages for many customers. This paper describes computerized methods for evaluating the reliability benefits of such advanced distribution systems.

The results in this paper are closely related to the effective use of the divide-and-conquer strategy for solving problems on planar graphs. It is shown that every planar graph can be partitioned into two or more components of roughly equal size by deleting only $O ( \sqrt{n} )$ vertices, and such a partitioning can be found in $O ( n )$ time. Some of the theorems proved in the paper are improvements on the previously known theorems while others are of more general form. An upper bound for the minimum size of the partitioning set is found.

In this paper we discuss discrete search for a number of objects distributed among a number of cells. A cell is chosen during each inspection period and objects removed. The initial number of objects in each cell has a discrete probability density independent of the number in another cell. Under a wide variety of conditions, it is shown that in order to maximize the expected discounted value of objects discovered in a fixed and infinite number of inspection periods, the myopic rule of selecting the cell at each stage which has largest expected value of objects is optimal.We prove this in the first part of the paper when objects are binomially distributed in each cell and later in the second part show that the myopic rule is optimal for a wide variety of distributions using the same proofs presented in the first part of the paper.

This paper examines the problem of determining the threshold dimension of a graph. There exists numerous characterizations of threshold graphs, those graphs of threshold dimension one, as well as fast polynomial time algorithms to test if a graph is a threshold graph. Yannakakis [1982] proved that, in general, determining the threshold dimension is a hard problem by proving that for fixed $k\geqq 3$, determining if the threshold dimension of a graph is less than or equal to kis an NP-complete problem. In this paper we compute the threshold dimension of several classes of graphs and obtain upper and lower bounds on the threshold dimension of a graph. Counterexamples to a conjecture on threshold dimension are provided.

The paper studies factorizations $a ( \lambda ) = b ( \lambda ) \cdot c ( \lambda )$ of $n \times n$ matrix polynomials, with emphasis on linear $b ( \lambda )$. It is assumed that $\det a ( \lambda )$ factorizes into scalar polynomials of degree 1. The tool is the concept of Keldysh chains (generalized Jordan chains). In Theorem 1 the linear independence of eigenvectors of a matrix is generalized to Keldysh chains.It is known that there is an $nm \times nm$ matrix polynomial $Kt ( m,a ( \lambda ) )$ such that the Keldysh chains of length $\leqq m$ with respect to an “eigenvalue” $\omega ( \det a ( \omega ) = 0 )$ may be identified with the nonzero vectors in the nullspace of $Kt ( m,a ( \omega ) )$. The main technique of the paper is to exploit the multiplicative property $Kt ( m,a ( \lambda ) ) = Kt ( m,b( \lambda ) ) \cdot Kt ( m,c ( \lambda ) )$ together with the mentioned generalization. Improved factorization results are obtained when det $a( \lambda )$ has more than $( n - 1 ) \cdot \deg a ( \lambda )$ different zeros. Also a number of known facts are derived in a simpler way than before.

This paper introduces a new approach to the T-coloring problem for complete graphs. The problem arises from Hale’s formulation of the channel assignment problem for potentially interfering communication nets. The motivating result of this paper is that the T-span of $K_n $, denoted $\operatorname{sp}_T ( K_n )$, is asymptotically independent of n. More precisely, each T-set has a rate, $\operatorname{rt} ( T )$, and $n /\operatorname{sp}_T ( K_n )$ converges to $\operatorname{rt} ( T )$. We introduce a finite algorithm for computing the rate of T. This is accomplished by associating to a given set Tan infinite sequence of integers with the property that the first nintegers of this sequence T-color $K_n $ in an asymptotically optimal way. Lastly, we compute $\operatorname{rt} ( T )$ or bounds on its value for some interesting special cases of sets T.

The index of many differential/algebraic equations (DAEs) is determined by the structure of the system, that is, by the pattern of nonzero entries in the Jacobians. This paper considers an important subclass of DAEs which can be solved by backward differentiation methods if their index does not exceed two. For this reason, it is desirable to determine whether the index exceeds two or not. In this paper we present an algorithm that determines if the index is one, two, or greater, based only on the structure. The algorithm can be exponential in its execution time: we do not know whether it is possible to get an asymptotically faster algorithm. However, in many practical problems, this algorithm will execute in polynomial time.

Given a random matrix, what condition number should be expected? This paper presents a proof that for real or complex $n \times n$ matrices with elements from a standard normal distribution, the expected value of the log of the 2-norm condition number is asymptotic to $\log n$ as $n \to \infty$. In fact, it is roughly $\log n + 1.537$ for real matrices and $\log n + 0.982$ for complex matrices as $n \to \infty$. The paper discusses how the distributions of the condition numbers behave for large nfor real or complex and square or rectangular matrices. The exact distributions of the condition numbers of $2 \times n$ matrices are also given.Intimately related to this problem is the distribution of the eigenvalues of Wishart matrices. This paper studies in depth the largest and smallest eigenvalues, giving exact distributions in some cases. It also describes the behavior of all the eigenvalues, giving an exact formula for the expected characteristic polynomial.

This paper presents an overview of the periodic Lyapunov equation, both in discrete time and in continuous time. Together with some selected results that have recently appeared in the literature, the paper provides necessary and sufficient conditions for the existence and uniqueness of periodic solutions.

This paper compares the convergence behavior of two popular iterative methods for solving systems of linear equations: the s-step restarted minimal residual method (commonly implemented by algorithms such as $\operatorname{GMRES}( s )$) and $( s - 1 )$-degree polynomial preconditioning. It is known that for normal matrices, and in particular for symmetric positive definite matrices, the convergence bounds for the two methods are the same. In this paper we demonstrate that for matrices unitarily equivalent to an upper triangular Toeplitz matrix, a similar result holds; namely, either both methods converge or both fail to converge. However, we show this result cannot be generalized to all matrices. Specifically, we develop a method, based on convexity properties of the generalized field of values of powers of the iteration matrix, to obtain examples of real matrices for which GMRES$( s )$ converges for every initial vector, but every $( s - 1 )$-degree polynomial preconditioning stagnates or diverges for some initial vector.

In their 1995 manuscript, Farenick and Lee proved that every normal Toeplitz matrix of order less than or equal to 5 is either of type I or of type II and had left open the case of higher order as a conjecture.The author of this paper settled the conjecture affirmatively. Almost simultaneously, Farenick and Lee themselves proved the conjecture in a work with Krupnik and Krupnik [SIAM J. Matrix Anal. Appl., 17 (1996), pp. 1037–1043]. Since the idea of proof in the work just mentioned is somewhat different from the one of this paper, the editor has recommended that the author publish in a separate paper.

Let Abe an $n \times n$ unitary matrix, and let the columns of an $n \times l\,( l < n )$ matrix $\tilde X_1 $ form an orthonormal basis for an approximate eigenspace $\tilde{\mathcal{X}}_1 $ of A. Then there are two problems: How near is $\tilde{\mathcal{X}}_1 $ to an eigenspace of A? How can we make use of the $l \times l$ matrix $\tilde X_1^H A\tilde X_1 $ to get lapproximate eigenvalues of A? This paper gives solutions to these problems. In particular, this paper reveals such a fact: One can use the eigenvalues of the unitary polar factor of $\tilde X_1^H A\tilde X_1 $ (or the eigenvalues of the matrix $\tilde X_1^H A\tilde X_1 $) as lapproximate eigenvalues of A, and the precision of the eigenvalues of the unitary polar factor of $\tilde X_1^H A\tilde X_1 $ (or the eigenvalues of $\tilde X_1^H A\tilde X_1 $) as lapproximate eigenvalues of Ais higher than that of $\tilde{\mathcal{X}}_1 $ as an approximate eigenspace of A.

The aim of this paper is to consider approximating a linear transfer function $F( s )$ of McMillan degree N, by one of McMillan degree min which $N \gg m$ and where Nis large. Krylov subspace methods are employed to construct bases to parts of the controllability and observability subspaces associated with the state space realisation of $F( s )$. Low rank approximate grammians are computed via the solutions to low dimensional Lyapunov equations and computable expressions for the approximation errors incurred are derived. We show that the low rank approximate grammians are the exact grammians to a perturbed linear system in which the perturbation is restricted to the transition matrix, and furthermore, this perturbation has at most rank = 2. This paper demonstrates that this perturbed linear system is equivalent to a low dimensional linear system with state dimension no greater than m. Finally, exact low dimensional expressions for the $\mathcal{L}^\infty $ norm of the errors are derived. The model reduction of discrete time linear systems is considered via the use of the same Krylov schemes. Finally, the behaviour of these algorithms is illustrated on two large scale examples.

Collocation methods based on bicubic Hermite piecewise polynomials have been proven to be effective techniques for solving general second order linear elliptic partial differential equations (PDEs) with mixed boundary conditions [ACM Trans. Math. Software, 11 (1985), pp. 379–412]. The corresponding system of discrete collocation equations is generally nonsymmetric and nondiagonally dominant. Methods for their iterative solution are not known and are currently solved using Gauss elimination with scaling and partial pivoting. Point iterative methods like those in ITPACK [Tech. Report CNA-216, Center for Numerical Analysis, Univ. of Texas at Austin, April 1988] do not converge even for the collocation equations obtained from the discretization of model PDE problems. The development of efficient iterative solvers for these collocation equations is necessary for the case of three-dimensional PDE problems and their parallel solution, since direct solvers tend to be space bound and their parallelization is difficult. In this paper block iterative methods are developed and analyzed for the collocation equations corresponding to elliptic PDEs defined on a rectangle and subject to uncoupled mixed boundary conditions. For these types of PDE problems certain boundary degrees of freedom of the collocation approximation can be predetermined symbolically [Houstis, Mitchell, and Rice]. The remaining equations are called “interior” collocation equations. The system of all discrete equations is referred to as “general” collocation equations. Papatheodorou [Math. Comp., 41 (1983), pp. 511-525] was first to determine the exact parameters of accelerated overrelaxation (AOR)-type iterative methods for the case of “interior” collocation equations associated with a model problem. This paper generalizes the results of Papatheodorou for the “interior” collocation equations and presents new results for a particular class of “general” collocation equations. Specifically, in the case of a model elliptic PDE problem with uncoupled mixed boundary conditions, analytic expressions are derived for the eigenvalues of the block Jacobi iteration matrix based on a new partitioning of the interior collocation matrix, and the optimal overrelaxation factors are determined for the block successive overrelaxation (SOR) iterative method. A number of numerical results are presented to verify the theoretical analysis of the block SOR method and to compare its convergence behavior with those of the block Jacobi, Gauss–Seidel and the optimal AOR of Papatheodorou. Furthermore, the authors compare the time and memory complexity of the block SOR, UNPACK Band GE, and generalized minimal residual (GMRES) mathematical software for solving the Hermite collocation equations obtained from the discretization of several PDE problems. The numerical results indicate that the block SOR is an efficient method for solving these equations.

The main result of this paper is the following index theorem, which is closely related to oscillation theorems on linear selfadjoint differential systems such as results by M. Morse. Let real $m \times m$-matrices $R_1 ,R_2 ,X,U$ be given, which satisfy \[ R_1 R_2^T = R_2 R_1^T ,\quad X^T U = U^T X,\quad \operatorname{rank} (R_1 ,R_2 ) = \operatorname{rank} (X^T ,U^T ) = m . \]Moreover, assume that $X(t),U(t)$ are real $m \times m$-matrix-valued functions on some interval $\mathcal{J} = [-\varepsilon ,\varepsilon ],\varepsilon > 0$, such that \[ X^T (t)U(t) = U^T (t)X(t)\quad{\text{on}}\quad\mathcal{J}, \]\[ X(t) \to X\quad {\text{and}}\quad U(t) \to U\quad{\text{as}}\quad t \to 0, \]\[ X(t)\quad{\text{is invertible for}}\quad t \in \mathcal{J}\backslash \{ 0 \},\quad {\text{and such that}} \]\[ U(t)X^{ - 1} (t)\quad {\text{is decreasing on}}\quad \mathcal{J}\backslash \{ 0 \} \] and define \[ M(t) \equiv R_1 R_2^T + R_2 U(t)X^{ - 1} (t)R_2^T ,\quad \Lambda (t) \equiv R_1 X(t) + R_2 U(t),\quad \Lambda \equiv R_1 X + R_2 U. \] Then $\operatorname{ind} M(0 + )$, $\operatorname{ind} M(0 - )$, and $\operatorname{def} \Lambda(0 + )$ exist and \[ \operatorname{ind} M(0 + ) - \operatorname{ind} M(0 - ) = \operatorname{def} \Lambda - \operatorname{def} \Lambda (0 + ) - \operatorname{def} X, \] where ind denotes the index (the number of negative eigenvalues) and def denotes the defect (the dimension of the kernel) of a matrix. The basic tool for the proof of this result consists of a theorem on the rank of a certain product of matrices, so that this rank theorem is the key result of the present paper.

The paper investigates the problem of computing structured matrix perturbations that cause, or most nearly cause, some specified system matrix to fail to have full rank. The paper discusses some theoretical issues concerning the existence of solutions to these problems. It suggests a numerical approach to computing solutions that utilizes some ideas on differentiation of singular values. Finally, an algorithm for finding structured most rank-reducing perturbations and structured most nearly rank-reducing perturbations is developed. The paper demonstrates convergence of the algorithm to a rank-reducing perturbation or to a local minimum for a most nearly rank-reducing perturbation. Numerical examples illustrating the technique are included.

This paper considers sequential direct methods for the reduction of a sparse symmetric matrix to tridiagonal form using sequences of orthogonal similarity transformations. Currently, the best published approach combines a bandwidth-reducing preordering algorithm, perhaps Gibbs–Poole–Stockmeyer (GPS), with a band-preserving tridiagonalization such as the EISPACK BANDR routine. This paper introduces a new hybrid tridiagonalization algorithm, BANDHYB, based upon band-preserving reduction techniques that rearrange the elimination sequence of nonzero entries to take better advantage of the sparsity within the band of the permuted matrix. For many practical sparse problems a GPS-BANDHYB approach substantially reduces the CPU requirements of tridiagonalization, compared to a GPS-BANDR scheme, without increasing storage requirements. Over a wide range of sparse problems the new algorithm reduced CPU time by an average of 31%, with reductions of more than 60% observed for some problems.

This paper examines the problem of computing a minimum norm real matrix perturbation that causes a general complex (system) matrix to drop rank. Given the state model describing a linear time-invariant system, the norm of this matrix perturbation helps to determine the robustness of several system properties with respect to real parameter variations. The norm of this perturbation, or the real-restricted singular value of the complex matrix, is known to be a discontinuous function of the complex matrix. The paper presents a simple condition on the complex matrix that eliminates this discontinuity. Specifically, the paper shows that the size of the smallest real rank-reducing perturbation is a continuous function of the complex matrix as long as the imaginary part of the complex matrix has full rank. The paper examines other aspects of the continuity of the problem. It also presents an algorithm that converges to a point satisfying a necessary condition for obtaining the smallest real rank-reducing matrix perturbation. A Lyapunov function approach is used to establish convergence of the algorithm. Some numerical examples are included illustrating the accuracy of the approach.

This paper considers the problem of finding the principal eigenspace and/or eigenpairs of $M \times M$ Hermitian matrices that can be expressed or approximated by a low-rank matrix plus a shift, i.e., ${\bf A} = {\bf B} + \sigma {\bf I}$, where ${\bf B}$ is a rank dHermitian matrix and $d \ll M$. Such matrices arise in signal processing, geophysics, dynamic structure analysis, and other fields. The proposed problem can be solved by a full $O( M^3 )$ eigendecomposition, or by several more efficient alternatives, e.g., the power, subspace iteration, and Lanczos algorithms. This paper shows that the Lanczos algorithm can exploit the inherent structure and is generally more efficient than other alternatives. More specifically, if ${\bf A} = {\bf B} + \sigma {\bf I}$, the Lanczos algorithm can be used to exactly determine the principal eigenspace span$\{ {\bf B} \}$ and $\sigma $ with a finite amount of computation. If ${\bf A}$ is close to ${\bf B} + \sigma {\bf I}$, the Lanczos algorithm can estimate the principal eigenvectors and eigenvalues in $O( M^2 d )$ flops. It is shown that the errors in the estimates of the kth principal eigenvalue $\lambda _k $ and eigenvector ${\bf e}_k $ decay at the rate of $\varepsilon ^2/( \lambda _k - \sigma )^2 $ and $\varepsilon/( \lambda _k - \sigma )$, respectively, where $\varepsilon $ is a measure of the mismatch between ${\bf A}$ and ${\bf B} + \sigma {\bf I}$.

Recently, a uniform approach was given by B. Beckermann and G. Labahn [Numer. Algorithms, 3 (1992), pp. 45–54] for different concepts of matrix-type Padé approximants, such as descriptions of vector and matrix Padé approximants along with generalizations of simultaneous and Hermite Padé approximants. The considerations in this paper are based on this generalized form of the classical scalar Hermite Padé approximation problem, power Hermite Padé approximation. In particular, this paper studies the problem of computing these new approximants.A recurrence relation is presented for the computation of a basis for the corresponding linear solution space of these approximants. This recurrence also provides bases for particular subproblems. This generalizes previous work by Van Barel and Bultheel and, in a more general form, by Beckermann. The computation of the bases has complexity $\mathcal{O} ( \sigma ^2 )$, where $\sigma $ is the order of the desired approximant and requires no conditions on the input data. A second algorithm using the same recurrence relation along with divide-and-conquer methods is also presented. When the coefficient field allows for fast polynomial multiplication, this second algorithm computes a basis in the super-fast complexity $\mathcal{O}( \sigma \log ^2 \sigma )$. In both cases the algorithms are reliable in exact arithmetic. That is, they never break down, and the complexity depends neither on any normality assumptions nor on the singular structure of the corresponding solution table. As a further application, these methods result in fast (and superfast) reliable algorithms for the inversion of striped Hankel, layered Hankel, and (rectangular) block-Hankel matrices.

A nonnegative symmetric matrix Bhas row maxima prescribed by a given vector r, if for each index i, the maximum entry in the ith row of Bequals $r_i $. This paper presents necessary and sufficient conditions so that for a given nonnegative symmetric matrix Aand positive vector rthere exists a positive diagonal matrix Dsuch that $B = DAD$ has row maxima prescribed by r. Further, an algorithm is described that either finds such a matrix Dor shows that no such matrix exists. The algorithm requires $O( n\lg n + p )$ comparisons, $O( p )$ multiplications and divisions, and $O( q )$ square root calculations where nis the order of the matrix, pis the number of its nonzero elements, and qis the number of its nonzero diagonal elements. The solvability conditions are compared and contrasted with known solvability conditions for the analogous problem with respect to row sums. The results are applied to solve the problem of determining for a given nonnegative rectangular matrix Apositive, diagonal matrices Dand Esuch that $DAE$ has prescribed row and column maxima. The paper presents an equivalent graph formulation of the problem. The results are compared to analogous results for scaling a nonnegative matrix to have prescribed row and column sums and are extended to the problem of determining a matrix whose rows have prescribed $l_p $ norms.

This article concerns the positive semidefinite matrices $M_+ ( G )$ with zero entries in prescribed locations; that is, matrices with given sparsity graph G. The issue here is the rank of the extremals of the cone $M_+ ( G )$. It was shown in [J. Agler, J. W. Helton, S. McCullough, and L. Rodman, Linear Algebra Appl., 107 (1988), pp. 101–149] that the key in constructing high rank extreme points resides in certain atomic graphs Gcalled blocks and superblocks. The k-superblocks are defined to be sparsity graphs Gthat contain an extreme point of rank kwhile containing (in an extremely strong sense) no graph with the same property. The goal of this article is to write down all graphs that are superblocks. The article succeeds completely for $k \leq 4$ and it lists necessary conditions in general as well as sufficient conditions. The subject is closely related to orthogonal representations of graphs as studied earlier in [L. Lovász, M. Saks, and A. Schrijver, Linear Algebra Appl., 114/115 (1989), pp. 439–454] and in the previously mentioned paper by Alger et al. Indeed, the paper is an extension of the findings of Alger et al.

This paper deals with the sensitivity of the solution of a nearly uncoupled Markov chain (NUMC). Such a chain arises in various applications where the states to be modeled can be grouped into loosely connected aggregates. The solution of an NUMC is very sensitive to general perturbations. However, in practice the perturbation has a special structure which renders worst case perturbation bounds a large overestimate. In this paper the structure of the perturbation is exploited and it is shown that the solution is very insensitive to a certain class of structured perturbations.

This paper addresses the problem of partitioning the vertex set of an edge-weighted undirected graph into two parts of specified sizes so as to minimize the sum of the weights on edges joining Vertices in different parts. This problem is NP-hard and has several important applications in which the graph size is typically large and the brute-force approach (of listing all feasible partitions and comparing costs) is computationally prohibitive. In this paper a new class of algorithms is developed on the basis of a transformation of the graph problem to a geometric problem of clustering a set of points in Euclidean space. Instead of searching through all feasible partitions that meet the size specifications, it is shown that the search can be confined to a set of $n^{p( p + 1 )/2} $ partitions, where nis the number of vertices in the graph and pis the rank of the $n \times n$ graph connection matrix. Procedures are developed for constructing all such partitions in $O( n^{p( p + 3 ) /2} )$ time. For matrices with large ranks, approximation of the connection matrix by a matrix of low rank by using principal-components analysis is suggested. The algorithms presented in this paper are constructive algorithms in that they generate a feasible partition of the graph directly from the connection matrix, as opposed to iterative algorithms that start from a feasible partition as an initial guess. The algorithms also bound the difference between the achieved cost and the lowest achievable cost. These lower bounds on the cost of the optimal partition are proved to be superior to the Donath–Hoffman lower bound for two significant special cases wherein either the two part sizes are equal or the graph connection matrix has equal row sums. Simulation results on randomly constructed graphs of different sizes clearly demonstrate the effectiveness of these heuristics in terms of both the cost of the constructed partition and the lower bound provided.

This paper considers the solution of the homogeneous system of linear equations $Ap = 0$ subject to $c^H p = 1$ where $A \in {\bf C}^{n \times n} $ is a singular matrix of rank $n - 1$, $c, p \in {\bf C}^n$, and $c^H A = 0$. It is assumed that the vector cis known. An important applications context for this problem is that of finding the stationary distribution of a Markov chain. In that context, Ais a real singular M-matrix of the form $A = I - Q^T $ where Qis row stochastic. In previous work by Barlow [SIAM J. Algebraic Discrete Methods, 7 (1986), pp. 414–424], it was shown that, for Aan M-matrix, this problem could be solved by solving a nonsingular linear system Bof degree $n - 1$ that was a principal submatrix of A. Moreover, this matrix Bcould always be chosen so that $\| B^{ - 1} \|_2 \approx \| A^\dag \|_2 $. Thus a stable algorithm to solve this problem could be developed for the Markov modeling problem using LU decomposition without pivoting and an update step that identified the correct submatrix.In this paper, that result is improved in several ways. First, it is shown that many of the results can be generalized to the case where Ais any complex matrix of degree nwith rank $n - 1$; thus they can be generalized to the case where $A = \lambda I - Q^H $ and $\lambda$ is a simple eigenvalue of $Q^H $. Second, it is shown that the update step is not necessary for the Markov modeling problem. For that problem, LU decomposition is used without pivoting. Finally, it is shown that a more elegant characterization and sharper error bounds are obtained for this algorithm in terms of the group inverse $A^# $. In fact, the error is shown to be bounded in terms of $\| A^{#} \|_1 \| | A | | p | \|_1 $, which is smaller than the more traditional condition number $\| A^# \|_1 \| A \|_1 $. These bounds show that the procedure is unconditionally stable.

This paper is concerned with the solution of the linear system $Ax = b$ by the modified successive overrelaxation (MSOR) method, if Abelongs to some classes of matrices. It is proven that the classes presented here are subclasses of H-matrices. Since, the general conditions for convergence of MSOR method for the class of H-matrices are not always easy to check in practice, some more practical conditions concerning these subclasses of H-matrices are given in this paper.