Generalization of convergence conditions for a restarted GMRES

We consider the GMRES(s), i.e. the restarted GMRES with restart s for the solution of linear systems Ax = b with complex coefficient matrices. It is well known that the GMRES(s) applied on a real system is convergent if the symmetric part of the matrix A is positive definite. This paper introduces sufficient conditions implying the convergence of a restarted GMRES for a more general class of non‐Hermitian matrices. For real systems these conditions generalize the known result initiated as above. The discussion after the main theorem concentrates on the question of how to find an integer j such that the GMRES(s) converges for all s ≥ j. Additional properties of GMRES obtained by derivation of the main theorem are presented in the last section. Copyright © 2000 John Wiley & Sons, Ltd.     

Necessary and sufficient conditions of optimality for some classical scheduling problems

A scheduling problem is generally to order the jobs such that a certain objective function f(π) is minimized. For some classical scheduling problems, only sufficient conditions of optimal solutions are concerned in the literature. In this paper, we study the necessary and sufficient conditions by means of the concept of critical ordering (critical jobs and their relations). These results are meaningful in recognition and characterization of optimal solutions of scheduling problems.     

抛物型时滞偏微分方程解振动的充要条件

讨论一类多滞量抛物型时滞偏微分方程解的振动性质，获得了其一切解振动的充要条件及一些充分条件；指出了其与普通抛物型偏微分方程解的质的差异．     

Necessary and sufficient conditions for optimal control of quasilinear partial differential systems

First-order necessary and sufficient conditions are obtained for the following quasilinear distributed-parameter optimal control problem: $$max\left\{ {J(u) = \int_\Omega {F(x,u,t) d\omega + } \int_{\partial \Omega } {G(x,t) \cdot d\sigma } } \right\},$$ subject to the partial differential equation $$A(t)x = f(x,u,t),$$ wheret,u,G are vectors andx,F are scalars. Use is made of then-dimensional Green's theorem and the adjoint problem of the equation. The second integral in the objective function is a generalized surface integral. Use of then-dimensional Green's theorem allows simple generalization of single-parameter methods. Sufficiency is proved under a concavity assumption for the maximized Hamiltonian $$H^\circ (x,\lambda ,t) = \max \{ H(x,u,\lambda ,t):u\varepsilon K\} $$ .     

Heavy Ball Flexible GMRES Method for Nonsymmetric Linear Systems

Flexible GMRES (FGMRES) is a variant of preconditioned GMRES, which changes preconditioners at every Arnoldi step. GMRES often has to be restarted in order to save storage and reduce orthogonalization cost in the Arnoldi process. Like restarted GMRES, FGMRES may also have to be restarted for the same reason. A major disadvantage of restarting is the loss of convergence speed. In this paper, we present a heavy ball flexible GMRES method, aiming to recoup some of the loss in convergence speed in the restarted flexible GMRES while keep the benefit of limiting memory usage and controlling orthogonalization cost. Numerical tests often demonstrate superior performance of the proposed heavy ball FGMRES to the restarted FGMRES.     

The Worst-Case GMRES for Normal Matrices

We study the convergence of GMRES for linear algebraic systems with normal matrices. In particular, we explore the standard bound based on a min-max approximation problem on the discrete set of the matrix eigenvalues. This bound is sharp, i.e. it is attainable by the GMRES residual norm. The question is how to evaluate or estimate the standard bound, and if it is possible to characterize the GMRES-related quantities for which this bound is attained (worst-case GMRES). In this paper we completely characterize the worst-case GMRES-related quantities in the next-to-last iteration step and evaluate the standard bound in terms of explicit polynomials involving the matrix eigenvalues. For a general iteration step, we develop a computable lower and upper bound on the standard bound. Our bounds allow us to study the worst-case GMRES residual norm as a function of the eigenvalue distribution. For hermitian matrices the lower bound is equal to the worst-case residual norm. In addition, numerical experiments show that the lower bound is generally very tight, and support our conjecture that it is to within a factor of 4/π of the actual worst-case residual norm. Since the worst-case residual norm in each step is to within a factor of the square root of the matrix size to what is considered an “average” residual norm, our results are of relevance beyond the worst case. This revised version was published online in July 2006 with corrections to the Cover Date.     

Necessary and sufficient conditions for bang-bang control

Necessary and sufficient conditions for the optimal control to be bang-bang are presented for a nonlinear system. The payoff, which is not necessarily quadratic, is assumed to be described by a Hilbert-space norm and to be differentiable and convex. The results are extensions of Ref. 1 to the case of nonlinear systems.     

Necessary and sufficient conditions for hyperplane transversals

We prove that a finite family ={B ₁,B ₂, ...,B _n } of connected compact sets in ^d has a hyperplane transversal if and only if for somek there exists a set of pointsP={p ₁,p ₂, ...,p _n } (i.e., ak-dimensional labeling of the family) which spans ^k and everyk+2 sets of are met by ak-flat consistent with the order type ofP. This is a common generalization of theorems of Hadwiger, Katchalski, Goodman-Pollack and Wenger.Supported in part by NSF grant DMS-8501947 and CCR-8901484, NSA grant MDA904-89-H-2030, and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center, under NSF grant STC88-09648.Supported by the National Science and Engineering Research Council of Canada and DIMACS.     

