Computing optimal scalings by parametric network algorithms

Asymmetric scaling of a square matrixA 0 is a matrix of the formXAX ^–1 whereX is a nonnegative, nonsingular, diagonal matrix having the same dimension ofA. Anasymmetric scaling of a rectangular matrixB 0 is a matrix of the formXBY ^–1 whereX andY are nonnegative, nonsingular, diagonal matrices having appropriate dimensions. We consider two objectives in selecting a symmetric scaling of a given matrix. The first is to select a scalingA of a given matrixA such that the maximal absolute value of the elements ofA is lesser or equal that of any other corresponding scaling ofA. The second is to select a scalingB of a given matrixB such that the maximal absolute value of ratios of nonzero elements ofB is lesser or equal that of any other corresponding scaling ofB. We also consider the problem of finding an optimal asymmetric scaling under the maximal ratio criterion (the maximal element criterion is, of course, trivial in this case). We show that these problems can be converted to parametric network problems which can be solved by corresponding algorithms.This research was supported by NSF Grant ECS-83-10213.     

Optimally scaled matrices,necessary and sufficient conditions

Summary We shall in this paper consider the problem of determination a row or column scaling of a matrixA, which minimizes the condition number ofA. This problem was studied by several authors. For the cases of the maximum norm and of the sum norm the scale problem was completely solved by Bauer [1] and Sluis [5]. The condition ofA subordinate to the pair of euclidean norms is the ratio /, where and are the maximal and minimal eigenvalue of (A ^H A)^1/2 respectively. The euclidean case was considered by Forsythe and Strauss [3]. Shapiro [6] proposed some approaches to a numerical solution in this case. The main result of this paper is the presentation of necessary and sufficient conditions for optimal scaling in terms of maximizing and minimizing vectors. A uniqueness proof for the solution is offered provided some normality assumption is satisfied.     

On the convergence of the symmetric SOR method for matrices with red-black ordering

Summary We prove that if the matrixA has the structure which results from the so-called red-black ordering and ifA is anH-matrix then the symmetric SOR method (called the SSOR method) is convergent for 0<<2. In the special case thatA is even anM-matrix we show that the symmetric single-step method cannot be accelerated by the SSOR method. Symmetry of the matrixA is not assumed.     

Deadbeat control: A special inverse eigenvalue problem

In this paper we give a numerical method to construct a rankm correctionBF (where then ×m matrixB is known and them ×n matrixF is to be found) to an ×n matrixA, in order to put all the eigenvalues ofA +BF at zero. This problem is known in the control literature as deadbeat control. Our method constructs, in a recursive manner, a unitary transformation yielding a coordinate system in which the matrixF is computed by merely solving a set of linear equations. Moreover, in this coordinate system one easily constructs the minimum norm solution to the problem. The coordinate system is related to the Krylov sequenceA ^–1 B,A ^–2 B,A ^–3 B, .... Partial results of numerical stability are also obtained.Dedicated to Professor Germund Dahlquist: on the occasion of his 60th birthday     

Properties of balanced and perfect matrices

In this paper we define wheel matrices and characterize some properties of matrices that are perfect but not balanced. A consequence of our results is that if a matrixA is perfect then we can construct a polynomial number of submatricesA _I,,A _n ofA such thatA is balanced if and only if all the submatricesA ₁,,A _n ofA are perfect. This implies that if the problem of testing perfection is polynomially solvable, then so is the problem of testing balancedness.Partial support under NSF Grants DMS-8606188, ECS-8800281 and DDM-8800281.     

On a theorem of Stein-Rosenberg type in interval analysis

Summary In classical numerical analysis the asymptotic convergence factor (R ₁-factor) of an iterative processx ^m+1=Ax^m+b coincides with the spectral radius of then×n iteration matrixA. Thus the famous Theorem of Stein and Rosenberg can at least be partly reformulated in terms of asymptotic convergence factor. Forn×n interval matricesA with irreducible upper bound and nonnegative lower bound we compare the asymptotic convergence factor ( _T ) of the total step method in interval analysis with the factor _S of the corresponding single step method. We derive a result similar to that of the Theorem of Stein and Rosenberg. Furthermore we show that _S can be less than the spectral radius of the real single step matrix corresponding to the total step matrix |A| where |A| is the absolute value ofA. This answers an old question in interval analysis.     

On thep-ranks of net graphs

Let be ak-net of ordern with line-point incidence matrixN and letA be the adjacency matrix of its collinearity graph. In this paper we study thep-ranks (that is, the rank over ) of the matrixA+kl withp a prime dividingn. SinceA+kI=N ^T N thesep-ranks are closely related to thep-ranks ofN. Using results of Moorhouse on thep-ranks ofN, we can determiner _p (A+kI) if is a 3-net (latin square) or a desarguesian net of prime order. On the other hand we show how results for thep-ranks ofA+kI can be used to get results for thep-ranks ofN, especially in connection with the Moorhouse conjecture. Finally we generalize the result of Moorhouse on thep-rank ofN for desarguesian nets of orderp a bit to special subnets of the desarguesian affine plane of orderp ^e .The author is financially supported by the Cooperation Centre Tilburg and Eindhoven Universities.     

Underlying graph and total length of optimal realizations of variable distance matrices

The general problem is to investigate, for acceptable values ofx, the optimal graph realization of a matrixD(x) obtained from a given tree-realizable distance matrixD as follows: we partition the index set ofD into two convex subsetsH andK, we subtractx from all entriesd _hk andd _kh whereh H andk K and we leave all other entries unchanged. We describe the optimal realization of the matrixD(x) and the behaviour of the total length of the optimal realization as a function ofx. This work was supported by the National Science Foundation Grant DMS-8401686 and by the PSC/CUNY Research Award Program.     

On the eigenvalue distribution of a class of preconditioning methods

Summary A class of preconditioning methods depending on a relaxation parameter is presented for the solution of large linear systems of equationAx=b, whereA is a symmetric positive definite matrix. The methods are based on an incomplete factorization of the matrixA and include both pointwise and blockwise factorization. We study the dependence of the rate of convergence of the preconditioned conjugate gradient method on the distribution of eigenvalues ofC ^–1 A, whereC is the preconditioning matrix. We also show graphic representations of the eigenvalues and present numerical tests of the methods.     

On optimal global error bounds obtained by scaled local error estimates

Summary In the second section a general method of obtaining optimal global error bounds by scaling local error estimates is developed. It is reduced to the solution of a fixpoint problem. In Sect. 3 we show more concrete error estimates reflecting a singularity of order . It is shown that under general circumstances an optimal global error bound is achieved by an (asymptotically) geometric mesh for the local error estimates. In the fourth section we specialize this to the best approximation ofg(x)x by piecewise polynomials with variable knots and degrees having a total numberN of parameters. This generalizes the result of R. DeVore and the author forg(x)=1. In the last section this problem is studied for the functione ^–x on (0, ). The exact asymptotic behaviour of the approximation withN parameters is determined toe ^qoN , whereq _o=0.895486 ....     

A conforming decomposition theorem,a piecewise linear theorem of the alternative,and scalings of matrices satisfying lower and upper bounds

A scaling of a nonnegative matrixA is a matrixXAY ^?1, whereX andY are nonsingular, nonnegative diagonal matrices. Some condition may be imposed on the scaling, for example, whenA is square,X=Y or detX=detY. We characterize matrices for which there exists a scaling that satisfies predetermined upper and lower bound. Our principal tools are a piecewise linear theorem of the alternative and a theorem decomposing a solution of a system of equations as a sum of minimal support solutions which conform with the given solutions.     

On the computation of a versal family of matrices

The aim of this article is to present algorithms for the computation of versal deformations of matrices. A deformation of a matrixA ₀ is a holomorphic matrix-valued function whose value at a pointt ₀C ^p is the matrixA ₀. We want to study the properties of these matrices in a neighbourhood oft ₀. One could, for each valuet in this neighbourhood, compute the Jordan form as well as the change of basis matrix; but, generally, the results will not be analytic. So, we want to construct a deformation of the matrixA ₀ into which any deformation can be transformed by an invertible deformation of the matrixId. After having introduced the notion of versal deformation, we shall provide computer algebra algorithms to computer these normal forms. In the last section, we shall show that a one-parameter deformation can be transformed into a simpler form than the general versal deformation.     

Difference sets and inverting the difference operator

For a setA of non-negative numbers, letD(A) (the difference set ofA) be the set of nonnegative differences of elements ofA, and letD ^k be thek-fold iteration ofD. We show that for everyk, almost every set of non-negative integers containing 0 arises asD ^k (A) for someA. We also give sufficient conditions for a setA to be the unique setX such that 0X andD ^k (X)=D ^k (A). We show that for eachm there is a setA such thatD(X)=D(A) has exactly 2 ^m solutionsX with 0X.This work was supported by grants DMS 92-02833 and DMS 91-23478 from the National Science Foundation. The first author acknowledges the support of the Hungarian National Science Foundation under grants, OTKA 4269, and OTKA 016389, and the National Security Agency (grant No. MDA904-95-H-1045).Lee A. Rubel died March 25, 1995. He is very much missed by his coauthors.     

Polyhedral sets having a least element

For a fixedm × n matrixA, we consider the family of polyhedral setsX _b ={x|Ax b}, b R ^m , and prove a theorem characterizing, in terms ofA, the circumstances under which every nonemptyX _b has a least element. In the special case whereA contains all the rows of ann × n identity matrix, the conditions are equivalent toA ^T being Leontief. Among the corollaries of our theorem, we show the linear complementarity problem always has a unique solution which is at the same time a least element of the corresponding polyhedron if and only if its matrix is square, Leontief, and has positive diagonals.This research was supported by the National Science Foundation under Grants GK-18339 and GP-25738, by the Office of Naval Research under Contracts N00014-67-A-0112-0050 (NR-042-264) and N00014-67-A-0112-0011, and by the IBM Corporation. Part of the second author's contribution to this paper was made while he was on sabbatical leave in 1968–9 as a consultant to the IBM Research Center. Reproduction in whole or in part is permitted for any purpose of the United States Government.     

On schematic orthogonal arraysOA(q t,k, q,t)

Am × k matrixA, with entries from a set ofq 2 elements, is called an orthogonal arrayOA(m, k, q, t) (t 2) if eachm × t submatrix ofA contains all possible 1 ×t row vectors with the same frequency(m = q ^t ). We call the array schematic if the set of rows ofA forms an association scheme with the relations determined by the Hamming distance. In this paper we determine the schematic orthogonal arraysOA(q ^t ,k, q, t) with2t – 1 > k.     

On the unique solvability of the Runge-Kutta equations

Summary We consider the existence of a unique solution to the systems of equations that arise when we apply a Runge-Kutta method to a stiff nonlinear system of differential equationsU =f(t, U), withf satisfying a one-sided Lipschitz condition with constant . For any given product h, whereh denotes the step size, we present algebraic conditions on the Runge-Kutta matrixA which are necessary and sufficient for unique solvability of the equations. As a second topic, we consider the question whether the solution to the system of equations is stable with respect to perturbations (known as BSI-stability). For this property also, necessary and sufficient algebraic conditions onA are presented.The research of this author has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences (K.N.A.W.). This work was finished while this author was visiting the Massachusetts Institute of Technology with additional financial support provided by L.N. Trefethen from his U.S. National Science Foundation Presidential Young Investigator AwardPart of this research was done while this author was visiting the University of Leiden with an Erwin Schrödinger stipend from the Fonds zur Förderung der wissenschaftlichen Forschung and financial support of the Netherlands Organization for Scientific Research (N.W.O.)     

A factorization of an integral 2×2 matrix via a rational method

While a 2×2 integral matrixA with characteristic polynomialx ²-m,m=2,3 (4), and square free, cannot always be expressed as the product of two integral symmetric matrices, it can be expressed as the product of two rational matrices, simultaneously similar to two integral symmetric matrices. This can be achieved in various ways. The paper deals with numerical examples which depend on the 2-part of the ideal class-group attached tox ²-m (see earlier work by the author, especially Acta Arith. 24, 151–156 (1973)).Dedicated to professor E. Hlawka on the occasion of his seventieth birthdayThe term rational is used here also to refer to not algebraic.     

The simultaneous computation of a few of the algebraically largest and smallest eigenvalues of a large,sparse, symmetric matrix

A heuristic argument and supporting numerical results are given to demonstrate that a block Lanczos procedure can be used to compute simultaneously a few of the algebraically largest and smallest eigenvalues and a corresponding eigenspace of a large, sparse, symmetric matrixA. This block procedure can be used, for example, to compute appropriate parameters for iterative schemes used in solving the equationAx=b. Moreover, if there exists an efficient method for repeatedly solving the equation (A–I)X=B, this procedure can be used to determine the interior eigenvalues (and corresponding eigenvectors) ofA closest to .     

The symmetric procrustes problem

The following symmetric Procrustes problem arises in the determination of the strain matrix of an elastic structure: find the symmetric matrixX which minimises the Frobenius (or Euclidean) norm ofAX — B, whereA andB are given rectangular matrices. We use the singular value decomposition to analyse the problem and to derive a stable method for its solution. A perturbation result is derived and used to assess the stability of methods based on solving normal equations. Some comparisons with the standard, unconstrained least squares problem are given.