Convergence of the unitary algorithm with a unimodular Wilkinson shift

In applying the algorithm to compute the eigenvalues of a unitary Hessenberg matrix, a projected Wilkinson shift of unit modulus is proposed and proved to give global convergence with (at least) a quadratic asymptotic rate for the iteration. Experimental testing demonstrates that the unimodular shift produces more efficient numerical convergence.

     

Homotopic residual correction processes

We present and analyze homotopic (continuation) residual correction algorithms for the computation of matrix inverses. For complex indefinite Hermitian input matrices, our homotopic methods substantially accelerate the known nonhomotopic algorithms. Unlike the nonhomotopic case our algorithms require no pre-estimation of the smallest singular value of an input matrix. Furthermore, we guarantee rapid convergence to the inverses of well-conditioned structured matrices even where no good initial approximation is available. In particular we yield the inverse of a well-conditioned matrix with a structure of Toeplitz/Hankel type in flops. For a large class of input matrices, our methods can be extended to computing numerically the generalized inverses. Our numerical experiments confirm the validity of our analysis and the efficiency of the presented algorithms for well-conditioned input matrices and furnished us with the proper values of the parameters that define our algorithms.

     

Convergence of relaxation schemes to the equations of elastodynamics

We study the effect of approximation matrices to semi-discrete relaxation schemes for the equations of one-dimensional elastodynamics. We consider a semi-discrete relaxation scheme and establish convergence using the theory of compensated compactness. Then we study the convergence of an associated relaxation-diffusion system, inspired by the scheme. Numerical comparisons of fully-discrete schemes are carried out.

     

Non-commutative positive kernels and their matrix evaluations

We show that a formal power series in non-commuting indeterminates is a positive non-commutative kernel if and only if the kernel on -tuples of matrices of any size obtained from this series by matrix substitution is positive. We present two versions of this result related to different classes of matrix substitutions. In the general case we consider substitutions of jointly nilpotent -tuples of matrices, and thus the question of convergence does not arise. In the ``convergent' case we consider substitutions of -tuples of matrices from a neighborhood of zero where the series converges. Moreover, in the first case the result can be improved: the positivity of a non-commutative kernel is guaranteed by the positivity of its values on the diagonal, i.e., on pairs of coinciding jointly nilpotent -tuples of matrices. In particular this yields an analogue of a recent result of Helton on non-commutative sums-of-squares representations for the class of hereditary non-commutative polynomials. We show by an example that the improved formulation does not apply in the ``convergent' case.

     

A parallel algorithm for the eigenvalues and eigenvectors of a general complex matrix

Summary A new parallel Jacobi-like algorithm is developed for computing the eigenvalues of a general complex matrix. Most parallel methods for this problem typically display only linear convergence, Sequential norm-reducing algorithms also exist and they display quadratic convergence in most cases. The new algorithm is a parallel form of the norm-reducing algorithm due to Eberlein. It is proven that the asymptotic convergence rate of this algorithm is quadratic. Numerical experiments are presented which demonstrate the quadratic convergence of the algorithm and certain situations where the convergence is slow are also identified. The algorithm promises to be very competitive on a variety of parallel architectures. In particular, the algorithm can be implemented usingn ²/4 processors, takingO(n log² n) time for random matrices.This research was supported by the Office of Naval Research under Contract N00014-86-k-0610 and by the U.S. Army Research Office under Contract DAAL 03-86-K-0112. A portion of this research was carried out while the author was visiting RIACS, Nasa Ames Research Center     

Products of Beta matrices and sticky flows

A discrete model of Brownian sticky flows on the unit circle is described: it is constructed with products of Beta matrices on the discrete torus. Sticky flows are defined by their moments which are consistent systems of transition kernels on the unit circle. Similarly, the moments of the discrete model form a consistent system of transition matrices on the discrete torus. A convergence of Beta matrices to sticky kernels is shown at the level of the moments. As the generators of the n-point processes are defined in terms of Dirichlet forms, the proof is performed at the level of the Dirichlet forms. The evolution of a probability measure by the flow of Beta matrices is described by a measure-valued Markov process. A convergence result of its finite dimensional distributions is deduced.Mathematics Subject Classification (2000):60J27, 60J35, 60G09     