Necessary and sufficient conditions for quadratic minimality

We provide necessary and sufficient conditions for a (non-convex) quadratic function to take a local minimum over a convex set. Various limiting examples are given.     

Necessary and sufficient conditions for interval-valued differentiability

This paper presents necessary and sufficient conditions for generalized Hukuhara differentiability of interval-valued functions and counterexamples of some equivalences previously presented in the literature, for which important results are based on. Moreover, applications of interval generalized Hukuhara differentiability are presented.     

Necessary and sufficient conditions for multivariate majorization

Let X and Y be m × n matrices whose elements are in K, a real or complex field. We obtain necessary and sufficient conditions for the existence of a matrix A belonging to the convex hull of a certain subgroup of the general linear group GL_n(K) such that X = YA, which unite and generalize several known results concerning majorization.     

Convergence conditions for a restarted GMRES method augmented with eigenspaces

We consider the GMRES(m,k) method for the solution of linear systems Ax=b, i.e. the restarted GMRES with restart m where to the standard Krylov subspace of dimension m the other subspace of dimension k is added, resulting in an augmented Krylov subspace. This additional subspace approximates usually an A‐invariant subspace. The eigenspaces associated with the eigenvalues closest to zero are commonly used, as those are thought to hinder convergence the most. The behaviour of residual bounds is described for various situations which can arise during the GMRES(m,k) process. The obtained estimates for the norm of the residual vector suggest sufficient conditions for convergence of GMRES(m,k) and illustrate that these augmentation techniques can remove stagnation of GMRES(m) in many cases. All estimates are independent of the choice of an initial approximation. Conclusions and remarks assessing numerically the quality of proposed bounds conclude the paper. Copyright © 2004 John Wiley & Sons, Ltd.     

Necessary and sufficient conditions for functions involving the tri- and tetra-gamma functions to be completely monotonic

The psi function ψ(x) is defined by ψ(x)=Γ^′(x)/Γ(x), where Γ(x) is the gamma function. We give necessary and sufficient conditions for the function ψ^″(x)+[ψ^′(x+α)]² or its negative to be completely monotonic on (−α,∞), where . We also prove that the function [ψ^′(x)]²+λψ^″(x) is completely monotonic on (0,∞) if and only if λ1. As an application of the latter conclusion, the monotonicity and convexity of the function e^pψ(x+1)−qx with respect to x(−1,∞) are thoroughly discussed for p≠0 and .     

Necessary and sufficient conditions for finiteness of lifetime

We give a geometric characterization for the finiteness of conditioned Brownian motion for a general class of simply connected domains, extending previous results and exhibit some new examples of domains with infinite area and finite lifetime.I would like to thank Professor Rodrigo Bañuelos, my academic advisor, for his help and guidance on this paper which is part of my Ph.D. thesis.     

Necessary and sufficient conditions for the Robbins-Monro method

This paper examines the relation between convergence of the Robbins-Monro iterates $\text{X}{}_{\mathrm{n+1}}\text{= X}{}_{\mathrm{n}}\text{?a}{}_{\mathrm{n}}\text{?(X}{}_{\mathrm{n}}\text{)+a}{}_{\mathrm{n}}\text{ξ}{}_{\mathrm{n}}\text{, ?(θ)=0}$, and the laws of large numbers S_n=a_nΣ^n?1_j=0ξ_j→0 as n→+∞. If a_n is decreasing at least as rapidly as c/n, then X_n→θw.p. 1 (resp. in L_p, p?1) implies S_n→0 w.p. 1 (resp. in L_p, p?1) as n→+∞. If a_n is decreasing at least as slowly as c?n and lim_n→+∞a_n=0, then S_n→0 w.p. 1 (resp. in L_p, p?2) implies X_n→θw.p. 1 (resp. in L_p, p?2) as n →+∞. Thus, there is equivalence in the frequently examined case $\text{a}{}_{\mathrm{n}}\text{?c?n}$. Counter examples show that the LLN must have the form of S_n, that the rate of decrease conditions are sharp, that the weak LLN is neither necessary nor sufficient for the convergence in probability of X_n to θ when $\text{a}{}_{\mathrm{n}}\text{?c?n}$.     

A simpler GMRES and its adaptive variant for shifted linear systems

A variant of the simpler GMRES method is developed for solving shifted linear systems (SGMRES‐Sh), exhibiting almost the same advantage of the simpler GMRES method over the regular GMRES method. Because the remedy adapted by GMRES‐Sh is no longer feasible for SGMRES‐Sh due to the differences between simpler GMRES and GMRES for constructing the residual vectors of linear systems, we take an alternative strategy to force the residual vectors of the add system also be orthogonal to the subspaces, to which the residual vectors of the seed system are orthogonal when the seed system is solved with the simpler GMRES method. In addition, a seed selection strategy is also employed for solving the rest non‐converged linear systems. Furthermore, an adaptive version of SGMRES‐Sh is presented for the purpose of improving the stability of SGMRES‐Sh based on the technique of the adaptive choice of the Krylov subspace basis developed for the adaptive simpler GMRES. Numerical experiments demonstrate the benefits of the presented methods.