LU decompositions of generalized diagonally dominant matrices

Summary Using the simple vehicle ofM-matrices, the existence and stability ofLU decompositions of matricesA which can be scaled to diagonally dominant (possibly singular) matrices are investigated. Bounds on the growth factor for Gaussian elimination onA are derived. Motivation for this study is provided in part by applications to solving homogeneous systems of linear equationsAx=0, arising in Markov queuing networks, input-output models in economics and compartmental systems, whereA or –A is an irreducible, singularM-matrix.This paper extends earlier work by Funderlic and Plemmons and by Varga and Cai.Research sponsored by the Applied Mathematical Sciences Research Program, Office of Energy Research, U.S. Department of Energy under contract W-7405-eng-26 with the Union Carbide CorporationResearch supported in part by the National Science Foundation under Grant No. MCS 8102114Research supported in part by the U.S. Army Research Office under contract no. DAAG 29-81-k-0132     

On the zeros and poles of Padé approximants toe z . III

Summary In this paper, we continue our study of the location of the zeros and poles of general Padé approximants toe ^z . We state and prove here new results for the asymptotic location of the normalized zeros and poles for sequences of Padé approximants toe ^z , and for the asymptotic location of the normalized zeros for the associated Padé remainders toe ^z . In so doing, we obtain new results for nontrivial zeros of Whittaker functions, and also generalize earlier results of Szegö and Olver.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2688Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2729, and by the Energy Research and Development Administration (ERDA) under Grant EY-76-S-02-2075     

Quadrature formulas for oscillatory integral transforms

Summary Quadrature formulas are obtained for the Fourier and Bessel transforms which correspond to the well-known Gauss-Laguerre formula for the Laplace transform. These formulas provide effective asymptotic approximations, complete with error bounds. Comparison is also made between the quadrature formulas and the asymptotic expansions of these transforms.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada under Contract A7359     

On monotone Abel-Volterra integral equations on the half line

Summary In this paper we reanalyze the trapezoidal method for the solution of nonlinear Abel-Volterra integral equations on the half line. We prove the convergence of the method in the uniform norm, provided the nonlinearity is Lipschitz-continuous and strictly monotone.Research supported in part by the United States Army under contracts DAAG29-83-K-0109 and DAAG 29-85-G-0009     

The treatment of nonhomogeneous Dirichlet boundary conditions by thep-version of the finite element method

Summary The paper addresses the problem of the implementation of nonhomogeneous essential Dirichlet type boundary conditions in thep-version of the finite element method.Partially supported by the Office of Naval Research under Grant N-00014-85-K-0169Research partially supported by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR 85-0322     

A finite element method for the Tricomi problem

Summary We consider the numerical solution of the Tricomi problem. Using a weak formulation based on different spaces of test and trial functions, we construct a new Galerkin procedure for the Tricomi problem. Existence, uniqueness, and uniform stability of the approximate solution is proven, and a priori error bounds are given.Research supported in part by the Department of Energy under contract DOE E(40-1)3443     

On computing the center of a convex quadratically constrained set

We propose a method for finding analytic center of a convex feasible region whose boundaries are defined by quadratic functions. The algorithm starts from an arbitrary initial point and approaches to the desired center by simultaneously reducing infeasibility or slackness of all constraints. A partial Newton step is taken at each iteration.Research supported in part by the ONR under grant N00014-87-K-0214 and by the NSF under grant CCR-8810107.Research supported in part by the NSF under grant ECS-8721709.     

The scalar curvature equation on 2- and 3-spheres

In this article we obtain a priori estimates for solutions to the prescribed scalar curvature equation on 2- and 3-spheres under a nondegeneracy assumption on the curvature function. Using this estimate, we use the continuity method to demonstrate the existence of solutions to this equation when a map associated to the given curvature function has non-zero degree.Research of first author supported in part by NSF grant 91-03949Research of second author supported by a NSF Postdoctoral Fellowship.Research of third author supported in part by NSF grant 91-02872 and the Ellentuck Fund.     

On the sharpness of theorems concerning zero-free regions for certain sequences of polynomials

Summary In this paper, we establish the sharpness of a theorem concerning zero-free parabolic regions for certain sequences of polynomials satisfying a three-term recurrence relation. Similarly, we establish the sharpness of a zero-free sectorial region for certain sequences of Padé approximants toe ^z .Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2688Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2729, and by the Energy Research and Development Administration (ERDA) under Grant E(11-1)-2075     

On the relation between quadratic termination and convergence properties of minimization algorithms

Summary It is shown that the theory developed in part I of this paper [22] can be applied to some well-known minimization algorithms with the quadratic termination property to prove theirn-step quadratic convergence. In particular, some conjugate gradient methods, the rank-1-methods of Pearson and McCormick (see Pearson [18]) and the large class of rank-2-methods described by Oren and Luenberger [16, 17] are investigated.This work was supported in part at Stanford University, Stanford, California, under Energy Research and Development Administration, Contract E(04-3) 326 PA No. 30, and National Science Foundation Grant DCR 71-01996 A04 and in part by the Deutsche Forschungsgemeinschaft     

On conforming finite element methods for the inhomogeneous stationary Navier-Stokes equations