An analysis of reduced Hessian methods for constrained optimization

We study the convergence properties of reduced Hessian successive quadratic programming for equality constrained optimization. The method uses a backtracking line search, and updates an approximation to the reduced Hessian of the Lagrangian by means of the BFGS formula. Two merit functions are considered for the line search: the ₁ function and the Fletcher exact penalty function. We give conditions under which local and superlinear convergence is obtained, and also prove a global convergence result. The analysis allows the initial reduced Hessian approximation to be any positive definite matrix, and does not assume that the iterates converge, or that the matrices are bounded. The effects of a second order correction step, a watchdog procedure and of the choice of null space basis are considered. This work can be seen as an extension to reduced Hessian methods of the well known results of Powell (1976) for unconstrained optimization.This author was supported, in part, by National Science Foundation grant CCR-8702403, Air Force Office of Scientific Research grant AFOSR-85-0251, and Army Research Office contract DAAL03-88-K-0086.This author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contracts W-31-109-Eng-38 and DE FG02-87ER25047, and by National Science Foundation Grant No. DCR-86-02071.     

On splitting methods for Schrödinger-Poisson and cubic nonlinear Schrödinger equations

We give an error analysis of Strang-type splitting integrators for nonlinear Schrödinger equations. For Schrödinger-Poisson equations with an -regular solution, a first-order error bound in the norm is shown and used to derive a second-order error bound in the norm. For the cubic Schrödinger equation with an -regular solution, first-order convergence in the norm is used to obtain second-order convergence in the norm. Basic tools in the error analysis are Lie-commutator bounds for estimating the local error and -conditional stability for error propagation, where for the Schrödinger-Poisson system and for the cubic Schrödinger equation.

     

Limit cycles of polynomial differential systems with homogeneous nonlinearities of degree 4 via the averaging method

By using the averaging method, we study the limit cycles for a class of quartic polynomial differential systems as well as their global shape in the plane. More specifically, we analyze the global shape of limit cycles bifurcating from a Hopf bifurcation and also from periodic orbits with linear center , . The perturbation of these systems is made inside the class of quartic polynomial differential systems without quadratic and cubic terms.     

The Asymptotics of Wilkinson’s Shift: Loss of Cubic Convergence

One of the most widely used methods for eigenvalue computation is the QR iteration with Wilkinson’s shift: Here, the shift s is the eigenvalue of the bottom 2×2 principal minor closest to the corner entry. It has been a long-standing question whether the rate of convergence of the algorithm is always cubic. In contrast, we show that there exist matrices for which the rate of convergence is strictly quadratic. More precisely, let $T_{ {\mathcal {X}}}One of the most widely used methods for eigenvalue computation is the QR iteration with Wilkinson’s shift: Here, the shift s is the eigenvalue of the bottom 2×2 principal minor closest to the corner entry. It has been a long-standing question whether the rate of convergence of the algorithm is always cubic. In contrast, we show that there exist matrices for which the rate of convergence is strictly quadratic. More precisely, let T _XT_{ {\mathcal {X}}} be the 3×3 matrix having only two nonzero entries (T _X)₁₂=(T _X)₂₁=1(T_{ {\mathcal {X}}})_{12}=(T_{ {\mathcal {X}}})_{21}=1 and let T_\varLambda {\mathcal {T}}_{\varLambda } be the set of real, symmetric tridiagonal matrices with the same spectrum as T _XT_{ {\mathcal {X}}} . There exists a neighborhood U ì T_\varLambda \boldsymbol {{\mathcal {U}}}\subset {\mathcal {T}}_{\varLambda } of T _XT_{ {\mathcal {X}}} which is invariant under Wilkinson’s shift strategy with the following properties. For T₀ ? UT_{0}\in \boldsymbol {{\mathcal {U}}} , the sequence of iterates (T _k ) exhibits either strictly quadratic or strictly cubic convergence to zero of the entry (T _k )₂₃. In fact, quadratic convergence occurs exactly when limT_k=T _X\lim T_{k}=T_{ {\mathcal {X}}} . Let X\boldsymbol {{\mathcal {X}}} be the union of such quadratically convergent sequences (T _k ): The set X\boldsymbol {{\mathcal {X}}} has Hausdorff dimension 1 and is a union of disjoint arcs X^s\boldsymbol {{\mathcal {X}}}^{\sigma} meeting at T _XT_{ {\mathcal {X}}} , where σ ranges over a Cantor set.     

On triangularization of complex matrices by two-dimensional unitary transformations

A theoretical discussion is presented concerning convergence difficulties in applying Jacobi-like methods for triangularization of general complex matrices.This work was performed under Contract DA-ARO(D)-31-124-G 388, Basic Research in Numerical Analysis, a grant given to the University of Texas by the Army Research Office (Durham).     

Circulant Preconditioners for Indefinite Toeplitz Systems

In recent papers circulant preconditioners were proposed for ill-conditioned Hermitian Toeplitz matrices generated by 2-periodic continuous functions with zeros of even order. It was show that the spectra of the preconditioned matrices are uniformly bounded except for a finite number of outliers and therefore the conjugate gradient method, when applied to solving these circulant preconditioned systems, converges very quickly. In this paper, we consider indefinite Toeplitz matrices generated by 2-periodic continuous functions with zeros of odd order. In particular, we show that the singular values of the preconditioned matrices are essentially bounded. Numerical results are presented to illustrate the fast convergence of CGNE, MINRES and QMR methods.This revised version was published online in October 2005 with corrections to the Cover Date.     

Fourier-Galerkin Method for Localized Solutions of Equations with Cubic Nonlinearity

Using a complete orthonormal system of functions in L ²(– ,) a Fourier-Galerkin spectral technique is developed for computing of the localized solutions of equations with cubic nonlinearity. A formula expressing the triple product into series in the system is derived. Iterative algorithm implementing the spectral method is developed and tested on the soliton problem for the cubic Boussinesq equation. Solution is obtained and shown to compare quantitatively very well to the known analytical one. The issues of convergence rate and truncation error are discussed.     

Efficient inversion of the Galerkin matrix of general second-order elliptic operators with nonsmooth coefficients

This article deals with the efficient (approximate) inversion of finite element stiffness matrices of general second-order elliptic operators with -coefficients. It will be shown that the inverse stiffness matrix can be approximated by hierarchical matrices ( -matrices). Furthermore, numerical results will demonstrate that it is possible to compute an approximate inverse with almost linear complexity.

     

Global and Superlinear Convergence of a Restricted Class of Self-Scaling Methods with Inexact Line Searches, for Convex Functions

This paper studies the convergence properties of algorithms belonging to the class of self-scaling (SS) quasi-Newton methods for unconstrained optimization. This class depends on two parameters, say _k and _k , for which the choice _k =1 gives the Broyden family of unscaled methods, where _k =1 corresponds to the well known DFP method. We propose simple conditions on these parameters that give rise to global convergence with inexact line searches, for convex objective functions. The q-superlinear convergence is achieved if further restrictions on the scaling parameter are introduced. These convergence results are an extension of the known results for the unscaled methods. Because the scaling parameter is heavily restricted, we consider a subclass of SS methods which satisfies the required conditions. Although convergence for the unscaled methods with _k 1 is still an open question, we show that the global and superlinear convergence for SS methods is possible and present, in particular, a new SS-DFP method.     

A Note on Ultrametric Matrices

It is proved in this paper that special generalized ultrametric and special matrices are, in a sense, extremal matrices in the boundary of the set of generalized ultrametric and matrices, respectively. Moreover, we present a new class of inverse M-matrices which generalizes the class of matrices.     

A Gauss—Newton method for convex composite optimization

An extension of the Gauss—Newton method for nonlinear equations to convex composite optimization is described and analyzed. Local quadratic convergence is established for the minimization ofh F under two conditions, namelyh has a set of weak sharp minima,C, and there is a regular point of the inclusionF(x) C. This result extends a similar convergence result due to Womersley (this journal, 1985) which employs the assumption of a strongly unique solution of the composite functionh F. A backtracking line-search is proposed as a globalization strategy. For this algorithm, a global convergence result is established, with a quadratic rate under the regularity assumption.This material is based on research supported by National Science Foundation Grants CCR-9157632 and DMS-9102059, the Air Force Office of Scientific Research Grant F49620-94-1-0036, and the United States—Israel Binational Science Foundation Grant BSF-90-00455.