Summary We consider the stationary Navier-Stokes equations, written in terms of the primitive variables, in the case where both the partial differential equations and boundary conditions are inhomogeneous. Under certain conditions on the data, the existence and uniqueness of the solution of a weak formulation of the equations can be guaranteed. A conforming finite element method is presented and optimal estimates for the error of the approximate solution are proved. In addition, the convergence properties of iterative methods for the solution of the discrete nonlinear algebraic systems resulting from the finite element algorithm are given. Numerical examples, using an efficient choice of finite element spaces, are also provided.Supported, in part, by the U.S. Air Force Office of Scientific Research under Grant No. AF-AFOSR-80-0083Supported, in part, by the same agency under Grant No. AF-AFOSR-80-0176-A. Both authors were also partially supported by NASA Contract No. NAS1-15810 while they were in residence at the Institute for Computer Applications in Science and Engineering, NASA Langley Research Center, Hampton, VA 23665, USA     

Geometric convergence of rational approximations toe −z in infinite sectors

Summary In this paper, we study the geometric convergence of rational approximations toe ^–z in infinite sectors symmetric about the positive real axis.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2688, and by the University of South Florida Research CouncilResearch supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2729, and by the Atomic Energy Commission under Grant AT (11-1)-2075     

Expansions for statistics involving the mean absolute deviations

Expansion for the difference of mean absolute deviations from the sample mean and the population mean is derived. This result is used to obtain strong representations for mean absolute deviations from the sample mean and the sample median. Edgeworth expansions for some scale invariant statistics involving the mean absolute deviations are studied. These expansions are shown to be valid in spite of the presence of a lattice variable.Research supported in part by NSA Grant MDA904-90-H-1001.Research supported by the Air Force Office of Scientific Research under Grant AFOSR-89-0279.     

On the zeros and poles of Padé approximants toe z

Summary In this paper, we study the location of the zeros and poles of general Padé approximats toe ^z. The location of these zeros and poles is useful in the analysis of stability for related numerical methods for solving systems of ordinary differential equations.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2688, and by the University of South Fla. Research Council.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2729, and by the Atomic Energy Commission under Grant AT(11-1)-2075.     

Eigenvalues of graded matrices and the condition numbers of a multiple eigenvalue

Summary This paper concerns two closely related topics: the behavior of the eigenvalues of graded matrices and the perturbation of a nondefective multiple eigenvalue. We will show that the eigenvalues of a graded matrix tend to share the graded structure of the matrix and give precise conditions insuring that this tendency is realized. These results are then applied to show that the secants of the canonical angles between the left and right invariant of a multiple eigenvalue tend to characterize its behavior when its matrix is slightly perturbed.This work was supported in part by the Air Force Office of Sponsored Research under Contract AFOSR-87-0188     

Weakly self-injective semilattices

In this note we characterize weakly self-injective semilattices as Brouwerian semilattices which are compact in the residuated interval topology. We also characterize weakly self-injective semigroups which are semilattices of groups with trivial multiplication. Research of first author supported in part by a research grant from the Faculty Research Committee of Bowling Green State University. Research of second author supported in part by a postdoctoral fellowship in the Biomathematics Program at North Carolina State University under PHS Grant #GM-678 from NIGMS.     

On a direct method for the solution of nearly uncoupled Markov chains

Summary This note is concerned with the accuracy of the solution of nearly uncoupled Markov chains by a direct method based on the LU decomposition. It is shown that plain Gaussian elimination may fail in the presence of rounding errors. A modification of Gaussian elimination with diagonal pivoting and correction of small pivots is proposed and analyzed. It is shown that the accuracy of the solution is affected by two condition numbers associated with aggregation and the coupling respectively.This work was supported in part by the Air Force Office of Sponsored Research under Contract AFOSR-87-0188     

Shellability of exponential structures

We show that the poset of all partitions of an nd-set with block size divisible by d is shellable. Using similar techniques, it also follows that various other examples of exponential structures cited by Stanley are also shellable. The method used involves the notion of recursive atom orderings introduced by Björner and Wachs.Research supported in part by NATO post-doctoral grant administered by the NSF.     

Large regular graphs with no induced 2K 2

Letr be a positive integer. Considerr-regular graphs in which no induced subgraph on four vertices is an independent pair of edges. The numberv of vertices in such a graph does not exceed 5r/2; this proves a conjecture of Bermond. More generally, it is conjectured that ifv>2r, then the ratiov/r must be a rational number of the form 2+1/(2k). This is proved forv/r≥21/10. The extremal graphs and many other classes of these graphs are described and characterized. Research supported in part by the National Science Foundation under ISP 80110451. Research supported in part by the National Science Foundation under DMS-8401281. Research supported in part by the National Science Foundation under DMS-8504322, and by the Office of Naval Research under N00014-85K0570.     

A parallel projection method for solving generalized linear least-squares problems

Summary A parallel projection algorithm is proposed to solve the generalized linear least-squares problem: find a vector to minimize the 2-norm distance from its image under an affine mapping to a closed convex cone. In each iteration of the algorithm the problem is decomposed into several independent small problems of finding projections onto subspaces, which are simple and can be tackled parallelly. The algorithm can be viewed as a dual version of the algorithm proposed by Han and Lou [8]. For the special problem under consideration, stronger convergence results are established. The algorithm is also related to the block iterative methods of Elfving [6], Dennis and Steihaug [5], and the primal-dual method of Springarn [14].This material is based on work supported in part by the National Science foundation under Grant DMS-8602416 and by the Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign